The Probabilistic Method

A party problem

You are hosting a party with five guests. You hope for some level of familiarity, but also some level of strangeness between the guests — specifically, you hope that no three guests all simultaneously know each other beforehand, and no three are all mutual strangers.

Graphs and colorings

To make this problem more mathematical, we can represent it as a graph. Each of the five people is depicted as a node, and there is a line drawn between every pair. We color each edge red if the two people are friends, and blue if they are strangers. In the lingo, this is a 2-coloring of the complete graph $K_5$.

What we want to avoid is a monochromatic triangle: three vertices whose connecting edges all share the same color. A red triangle would mean three mutual friends; a blue triangle, three mutual strangers.

Building up: small cases

It's instructive to start with smaller examples. For simplicity, we can abstract away the names of the party-goers and label them with single letters.

If we only have three people at the party, it's not too difficult to construct the arrangement we want. We can color $A$--$B$ red, then $A$--$C$ red, and we're forced to color $B$--$C$ blue to avoid a red triangle. That gives us a valid configuration.

source

let soft = |col| lerp(WHITE, col, 0.24)

let cis = |n, i, radius| {
    let angle = -TAU * i / n + PI / 2
    return [radius * cos(angle), radius * sin(angle), 0]
}

let labels = ["A", "B", "C"]

let NameBadge = |pos, label, col| [
    center{pos} fill{soft(col)} stroke{col, 2.2} Circle(0.3),
    center{pos} color{BLACK} Text(label, 0.8)
]

let GuestRing = block {
    for (i in range(0, 3)) {
        for (j in range(i + 1, 3)) {
            . stroke{LIGHT_GRAY, 2.0} tag{[i, j]} Line(cis(3, i, 0.8), cis(3, j, 0.8))
        }
    }
    for (i in range(0, 3)) {
        . tag{i} z_index{2} NameBadge(cis(3, i, 0.8), labels[i], TEAL)
    }
}

let style = operator |target, reds, blues| {
    return
        stroke{RED, 3, |tag| tag in reds}
        stroke{BLUE, 3, |tag| tag in blues}
        target
}

mesh graph = style{reds: [], blues: []} GuestRing
mesh caption = center{1.5d} color{DARK_GRAY} Text("n = 3", 0.7)

slide "Start"
    play Fade(0.5)

slide "A-B red"
    graph.reds = [[0, 1]]
    play Trans(0.5)
    play Wait(0.3)

slide "A-C red"
    graph.reds .= [0, 2]
    play Trans(0.5)
    play Wait(0.3)

slide "B-C blue"
    graph.blues = [[1, 2]]
    caption = center{1.5d} color{TEAL} Text("Valid coloring!", 0.7)
    play Trans(0.5)
    play Wait(0.5)

Moving to four, we can partially reuse our construction from $n = 3$ and try to color the remaining edges. Coloring $B$--$D$ red and the other two new edges blue gives us another valid configuration.

source

let soft = |col| lerp(WHITE, col, 0.24)

let cis = |n, i, radius| {
    let angle = -TAU * i / n + PI / 2
    return [radius * cos(angle), radius * sin(angle), 0]
}

let labels = ["A", "B", "C", "D"]

let NameBadge = |pos, label, col| [
    center{pos} fill{soft(col)} stroke{col, 2.2} Circle(0.3),
    center{pos} color{BLACK} Text(label, 0.8)
]

let GuestRing = |n, radius| block {
    for (i in range(0, n)) {
        for (j in range(i + 1, n)) {
            . stroke{LIGHT_GRAY, 2.0} tag{[i, j]} Line(cis(n, i, radius), cis(n, j, radius))
        }
    }
    for (i in range(0, n)) {
        . tag{i} z_index{2} NameBadge(cis(n, i, radius), labels[i], TEAL)
    }
}

let style = operator |target, reds, blues| {
    return
        stroke{RED, 3, |tag| tag in reds}
        stroke{BLUE, 3, |tag| tag in blues}
        target
}

mesh graph = style{reds: [[0, 1], [0, 2]], blues: [[1, 2]]} GuestRing(n: 3, 0.8)
mesh caption = center{1.5d} color{DARK_GRAY} Text("n = 3 coloring", 0.7)

slide "From n=3"
    play Fade(0.5)

slide "Grow to n=4"
    caption = center{1.5d} color{DARK_GRAY} Text("n = 4: extending from n = 3", 0.7)
    graph.n = 4
    play TagTrans(0.7)
    play Wait(0.3)

slide "B-D red"
    graph.reds .= [1, 3]
    play Trans(0.5)
    play Wait(0.3)

slide "A-D, C-D blue"
    graph.blues .= [0, 3]
    graph.blues .= [2, 3]
    caption = center{1.5d} color{TEAL} Text("Valid coloring!", 0.7)
    play Trans(0.5)
    play Wait(0.5)

