Teorema de ramsey
En matemática combinatoria , el teorema de Ramsey , en una de sus formas teóricas de grafos , establece que uno encontrará camarillas monocromáticas en cualquier rótulo de borde (con colores) de un grafo completo suficientemente grande . Para demostrar el teorema de dos colores (por ejemplo, azul y rojo), dejar que r y s sea cualquiera de los dos positivos enteros . [1] El teorema de Ramsey establece que existe un número entero positivo mínimo R ( r , s ) para el cual cada color de borde azul-rojo del gráfico completo enLos vértices R ( r , s ) contienen una camarilla azul en losvértices r o una camarilla roja en los vértices s . (Aquí R ( r , s ) significa un número entero que depende tanto de r como de s ).
El teorema de Ramsey es un resultado fundamental en combinatoria. La primera versión de este resultado fue probada por FP Ramsey . Esto inició la teoría combinatoria ahora llamada teoría de Ramsey , que busca la regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares. En esta aplicación se trata de la existencia de subconjuntos monocromáticos , es decir, subconjuntos de aristas conectadas de un solo color.
Una extensión de este teorema se aplica a cualquier número finito de colores, en lugar de solo a dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c , y cualquier entero dado n 1 , ..., n c , hay un número, R ( n 1 , ..., n c ), tal que si los bordes de un gráfico completo de orden R ( n 1 , ..., n c ) están coloreados con c colores diferentes, entonces para algunos i entre 1 y c , debe contener un subgrafo completo de ordenn i cuyos bordes son todos de color i . El caso especial anterior tiene c = 2 (y n 1 = r y n 2 = s ).
Suponga que los bordes de un gráfico completo en 6 vértices están coloreados de rojo y azul. Elija un vértice, v . Hay 5 bordes incidentes av y por lo tanto (según el principio del casillero ) al menos 3 de ellos deben ser del mismo color. Sin pérdida de generalidad se puede suponer al menos 3 de estos bordes, que conecta el vértice, v , a los vértices, r , s y t , son de color azul. (Si no es así, intercambie rojo y azul en lo que sigue.) Si alguno de los bordes, ( r , s ), ( r , t ), ( s , t), también son azules, entonces tenemos un triángulo completamente azul. Si no, entonces esos tres bordes son todos rojos y tenemos un triángulo completamente rojo. Dado que este argumento funciona para cualquier color, cualquier K 6 contiene un K 3 monocromático y, por lo tanto, R (3, 3) ≤ 6. La versión popular de esto se llama teorema de amigos y extraños .
Una prueba alternativa funciona contando dos veces . Es como sigue: Cuente el número de triples ordenados de vértices, x , y , z , de manera que la arista, ( xy ), sea roja y la arista, ( yz ), sea azul. En primer lugar, cualquier vértice será el medio de 0 × 5 = 0 (todos los bordes del vértice son del mismo color), 1 × 4 = 4 (cuatro son del mismo color, uno es el otro color), o 2 × 3 = 6 (tres son del mismo color, dos son del otro color) tales triples. Por lo tanto, hay como máximo 6 × 6 = 36 triples de este tipo. En segundo lugar, para cualquier triángulo no monocromático ( xyz), existen precisamente dos de esos triples. Por lo tanto, hay como máximo 18 triángulos no monocromáticos. Por lo tanto, al menos 2 de los 20 triángulos del K 6 son monocromáticos.
A la inversa, es posible dos colores de un K 5 sin crear ningún K 3 monocromático , mostrando que R (3, 3)> 5. El color único [2] se muestra a la derecha. Por tanto, R (3, 3) = 6.
