The Ramsey Theorems, at their core, capture a profound combinatorial truth: sufficient structure can not avoid order. Chaos can not be manufactured at scale because patterns will always emerge. If you are unfamiliar with Ramsey, you may be suspicious upon reading this. Examples may come to mind… Like $\pi$. Didn’t we learn in primary school that $\pi$ has infinitely many non-zero decimals that never repeat? Well, yes and that’s still true, but what Ramsey states is a little more nuanced than that what you might think, and doesn’t really reveal much which is substantially meaningful about the infamous digits of $\pi$. It will make more sense as we dive in and explore just what this means.

For general purposes, I’ll use some python code that is available on my GitHub (link top right corner). I’ll have a few custom functions that have been well named to indicate what it is they do, however to save space from trivial programming I will ommit their definitions from this page so we can focus on the algorithmic content. Again, the definitions for these functions can be found on my GitHub. Let’s start by discussing Infinte Ramsey, which we’ll be working at within the contexts of graphs, i.e. networks.

Infinite Ramsey

$$\text{Given the coloring } \chi_r(K_\omega) \text{ where } r \in \mathbb{N} \text{,} \space \exists K_\alpha \subseteq K_\omega \text{ s.t. } K_\alpha \text{ is an infinite monochromatic clique in } \chi_r(K_\omega)$$

Let’s put that in more widely digestable terms. Consider an infinitely large neighborhood, where ever house is connected to every other house via single road. There are a finite number of names to choose from when naming each road. This theorem states that no matter how the neighborhood names the streets, there must be an infinite number of houses in the neighborhood which are all connected to one another by roads all with the same name.

For some that may seem intuitively plausible. Those without a background in formal proofs may find that it sounds like a ridiculous claim. So lets prove that, beyond any doubt, it must be the case.

Proof

Let $K_\omega$ denote an infinite complete graph.
Let $r \in \mathbb{N}$ be the number of colors in the coloring $\chi_r(K_\omega)$.
Select $v_1 \in V(K_\omega)$ and partition $V(K_\omega)/v_1$ based on the edge color of $\{v_1,v_i\}$.
Since $r$ is finite, by pigeonhole principle, $\exists S_1 \subseteq V(K_\omega)$ such that $S_1$ is infinite and the edge set $\Set{\{v_1,v_i\}|v_i\isin S_1}$ is monochromatic.
Call this color $c_1$, where $c_1 \isin \{1,...,r\}$.
Now, let $v_n \isin S_n$.
Select some $v_{n+1} \isin S_n$ and partition $S_n$ similarly based on colors of $\{v_{n+1},v_i\}\forall v_i \isin S_n$.
Since $r$ is finite, by pigeonhole principle, $\exists S_{n+1} \subseteq S_n$ such that $S_{n+1}$ is infinite and the edge set $\Set{\{v_{n+1},v_i\}|v_i\isin S_{n+1}}$ is monochromatic.
Call this color $c_{n+1}$.
We can construct an infinite complete graph coloring in this way, with a sequence of vertices and color selections:
$\{(v_1,c_1),...,(v_n,c_n),...\}$ where $c_i \isin \{1,...,r\} \forall i$ and $v_m \isin S_n \forall m>n$.
Since $r$ is finite, we once again see pigeonhole principle states there must be some $c\isin\{1,...,r\}$ which occurs infinitely many times, $c^*$.
We now have an infinite monochromatic clique in the coloring $chi_r(K_\omega)$.
$\blacksquare$

In plain english…
Take an infinite complete graph, a graph where every vertex (or node) is connected to all other vertices, and color each of the infinite edges. You can select any color for each edge from $r$ possible colors. Select any one vertex, and separate all other vertices into partitions based on the color of their connecting edge with our selected vertex. Since we have finitely many colors to choose from, there must be one color which connects our vertex to infinitely many other vertices. This is due to what’s called the pigeonhole principle.

Quickly put, the pigeonhole principle goes like this: only so many pigeonholes but infinite pigeons, if no pigeonhole had infinite pigeons then there would have to be finitely many pigeons, but there are infinite pigeons, therefor atleast one pigeonhole has infinite pigeons. Whew… lots of birds.