For five, extending from the previous case works, though the construction has a particularly nice form: arrange the five vertices in a regular pentagon, color the pentagon edges blue and the diagonals red. Every triangle now contains edges of both colors.

So the answer to the party question is yes — with five guests, a valid arrangement exists.

The wall at six

Can we keep going? Based on the past it might seem that there is an inductive argument — take a valid coloring on $n - 1$ vertices and extend it to $n$. But once we get to $n = 6$, no matter what you try, you can't avoid a monochromatic triangle.

source

let soft = |col| lerp(WHITE, col, 0.24)

let cis = |n, i, radius| {
    let angle = -TAU * i / n + PI / 2
    return [radius * cos(angle), radius * sin(angle), 0]
}

let labels = ["A","B","C","D","E","F","G","H"]

let NameBadge = |pos, label, col, collapsed| block {
    if (collapsed) {
        . center{pos} fill{soft(col)} stroke{col, 2.2} Circle(0.3)
    }
    if (collapsed == 1) {
        . center{pos} color{BLACK} Text(label[0], 0.8)
    }
    if (not collapsed) {
        . center{pos} fill{soft(col)} stroke{col, 2.2} Rect([0.78, 0.42])
        . center{pos} color{BLACK} Text(label, 0.6)
    }
}

let GuestRing = |n, radius, collapsed| block {
    for (i in range(0, n)) {
        for (j in range(i + 1, n)) {
            . stroke{LIGHT_GRAY, 2.0} tag{[i, j]} Line(cis(n, i, radius), cis(n, j, radius))
        }
    }
    for (i in range(0, n)) {
        . tag{i} z_index{2} NameBadge(cis(n, i, radius), labels[i], TEAL, collapsed)
    }
}

let edges = |n| block {
    for (i in range(0, n)) {
        for (j in range(i + 1, n)) {
            . [i, j]
        }
    }
}

let style = operator |target, reds, blues, highlight=[]| {
    let base =
        stroke{RED, 3, |tag| tag in reds}
        stroke{BLUE, 3, |tag| tag in blues}
        target
    if (highlight != []) {
        return fade{0.2, |tag| not all(map(tag, |t| t in highlight))} base
    }
    return base
}

let ColorExpose = |&target, reds, duration=1| anim {
    target.highlight = []
    target.reds = reds
    target.blues = filter(edges(6), |e| not (e in reds))
    play Trans(1)

    var fail = []
    for (i in range(0, 6)) {
        for (j in range(i + 1, 6)) {
            let ij = [i, j] in reds
            for (k in range(j + 1, 6)) {
                let jk = [j, k] in reds
                let ik = [i, k] in reds
                let sum = ij + jk + ik
                if (sum in [0, 3]) {
                    fail = [i, j, k]
                }
            }
        }
    }
    target.highlight = fail
    play Trans(1)

    play Wait(duration)
}

slide "Wall"
    let rows = 3
    let cols = 5
    let tries = 3
    var anims = []
    for (r in sample(-1.5, 1.5, rows)) {
        for (c in sample(-3, 3, cols)) {
            mesh sub =
                style{reds: [], blues: [], highlight: []}
                center{[c, r, 0]}
                scale{0.5}
                GuestRing(n: 6, 1.0, 2)

            var reds = []
            var durs = []
            for (t in range(0, tries)) {
                var curr = []
                for (i in range(0, 6)) {
                    for (j in range(i + 1, 6)) {
                        if (random() > 0.5) {
                            curr .= [i, j]
                        }
                    }
                }
                reds .= curr
                durs .= 2
            }
            anims .= anim {
                play Fade()
                for ([red, dur] in zip(reds, durs)) {
                    play ColorExpose(&sub, red, dur)
                }
                sub = []
                play Fade()
            }
        }
    }
    play anims

Why six always fails

So let's see why with $n = 6$, you'll always reach a monochromatic triangle. Suppose for sake of contradiction that some 2-coloring of $K_6$ has no monochromatic triangle. Look at the five edges adjacent to vertex $F$. Some of these will be red and the others blue, but since five is odd, there will be a strict majority color that occurs at least three times. Without loss of generality, say three of those edges are red, connecting $F$ to vertices $A$, $B$, and $C$.

Now focus on the edges among $A$, $B$, and $C$. If any of them is red, that edge together with its two endpoints and $F$ forms a red triangle. So all three edges among $A$, $B$, $C$ must be blue — but that's a blue triangle. Contradiction. $\square$

Loading runtime...

0.00s

source

let soft = |col| lerp(WHITE, col, 0.24)

let cis = |n, i, radius| {
    let angle = -TAU * i / n + PI / 2
    return [radius * cos(angle), radius * sin(angle), 0]
}

let labels = ["A","B","C","D","E","F"]

let NameBadge = |pos, label, col| [
    center{pos} fill{soft(col)} stroke{col, 2.2} Circle(0.25),
    center{pos} color{BLACK} Text(label, 0.7)
]

let all_edges = block {
    for (i in range(0, 6)) {
        for (j in range(i + 1, 6)) {
            . [i, j]
        }
    }
}

