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.