So lets remove all other vertices not connected to our selected vertex with this infinite color edge. Notice we still have an infinite complete graph. Now let us continue this process. We do this over and over, selecting different colors each time, but never removing the selected vertices. Each of these selected vertices has a color associated with it. Birds incoming! Again, by pigeonhole principle, we know that atleast one color can be selected infinitely many times as we continue. Do we know which color that must be? Nope. But we know it exists! And now we know that there must be an infinite monochromatic clique within the coloring.

It seems almost trivial when considering a set of 3, 5, or even 10 colors. But what’s amazing about keeping things in the abstract with proofs, this holds true when dealing with 10,000 colors! Or any finite amount. Amazing, yes, but difficult to wrap the mind around with infinity in the mix. Let’s consider the concepts of the more approachable finite cousin to this theorem.

Finite Ramsey

$$\text{Given } r,n,t\isin \mathbb{N},\space \exists N \isin \mathbb{N} \text{ s.t. } \chi_r(K_N) \text{ contains a monochromatic clique of size } n \text{ or of size } t \space \forall \space r \text{-colorings,} \newline \text{and } \exists \space \chi_r(K_m) \text{with no monochromatic cliques of size } n \text{ or } t \space \forall \space m \isin \mathbb{N} \text{ where } m<N$$

You can look at the proof for this theorem, but I think we have enough to cover here so you can just take my word for it: someone already proved this to be true (I wonder who?).

What this theorem is stating is that if you are given a number of colors, $r$, and 2 sizes for a desired clique, $n$ and $t$, there is a minimum sized complete graph, $K_N$, which guarantees the existence of a monochromatic clique with either $n$ or $t$ vertices. This “Ramsey Number”, $N$, is often looked at where $r=2$ and in this case is denoted by $N=R(n,t)$. To really understand this, in simpler terms, let’s talk through the most common example. The party problem.

Lets say you are throwing a party. Your friend, Callicles, challenges you to throw the smallest party possible such that if he chose random guests to attend, the party is guaranteed to have either a group of 3 people who all know one another, or a group of 3 strangers. We can frame the relationships between guests as a coloring of a complete graph. With $N$ party guests, we have our $K_N$ which we will give a 2-coloring to represent the binary relationship between each guest. A $\color{red}{\text{red}}$ edge denotes the two endpoints are strangers, a $\color{blue}{\text{blue}}$ edge denotes familiarity. In our example, we are simply solving for $R(3,3)$. To search these colorings, we’ll need an algorithm. To be thorough, and since our example is relatively simple, we can use the obvious and robust approach with little concern for the run time complexity. We can generate every possible coloring for each sized $K_N$, check every coloring for an absence of a 3-clique, otherwise known as a triangle, until we find a set of coloring permutations which all contain a monocolored triangle. This is the brute force approach, but don’t worry. We’ll look into a more elegant approach momentarily.

Using python, lets generate all possible graph $2$-colorings for $K_N$. We can do so by considering the edge set, and encode each possible partition using binary. For example, if we have three edges, we encode the partitions into three digits. $101$ would indicate the first and last edges in the set are selected to be red because the first and last digits of our code are $1$‘s, and the middle edge would be blue. As you might have noticed, we can save ourselves a bit of time knowing we have symmetry. Since the actual color doesn’t really matter in our case, we can recognize that our binary interpretation would essentially duplicate our colorings. $010$ would be the same as $101$, and $111$ would be the same as $000$. So we can save ourselves a little extra search time. We can trim just a hair more by excluding monochromatic colorings, as we know that these satisfy the conditions of our search.

def generate_all_colorings(N):
    edges = list(combinations(range(N),2))
    partitions = []
    total = len(edges)
    for i in range(1,2**(total-1)):
        red = {edges[j] for j in range(total) if i & (1 << j)} #doing a binary selection if bit j is set in i
        blue = {edges[j] for j in range(total) if not(i & (1<<j))} | {edges[-1]} #grabs everything left over
        partitions.append([red,blue])
    return partitions

Since we need atleast 3 people at the party (or Callicles will accuse us of cheating), we’ll begin with the fairly simple case of $K_3$. Our search leads us to the graph below:

all_colorings=generate_all_colorings(3)
red = list(all_colorings[1][0])
blue = list(all_colorings[1][1])

r_coloring_K_n(3,edge_coloring=[red,blue], node_size=2000, labels={0:"Calvin", 1:"Hobbes", 2:"Scooby"}, palette=["red","blue"])

That’s not very interesting. A little too easy. I didn’t even run search code, I just picked one at random. Let’s move on to $K_4$, where we’ll actually need to our search for satisfactory colorings.