let GuestRing = block {
    for (i in range(0, 6)) {
        for (j in range(i + 1, 6)) {
            . stroke{LIGHT_GRAY, 2.0} tag{[i, j]} Line(cis(6, i, 1.0), cis(6, j, 1.0))
        }
    }
    for (i in range(0, 6)) {
        . tag{i} z_index{2} NameBadge(cis(6, i, 1.0), labels[i], TEAL)
    }
}

let style = operator |target, reds, blues, highlight=[]| {
    let base =
        stroke{RED, 3, |tag| tag in reds}
        stroke{BLUE, 3, |tag| tag in blues}
        target
    if (highlight != []) {
        return fade{0.2, |tag| not all(map(tag, |t| t in highlight))} base
    }
    return base
}

mesh graph = style{reds: [], blues: [], highlight: []} GuestRing

slide "K6"
    play Fade(1)
    play Wait(0.5)

slide "Red from F"
    graph.reds = [[0, 5], [1, 5], [2, 5]]
    graph.blues = [[3, 5], [4, 5]]
    play Trans(1)
    play Wait(0.5)
    graph.highlight = [0, 1, 2, 5]
    play Trans(0.5)
    play Wait(0.5)

slide "If A-B red"
    graph.reds .= [0, 1]
    play Trans(0.5)
    graph.highlight = [0, 1, 5]
    play Trans(0.5)
    play Wait(1)

slide "So all blue"
    graph.reds = [[0, 5], [1, 5], [2, 5]]
    graph.highlight = [0, 1, 2, 5]
    play Trans(0.5)
    graph.blues = [[3, 5], [4, 5], [0, 1], [1, 2], [0, 2]]
    play Trans(0.5)
    graph.highlight = [0, 1, 2]
    play Trans(0.5)
    play Wait(1)

Ramsey numbers

What we just showed is that $R(3, 3) = 6$, where the Ramsey number $R(s, t)$ is the smallest $n$ such that every 2-coloring of $K_n$ must contain either a red clique of size $s$ or a blue clique of size $t$. The five-vertex pentagon coloring proves $R(3,3) > 5$, and the argument above proves $R(3,3) \le 6$.

$$ R(3, 3) = 6 $$

These numbers are incredibly hard to compute due to the exponential number of colorings of graphs. Even $R(5, 5)$ is unknown — the best we know is that it lies somewhere between 43 and 48.

A brief history

The problem of Ramsey numbers has an interesting history. Note that a priori, they aren't even well-defined — why should a finite minimum always exist?

In 1930, Frank Ramsey proved that such a minimum always exists for any $s$ and $t$. A few years later, Erdos and Szekeres gave a constructive approach that placed an explicit upper bound:

R(s, t) \le \binom{s + t - 2}{s - 1}

For a while progress somewhat slowed, as researchers tried increasingly clever constructions to push the lower bounds higher. Then in 1947, Erdos blew everybody's socks off with an innovative approach — the actual proof was merely half a page, yet it introduced a fundamentally new lower bound.

The probabilistic method

The core idea behind Erdos' method is probabilistic instead of constructive. We literally start with a completely random coloring and ask: what is the probability that this coloring contains one or more monochromatic cliques of size $k$?

Computing this probability exactly is difficult, since the monochromaticity of two different cliques is not independent when they share edges. However, we can use the union bound, which says that the probability of a union of events is at most the sum of the individual probabilities.

There are $\binom{n}{k}$ possible $k$-cliques. Since we're choosing the color of each edge uniformly and independently, the probability any particular clique is monochromatic is $2^{1 - \binom{k}{2}}$ (the factor of 2 accounting for the two possible monochromatic colors). So:

P(\text{some monochromatic } k\text{-clique exists}) \le \binom{n}{k} \cdot 2^{1 - \binom{k}{2}}

The lower bound

This gives us a useful bound. If we fix $k$ and choose $n$ so that the expression above is less than 1, then the probability of a random coloring having a monochromatic $k$-clique is less than 1 — which means there must exist at least one coloring with no monochromatic $k$-clique, and therefore $R(k, k) > n$.

Using the estimate $\binom{n}{k} \le \frac{n^k}{k!}$ and simplifying, this holds whenever $n < 2^{k/2}$ (for large enough $k$). Therefore:

\boxed{R(k, k) \ge 2^{k/2}}

Hay in a haystack

It's hard to overstate how remarkable this result is. A completely random method with no intelligence at all provides a better lower bound than elegant, thought-out constructions. It's as if we are unable to find hay in a haystack.

The probabilistic method has since become one of the most powerful techniques in combinatorics, proving the existence of objects that no one knows how to construct explicitly.

And to illustrate just how challenging the problem remains despite its simple statement, Joel Spencer recounts the following anecdote: "Erdos asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of $R(5, 5)$ or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for $R(6, 6)$. In that case, he believes, we should attempt to destroy the aliens."