Recitation 27

In today’s recitation, we discussed several problems related to the pigeonhole principle. One of the results is usually referred as Ramsey theorem, which states that there are always 3 people in a group of 6 who all know each other or who all don’t know each other.

Note that we could state the theorem in terms of graph theoretic terminology as follows. Any 2-coloring of the edges of $K_6$ contains a monochromatic $K_3$, where $K_n$ stands for a complete graph with $n$ vertices, i.e., a graph with $n$ vertices in which every pair of distinct vertices is connected by a unique edge.

In general, the smallest natural number $m$ that guarantees the existence of a monochromatic $K_m$ for any 2-coloring of the edges of $K_n$ is denoted as $R(n,n)$.

Therefore, $R(3,3)=6$ as there is a 2-colring of $K_5$ that has no monochromatic triangle. It is also known that $R(4,4)=18$. However, the exact value of $R(5,5)$ is unknown, although it is known to lie between 43 and 49 (inclusive).

Lastly, an interesting quote from Joel Spencer.

Erdős 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.