def monochromatic_triangle_check(partition):
    results = []
    for i, edge_set in enumerate(partition):
        for triple in combinations(edge_set,3):
            numbers = set()
            for pair in triple:
                numbers.update(pair)
            if len(numbers) == 3:
                results.append(triple)
    return(results)

n_coloring = generate_all_colorings(4)
for i in range(len(n_coloring)):
    if not monochromatic_triangle_check(n_coloring[i]):
        print(n_coloring[i])
        break

This search then produces a coloring which indicates we may move on to the next iteration.

Remember, we’re only interested in monochromatic triangles where each corner is a vertex, so the intersection here does not satisfy the condition. Fairly straightforward still, how about $K_5$?

This is itterative process is tedious, didn’t I say this was an inefficient approach? Let’s see what our code turns up with for $K_6$.

It seems nothing which satisfies can be found…

Eureka! We have found our solution: $R(3,3)=6$

Hardly an interesting approach. Let us construct an algorithm which can seek out a coloring with no monochromatic cliques, and do so such that if it fails we know it is not possible. Please note, the following method is also computationally expensive, at sufficiently large $N$ we could not run this easily. But we’ll get into current day limitations later.

Our approach will be to construct the $K_N$ graph one vertex at a time, drawing edges between each new vertex and all the prior vertices. We will color each edge according to the risk of creating a monochromatic clique. If the edge can not be colored without creating a clique of the given sizes, we backtrace the search to the prior edge. If a coloring passes, we know the Ramsey Number is greater than $N$, and the smallest value of $N$ which fails gives us our $R(3,3)$. For generalization purposes, we’ll make the algorithm so that we can pass it different sizes of cliques and color sets.

#First we'll define a "danger score" that prioritizes colorings for each "decision point" in the algorithm
#We want to consider the intersection of the neighborhoods of both vertices incident to the edge we are coloring
#We then consider the (n-2)-cliques inside this intersection, which tells us which colorings would be forbidden
def danger_score(u, v, color, coloring, n_clique):
    if n_clique <= 2:
        return 0
    colored_with_u = {
        w for (a, b), c in coloring.items()
        if c == color and (a == u or b == u)
        for w in ([b] if a == u else [a])
    } #vertices color adjacent to u
    colored_with_v = {
        w for (a, b), c in coloring.items()
        if c == color and (a == v or b == v)
        for w in ([b] if a == v else [a])
    } #vertices color adjacent to v
    W = frozenset(colored_with_u & colored_with_v) #intersection of the neighborhoods identified
    return count_cliques(W, coloring, color, n_clique - 2) #the higher the score the more danger

#Then we can implement our algorithm using this danger score as a guide.
#Unfamiliar functions may have been defined, but for the sake of brevity, are ommitted here.
#If interested, these additional functions are defined in my GitHub (link at top&bottom of page)
def solve(edges, idx, coloring, r, n_clique, stats):
    stats['nodes'] += 1 #stores information about number of nodes being visited
    if idx == len(edges):
        return coloring
    u, v = edges[idx]
    edge = _edge(u, v) #just makes sure that the edge (v,u) is not written instead of (u,v) where lower index is first
    color_order = sorted(range(1, r + 1), key=lambda c: danger_score(u, v, c, coloring, n_clique))#order colors by ascending danger score 
    for color in color_order: #checking colors in order of danger
        if not is_forbidden(u, v, color, coloring, n_clique): #checking if color is forbidden
            coloring[edge] = color  #assigning a non-forbidden color                        
            result = solve(edges, idx + 1, coloring, r, n_clique, stats) #running solve recursively
            if result is not None: #checking if all colors were exhausted 
                return result                                
            del coloring[edge] #backtracking
            stats['backtracks'] += 1 #stores information about number of times we backtrack
    return None  #all colors exhausted

Now we have an algorithm with more intent and finesse. While the worst case for the run time complexity is essentially the same as our brute force approach, $O(2^{N^2/2})$ for a $2$-coloring, in practice we are pruning to skip sizeable subtrees of possibilities given the opportunity. Let’s return to $K_5$ with our new approach and see how we find a coloring with no triangles.

Isn’t that much more satisfying than searching through permutations? We knew going in that $K_5$ would find a coloring. Let’s watch our algorithm struggle to find the impossible with $K_6$.

