About: Teorema de Ramsey

En combinatoria el teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo de un grafo completo suficientemente grande, se hallarán subgrafos completos monocromáticos. Para dos colores, el teorema enuncia que para cualquier par de enteros positivos (r,s), existe al menos un entero positivo R(r,s) como aquel para cualquier grafo completo en R(r,s) vértices, cuyas aristas (o ramas) están coloreados de rojo o azul, existe un subgrafo completo de r vértices que es totalmente azul, o un subgrafo completo de s vértices que es totalmente rojo. R(r,s) representa un entero que depende conjuntamente de r y s. Se entiende que representa al entero más pequeño para el que el teorema aplica. A ese número se le llama número de Ramsey.