Ramsey Theory - The Party Problem

Intro

How many people must be at a party to guarantee that at least $m$ people all know each other or at least $n$ people all do not know each other? This is the Party Problem and is a fun result from the area of mathematics known as Ramsey Theory.

Triangles with two colours

Consider the case $m, n = 3$. We'll sketch a proof that the minimum required number of people to guarantee at least three people will all know each other or all do not know each other is six.

Transforming this problem to a graph we start with the complete graph $K_i$ with $i$ nodes and all possible edges between them. Each node represents a person at the party and we colour the edges either red or blue with red representing the two people at either end of the edge know each other and blue representing the two people at either end of the edge do not know each other. A clique of a graph $G$ is defined as a subgraph of $G$ that is also complete i.e. has all possible edges between its nodes. We are therefore looking for a red or a blue clique of size three ($K_3$), or in other words a red or a blue triangle.

Red triangle represents all three people know each other

Blue triangle represents all three people do not know each other

First, we show a counterexample that the party must have more than five people. Here is a red/blue colouring of $K_5$ which does not contain a red or blue triangle:

$K_5$ counterexample

Now we must show that for any red/blue colouring of $K_6$ there must always be a red triangle or a blue triangle. Consider a node of $K_6$ and the colours of its five edges to the other five nodes in the graph:

A node and its edge colours in $K_6$

By the pigeonhole principle there must be at least three edges with the same colour. Without loss of generality let us assume we are looking at node 1 and the edges to 2, 3 and 4 are red. If this is not the case we can relabel the nodes and reverse the role of red and blue to make this true. Now, consider the colours of the edges between nodes 2, 3 and 4:

Edges between 2, 3 and 4

We have two cases:

• If there is at least one red edge we complete a red triangle
• If there are no red edges then they must all be blue and we have a blue triangle

Therefore, the minimum number of people at a party to guarantee at least three people will all know each other or all do not know each other is six!

Ramsey's Theorem

More generally, Ramsey's Theorem states that for any positive integers $m, n$ there exists a minimum number $R(m, n)$ called a Ramsey number such that for any complete graph with $R(m, n)$ vertices will contain either a red clique of size $m$ or a blue clique of size $n$.

By the above, we've shown that $R(3, 3) = 6$.

You can find some other Ramsey numbers at Wolfram MathWorld for example for a larger party to guarantee at least four people will all know each other or all do not know each other you would need a minimum of $R(4, 4) = 18$ people.