Ramsey problems for beginners: one move, four levels

Ramsey problems scare beginners because the statements sound like they need a big theorem. They do not. Almost every Ramsey problem you will meet before the IMO yields to the same three-step move, and the difficulty ladder is just that move applied with more colours, lopsided targets, or a disguise. Learn the move on the easiest problem, then climb.

How to recognise a Ramsey problem

The tell is a promise that order is unavoidable. "Among any six people…", "however the edges are coloured…", "no matter how the numbers are split into two groups…". The problem gives you a colouring you do not control and asks you to find a small, perfectly uniform piece inside it: three people who all know each other, a triangle all in one colour, three numbers in the same group with $x + y = z$.

Translate before you do anything else. Things become vertices, every pair becomes an edge, and the relationship or the group becomes the colour of that edge. Once the problem is a coloured complete graph, you know which move to make.

Level 1: the move, on six people

Among any six people, three all know each other or three are all strangers. Here is the move in three steps, and every later level is these three steps again.

1. Stand at one vertex. Pick any person $v$. They have five edges going out.
2. Pigeonhole the edges. Five edges in two colours means at least $\lceil 5/2 \rceil = 3$ of them share a colour. Call it red, and call the three people at the other ends the red neighbours.
3. Look inside the neighbourhood. Any red edge between two red neighbours closes a red triangle with $v$. If there is none, the three red neighbours are joined entirely in blue: a blue triangle.

Step 2 is the pigeonhole principle, and step 3 is where beginners stop too early. The point of collecting three same-coloured neighbours is that it leaves the colouring nowhere to hide: whatever it does inside that group, it loses.

Then check the number is sharp. With five people, $v$ has only four edges, which can split two and two, and the move fails. It is not just the proof that fails. Seat five people in a circle, make neighbours friends and everyone else strangers, and there are no three mutual friends and no three mutual strangers. So six is exactly the answer, not just an answer that works.

Level 2: three colours

The classic next step: seventeen people write to each other, each pair about one of three topics. Prove some three people all write to each other about the same topic.

Same move. Stand at one person: sixteen edges in three colours, so at least $\lceil 16/3 \rceil = 6$ share a topic. Look inside those six. If any two of them use that topic with each other, you have the triangle. If none do, those six people only use the other two topics among themselves, and that is exactly Level 1: six people, two colours, a triangle is forced.

That is the whole lesson of Level 2. The previous level becomes a step in this one. Ramsey proofs stack, and recognising the smaller problem inside the neighbourhood is the skill being tested.

Is seventeen sharp? With sixteen people the pigeonhole only gives $\lceil 15/3 \rceil = 5$ neighbours in one colour, which is not enough for the argument. And a colouring of sixteen people with no single-topic triangle does exist, though you would not find it by hand: it is built from arithmetic in a number system with exactly sixteen elements. In a contest you prove the bound and are rarely asked for that construction.

Level 3: lopsided targets

Now the targets differ. Show that however the edges among nine people are coloured red and blue, there is a red triangle or four people joined entirely in blue.

Start with the move and ten people, because it works first time there. A vertex has nine edges, so either at least four are red or at least six are blue.

• Four red neighbours. A red edge among them is a red triangle with $v$. With no red edge, the four are all blue to each other: a blue group of four.
• Six blue neighbours. Level 1 again: among six there is a red triangle (done) or a blue triangle, and that blue triangle plus $v$ is a blue group of four.

That proves ten is enough. Getting down to nine needs one more idea, and it is the one that separates a good solution from a complete one. Suppose nine people manage to avoid both. Then the two bullets above say no one can have four red edges or six blue ones. Each person has eight edges, so every single person has exactly three red and five blue. Now count red edge ends: $9 \times 3 = 27$. Every edge has two ends, so that total must be even. It is odd, so the colouring cannot exist.

That parity step is the handshake lemma doing Ramsey work, and it is the same counting that drives the extremal principle in graphs: squeeze every vertex to its limit, then count the edges two ways. With eight people, a colouring that avoids both does exist (number them round a circle and colour red the pairs that are one or four seats apart), so nine is exact.

Level 4: Ramsey in disguise

The hardest Ramsey problems at beginner level do not mention people or colours of edges at all. Here is the cleanest example. Split the numbers $1$ to $5$ into two groups however you like. Prove that one group contains numbers $x$, $y$, $z$ with $x + y = z$, where $x$ and $y$ may be the same number.

Draw six points labelled $0$ to $5$. Colour the edge between $i$ and $j$ with the group that contains $|i - j|$. By Level 1, some triangle $i < j < k$ is all one colour. Its three differences are $j - i$, $k - j$ and $k - i$, all in the same group, and

$$(j - i) + (k - j) = k - i.$$

That is your $x + y = z$. The proof is three lines because the work was already done six-people-deep. And the bound is sharp again: $\{1, 4\}$ and $\{2, 3\}$ split the numbers $1$ to $4$ with no such sum.

Disguised problems are where the recognition matters most. Whenever a problem colours numbers, points or pairs and asks for a uniform pattern, ask what the vertices would be and whether the pattern is a monochromatic triangle in some graph.

How to practise them in order

Do them in exactly this order, and do not move up until the previous level feels automatic.

1. Six people, two colours. Write the three-step move from memory, then prove five is not enough.
2. Seventeen people, three topics. The point is noticing Level 1 inside the neighbourhood.
3. Red triangle or blue four. Prove ten first, then get to nine with the parity count.
4. A disguised problem. Find the graph before you find the proof.

Once those are comfortable, try the counting version: every two-colouring of the edges between six points has at least two single-coloured triangles. It asks how many triangles, not whether one exists, and it is a good test of whether you can count instead of just find. The guide on extremal graph problems covers that kind of argument.

The pigeonhole page has the principle in full, and the problem archive holds the six-people problem with hints and expected time. For one new problem a day at three difficulty levels, no account needed, there is the daily problem.