Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 36 Β· Pigeonhole and Ramsey

Ramsey Theory

Meet Ramsey theory: prove R(3,3)=6 by exhaustive search over edge colorings, compute Schur numbers by backtracking, and see why complete disorder is impossible.

Ramsey theory says that complete disorder is impossible: in any large enough structure, some small orderly substructure must appear. It generalizes the pigeonhole principle from "two in a box" to "a whole orderly pattern in a coloring".

The party problem: R(3,3) = 6

Among any 6 people, there are 3 who all know each other or 3 who are all strangers.

Model people as vertices of the complete graph K_6, and color each edge red (know) or blue (stranger). The claim: every coloring contains a monochromatic triangle.

Proof. Take one vertex v. It has 5 edges, so by pigeonhole at least 3 have the same color, say red, to a, b, c. If any of ab, bc, ac is red, it forms a red triangle with v. Otherwise all three are blue and abc is a blue triangle.

Five people are not enough: color the pentagon's sides red and its diagonals blue; neither color contains a triangle. So the smallest such number, the Ramsey number R(3,3), is exactly 6.

The computer can confirm this by brute force. There are 2^(C(n,2)) colorings of K_n: 1,024 for n = 5 and 32,768 for n = 6.

Python Brute-force R(3,3)

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table reads: n = 3 has 3 edges and 6 triangle-free colorings, n = 4 has 18, n = 5 has 12 (these are the pentagon/pentagram colorings and their relabelings), and n = 6 has 0. The two printed lists show a valid coloring of K_5: each color class is a 5-cycle.

General Ramsey numbers

R(s, t) is the smallest n such that every red/blue coloring of K_n has a red K_s or a blue K_t. Ramsey's theorem says it always exists. Known values are tiny and hard-won: R(3,3)=6, R(3,4)=9, R(3,5)=14, R(4,4)=18; R(5,5) is known only to lie between 43 and 46. ErdΕ‘s's quip: if aliens demanded R(5,5) or they would destroy Earth, we should marshal all computers; for R(6,6) we should attack the aliens instead. The exhaustive search above is already infeasible for n around 10, since 2^45 colorings is too many.

A simple recursive bound is R(s, t) <= R(s-1, t) + R(s, t-1), which proves existence and gives R(s,t) <= binom(s+t-2, s-1).

Schur's theorem and sum-free colorings

Color the integers 1, 2, ..., n with k colors. A monochromatic Schur triple is x + y = z with all three the same color (x = y is allowed). Schur's theorem: for each k there is a number S(k) such that every k-coloring of {1..S(k)+1} contains a triple. The largest n that can be colored without one is S(k).

  • S(1) = 1: with one color, 1 + 1 = 2 already fails at 2.
  • S(2) = 4: color 1, 4 red and 2, 3 blue works; 5 is impossible.
  • S(3) = 13, S(4) = 44, S(5) = 160.

The code finds these by backtracking: assign colors to 1, 2, 3, ... in order and stop when no color can be used (it limits the number of colors introduced to break symmetry).

Python Compute Schur numbers by backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

S(1), S(2), S(3) = 1, 4, 13. The coloring of {1,2,3,4} printed is [0, 1, 1, 0], and colorable(5, 2) is None: no 2-coloring of 1..5 avoids a monochromatic x + y = z.

Schur's theorem was invented to prove that Fermat's equation x^n + y^n = z^n has solutions modulo every large enough prime. A modern landmark: Heule, Kullmann and Marek showed in 2016 that the Boolean Pythagorean triples problem (a^2 + b^2 = c^2) cannot be 2-colored beyond 7,824, with a 200-terabyte proof found by a SAT solver.

flowchart TD
    V["Pick one vertex v of K6"] --> E["5 edges, 2 colors"]
    E --> P["Pigeonhole: 3 edges same color, to a, b, c"]
    P --> Q{"Is any of ab, bc, ca the same color?"}
    Q -->|"yes"| T1["Monochromatic triangle with v"]
    Q -->|"no"| T2["abc is a triangle of the other color"]

The proof that R(3,3) <= 6.

Ramsey-type results all share one shape: "big enough means unavoidable pattern". Their numbers grow enormously (van der Waerden numbers, Graham's number), which is why exact values are so rare.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What does R(3,3) = 6 mean?

    6 is the smallest number of vertices forcing a monochromatic triangle.
  2. 2. In the proof for K6, why do at least 3 edges at one vertex share a color?

    ceil(5/2) = 3.
  3. 3. How many 2-colorings of K5 avoid a monochromatic triangle (from the brute-force output)?

    The enumeration printed 12 for n = 5: the pentagon/pentagram colorings.
  4. 4. What is the Schur number S(2)?

    1..4 can be 2-colored without x + y = z, but 1..5 cannot.

Summary

  • Ramsey theory: large structures force orderly substructures; R(3,3) = 6 via pigeonhole at one vertex.
  • Brute force confirms it: 12 good colorings of K_5, none of K_6.
  • Schur numbers S(1), S(2), S(3) = 1, 4, 13 come from backtracking over colorings of 1..n.
  • Exact Ramsey-type numbers are very hard; only a few are known.

Next: Burnside's Lemma