Brute force generated $16,384$ possible colorings for $K_6$ after eliminating for symetry, where as this algorithm only visits $324$ (not including the uncolored graph) to determine impossibility. This is because everytime we need to back trace we are eliminating several colorings which would have failed without having to actually check each one. All possible colorings of the grey/uncolored edges above in a backtrace step are determined as ineligible at once.

I’ve mentioned that we have yet to discover an algorithm which could give us a solution for larger Ramsey Numbers. What’s interesting is we can find a range which for where the Ramsey Numbers exist. We know that $R(n,t)\leq\dbinom{n+t-2}{n-1}$. For all my fellow combinatorics nerds out there, take a moment to contemplate this bound. In some cases, we have found ways to narrow the boundaries significantly. For example, we know that for a $2$-coloring that $43\leq R(5,5)\leq 46$. To guarantee finding a monochromatic clique of size $5$ in a $2$-coloring of a complete graph, we know that the minimum size of $N$ for $K_N$ is somewhere between $43$ and $46$, but we don’t know exactly where. Isn’t that bewildering? You might be asking, we really can’t narrow it down any further? Well… no. First, just take a look at a $2$-coloring sample of $K_{43}$ and $K_{46}$.

I just generated these at random to illustrate the point that there are a significant number of edges and the possible combinations of these edges grows significantly with every additional vertex. $K_{43}$ has $\binom{43}{2} = 903$ edges, where $K_{46}$ has $\binom{46}{2}=1035$. This really highlights the power of putting concepts in the abstract, proving possibilities must be true when we aren’t currently capable of locating with precision. Such practice is fairly common in theoretical mathematics, and something many find frusterating. If this is you, annoyed with Ramsey for telling us something exists without giving us a clear map to precisely calculate the number, I’d ask you to take a step back and reflect for a moment. Consider with me the philisophical implications of these theorems, particularly Infinite Ramsey.

Why am I fascinated?

A graph, we’ve seen, can be used to represent a set of relationships between… well, any number of things. It is an abstraction tool for understanding the larger network of relationships (and one I happen to be partial to). Ramsey’s theorems essentially say patterns are inevitable at some point, unavoidable even in the extremes. Relational systems within each of these networks guarantee some patterns to emerge. If it’s not obvious already, this is a quietly radical idea. It is not the assertion that patterns tend to appear, or that they are likely in favorable conditions; It is the assertion that they must. No matter how adversarially a system is constructed, no matter how deliberate one might try to engineer chaotic randomness, sufficiently large systems collapse into order. This resonates beyond mathematics. In history, the emergence of analogous institutions across civilizations (writing systems, legal codes, cosmological myths) suggests something Ramsy-esque at work: when human networks grow large enough, and complex enough, certain structural patterns become overdetermined by the relational logic of the system itself, not by conscious design or cultural diffusion. Although, I must admit that some things are historically proven to be a result of, say, cultural diffusion (colonization, renaissance, technological advancement, etc.). It’s a bit murky here so lets head for clearer waters.

In the philosophy of the mind, one might wonder whether something similar underlies the convergence of conceptual categories across languages and cultures. Cognitive networks, whatever their surface diversity, may be large enough to guarantee the emergence of certain shared structures. Not because minds are identical, but because the relational geometry of thought, at scale, admits only so many escape routes. In the composition of music, we have categorically organized sounds into notes, chords, rhythms, and harmonies. Certain sequences through out a song reflect the patterns of a genre, and the familiar structure of a graph in one genre may have stark contrast to those in others. In evolution there are relations between species, the developmental jump from one to the next. In astronomy, in linguistics, in medicine, in geopolitics. Ramsey is inevitable, pattern is the tax that complexity pays to scale.

What Ramsey theory offers is not merely a collection of combinatorial results, it is a kind of mathematical proof of an ancient intuition: the universe has a bias toward pattern. Forgive me Aristotle, this is not a metaphysical claim but a rigorous one. Randomness and freedom of construction are real, but they are bounded. The integers themselves, arranged only by their differences and relationships, cannot sustain infinite disorder.

There is something almost humbling in this. The open question of $R(5,5)$, pinned somewhere in the narrow corridor between $43$ and $46$, resisting resolution for decades… It reminds us that while some inevitability is guaranteed, its precise threshold remains stubbornly elusive. Ramsey theory does not hand us order; it proves order was always already there, waiting. The task of finding it remains, resolutely, our own.