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.

El teorema de Ramsey es fundacional en combinatoria. La primera versión de estos resultados fueron probados por F. P. Ramsey. Esto inició la teoría combinatoria, ahora llamada teoría de Ramsey, que busca regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares.

Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solamente dos. Más precisamente, el teorema enuncia que por cualquier número dado de colores «c», y cualquier entero n1,...,nc, existe un número, R(n1, ..., nc), que si las aristas de un grafo completo de orden R(n1, ...,nc) se colorea con c colores diferentes, entonces para algún i entre 1 y c, debe contener un subgrafo completo de orden ni cuyas aristas son de color i. El caso especial de arriba donde c = 2 (y n1 = r y n2 = s).

Otra generalización se obtiene al considerar grafos que no sean completos. Son conocidos todos los valores de R(G1,G2) si G1 y G2 tienen a lo más 5 vértices salvo cuando G1 ó G2 es el grafo completo de 5 vértices y el otro es o bien el grafo completo de 5 vértices o bien el grafo completo de 5 vértices menos una arista.

Ejemplo: R(3,3)=6
2 colores en K5 con K3 no monocromático.

En el siguiente ejemplo, la fórmula R(3,3) provee una solución a la pregunta sobre el número mínimo de vértices que debe contener un grafo para asegurar que

  1. al menos tres vértices del grafo están conectados o,
  2. al menos tres vértices están desconectados.

Nótese que debido a la naturaleza simétrica del problema, R(r,s) produce la misma solución que R(s,r). Esto es aún más evidente en el ejemplo R(3,3) porque los valores de r y s son los mismos.

Supongamos que las aristas de un grafo completo de 6 vértices están coloreadas en rojo y verde. Al elegir un vértice v, vemos que hay 5 aristas incidiendo en él, y así, por el principio del palomar, al menos 3 de ellos deben ser del mismo color. Sin pérdida de generalidad podemos asumir que al menos 3 de estas aristas, que conectan con los vértices r, s y t son azules (si no lo son, intercámbiese azul con rojo en lo que sigue). Si alguno de las aristas (r, s), (r, t) o (s, t) es también azul, entonces tenemos un triángulo enteramente azul. Sino, entonces las tres aristas son rojas, y tenemos un triángulo enteramente rojo. Como este argumento funciona para cualquier esquema de color, cualquier K6 contiene un K3 monocromático, y entonces R(3,3) ≤ 6. La versión popular de esta demostración se conoce como teorema de la amistad.

Referencias

    Bibliografía

    Enlaces externos
    Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.