Coloring problems for all ages

Take n points and join every pair with an edge in one of two colors, blue or red. You have just drawn a 2-coloring of the complete graph K_n . With five points, the colors can be chosen so that no triangle is monochromatic. In K₆ , however, a monochromatic triangle is unavoidable. Five edges meet at vertex A, and since only two colors are available, three of them—say [AB], [AC], and [AD]—must be the same color (blue, for example). If BCD is not monochromatic, at least one of its three sides must be blue and therefore forms a monochromatic triangle with A.

These entertaining little problems were studied in the late 1920s by the Briton Frank Plumpton Ramsey (1903–1930). The question can be generalized as follows: what is the smallest integer R(n) such that every 2-coloring of K_R(n) necessarily contains a monochromatic K_n subgraph?

R(3) = 6. In 1955, it was proved that R(4) = 18: every 2-coloring of K₁₈ contains a monochromatic complete subgraph of order 4, whereas this is not true for K₁₇.

is monochromatic. If we denote the eight possible edge lengths by ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_3\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_3$, the edges of lengths ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_4\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_4$ and ${\mathrm{\ell }}_3\backslash ell\_3$ are colored blue, and all the others red.

For the following values, only bounds are known: R(5) lies between 43 and 49, with recent research tending to confirm the lower bound. For R(10), the value lies between 798 and 23,556.