Problemas de coloración para todas las edades

Considere n puntos y únalos todos entre sí mediante aristas de dos colores a elegir (azul o rojo). Acaba de dibujar una 2-coloración del grafo completo K_n . Con cinco puntos, es posible elegir los colores de modo que ningún triángulo sea de un solo color. En cambio, en K₆ , es inevitable que haya un triángulo monocromo. En efecto, del vértice A parten cinco aristas y, como solo hay dos colores posibles, tres de ellas —[AB], [AC] y [AD], por ejemplo— son del mismo color (supongamos que azul). Si BCD no es monocromo, al menos uno de sus tres lados es azul y forma, por tanto, un triángulo monocromo con A.

Estos pequeños y entretenidos problemas fueron estudiados a finales de la década de 1920 por el británico Frank Plumpton Ramsey (1903–1930). La cuestión se generaliza así: ¿cuál es el menor número natural R(n) tal que toda 2-coloración de K_R(n) contenga necesariamente un subgrafo K_n monocromo?

Se tiene R(3) = 6. En 1955 se estableció que R(4) = 18: en toda 2-coloración de K₁₈ existe un subgrafo completo monocromo de orden 4, pero no ocurre así con K₁₇.

es monocromo. Si denotamos con ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_3\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_3$ las ocho longitudes de arista posibles, se han coloreado de azul las aristas de longitud ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2\dots {\mathrm{\ell }}_4\backslash ell\_1,\backslash ell\_2\backslash ldots\backslash ell\_4$ y ${\mathrm{\ell }}_3\backslash ell\_3$, y de rojo las demás.

Para los siguientes valores, solo se conocen algunas cotas: R(5) está comprendido entre 43 y 49, y trabajos recientes tienden a confirmar la cota inferior. Para R(10), el valor está comprendido entre 798 y 23 556.