Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 68 ยท Counting

Ramsey Theory and Pigeonhole Extensions

Learn Ramsey theory: why any group of six contains three mutual friends or strangers, how R(3,3) = 6 is proved, and verify it by brute force in Python.

Among any six people at a party, there are always three who all know each other or three who are all strangers. It does not matter who the people are. The statement sounds like a puzzle, but it is the simplest case of Ramsey theory, whose slogan is: complete disorder is impossible. Every large enough structure contains a small, perfectly ordered piece.

Ramsey theory extends the pigeonhole principle. Pigeonhole says: with enough objects and few enough boxes, some box holds many objects. Ramsey says the same about relationships between pairs, not just objects. This lesson proves the six-person result, brute-forces it in Python, and shows how the general numbers grow.

Coloring edges of a complete graph

Model the party as the complete graph K_n on n vertices (see Graph Basics): one vertex per person, one edge between every pair. Color each edge red if the two people know each other and blue if they are strangers. A monochromatic triangle is three vertices whose three edges all share a color: three mutual friends or three mutual strangers.

The Ramsey number R(s, t) is the smallest n such that every red/blue coloring of K_n contains either a red K_s or a blue K_t. The party puzzle claims R(3, 3) = 6.

The proof that six is enough

Pick one person, call her A. She has 5 relationships with the others, each red or blue. By the pigeonhole principle, at least 3 of those 5 edges share a color; say red (the blue case is symmetric). Call the three people B, C, D. Now look at the edges among B, C and D:

  • If any of BC, BD, CD is red, that edge together with A's red edges to its endpoints forms a red triangle.
  • If none is red, then BC, BD, CD are all blue, a blue triangle.

Either way a monochromatic triangle appears, so six people always suffice.

Five is not enough

For R(3, 3) = 6 we must also show that five is too few: a coloring of K_5 exists with no monochromatic triangle. Arrange five people around a pentagon, color the five sides red and the five diagonals blue. A red triangle would need three pentagon vertices pairwise adjacent along sides, which is impossible; a blue triangle would need three vertices pairwise non-adjacent, also impossible.

Why R(3,3) is exactly six

Six always works Pigeonhole gives three same-color edges at one vertex.
Five can escape A pentagon with a blue star has no mono triangle.
So R(3,3) = 6 The smallest size that forces the pattern.

Both halves are needed, a size that works and a smaller size that fails.

1 / 2
Python Brute force: K5 can escape, K6 cannot

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.

For K_5, 1024 colorings are checked and 12 of them avoid monochromatic triangles (all are pentagon-style colorings, relabelled). For K_6, all 32,768 colorings contain a monochromatic triangle, so the count is zero.

Bigger Ramsey numbers

Ramsey numbers explode in difficulty. Known values include R(3, 3) = 6, R(3, 4) = 9, R(3, 5) = 14, R(4, 4) = 18 and R(3, 9) = 36. Even R(5, 5) is only known to lie between 43 and 46. A general bound comes from the same argument as above:

R(s, t) โ‰ค R(s - 1, t) + R(s, t - 1)

which gives R(s, t) โ‰ค C(s + t - 2, s - 1). Pick a vertex, split its other edges by color, and recurse on the larger group, exactly as we did for six people.

Why is R(5, 5) hard? Checking whether a coloring exists means searching a space of 2^C(n,2) colorings, which is astronomically large for n near 45. Famous folklore says that if aliens demanded R(5, 5) we should marshal the world's computers, but if they demanded R(6, 6) we should try to destroy the aliens.

Other Ramsey-type results

  • Pigeonhole in disguise: among any n + 1 integers, two share a remainder when divided by n, so their difference is a multiple of n.
  • Schur's theorem: however you color the numbers 1..n with k colors, for n large enough there are a, b and a + b all of one color. For two colors the threshold is 5, as the program below shows.
  • Happy Ending problem: any 5 points in the plane with no three on a line contain 4 forming a convex quadrilateral.
  • van der Waerden: any 2-coloring of a long enough list of integers has a long arithmetic progression of one color.
Python Schur's theorem for two colors

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 count falls to zero at n = 5, so every red/blue coloring of 1..5 contains a + b = c with all three the same color (a and b may be equal). Four numbers can still escape.

Why it matters

Ramsey theory proves that unavoidable patterns exist in networks, in sequences of data and in orderings, and it tells algorithm designers that some structure must appear in large inputs. It also marks the limits of exhaustive search, since the exact Ramsey numbers are known for only a handful of cases.

Ramsey proofs are non-constructive in spirit: they show a pattern must exist without telling you where. Pigeonhole arguments in Counting Principles work the same way.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is R(3, 3)?

    Six vertices always force a monochromatic triangle, while five can be colored to avoid one.
  2. 2. Which principle supplies the first step of the proof that six people suffice?

    One vertex has five edges in two colors, so at least three have the same color.
  3. 3. Why does the pentagon coloring (red sides, blue diagonals) show R(3, 3) > 5?

    A coloring of K5 with no monochromatic triangle proves that five vertices do not force the pattern.
  4. 4. A complete graph K_n has how many edges?

    Each of the n vertices connects to n - 1 others, and each edge is counted twice.

Summary

  • Ramsey theory shows that complete disorder is impossible: large enough structures contain ordered pieces.
  • R(s, t) is the smallest n forcing a red K_s or blue K_t in every 2-coloring of K_n.
  • R(3, 3) = 6: pigeonhole proves six suffice, and the pentagon coloring shows five do not.
  • Bigger Ramsey numbers are hard; only a few are known exactly.
  • Schur's theorem, the Happy Ending problem and van der Waerden's theorem are further Ramsey-type results.

Continue with Probability Basics.