teorema de ramsey
En combinatoria , el teorema de Ramsey , en una de sus formas de teoría de grafos , establece que se encontrarán camarillas monocromáticas en cualquier etiquetado de bordes (con colores) de un gráfico completo suficientemente grande . Para demostrar el teorema de dos colores (digamos, azul y rojo), sean r y s dos enteros positivos cualesquiera . [1] El teorema de Ramsey establece que existe un entero mínimo positivo R ( r , s ) para el cual cada coloración de borde azul-rojo del gráfico completo en R( r , s ) vértices contiene una camarilla azul en r vértices o una camarilla roja en s vértices. (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 demostrada por Frank 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 sólo dos. Más precisamente, el teorema establece que para cualquier número dado de colores, c , y cualquier número entero dado n 1 ,…, n c , hay un número, R ( n 1 ,…, n c ) , tal que si las aristas de un gráfico completo de orden R ( n 1 , …, n c ) está coloreado con c colores diferentes, entonces, para alguna i entre 1 y c , debe contener un subgrafo completode orden n i cuyas aristas son todas de color i . El caso especial anterior tiene c = 2 (y n 1 = r y n 2 = s ).
Supongamos que los bordes de un gráfico completo en 6 vértices están coloreados en rojo y azul. Elija un vértice, v . Hay 5 aristas incidentes en v y por lo tanto (según el principio de casillero ) al menos 3 de ellas deben ser del mismo color. Sin pérdida de generalidad, podemos asumir que al menos 3 de estos bordes, que conectan el vértice, v , con los vértices, r , s y t , son azules. (Si no, intercambie rojo y azul en lo que sigue). Si alguno de los bordes, ( rs ) , ( rt ) , ( st ), 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 coloración, 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 mediante doble conteo . Dice lo siguiente: Cuente el número de triples ordenados de vértices, x , y , z , de modo que la arista ( xy ) sea roja y la arista ( yz ) sea azul. En primer lugar, cualquier vértice dado 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 del 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 = 36tales triples. En segundo lugar, para cualquier triángulo no monocromático ( xyz ) , existen precisamente dos de esos triples. Por tanto, hay como máximo 18 triángulos no monocromáticos. Por tanto, al menos 2 de los 20 triángulos del K 6 son monocromáticos.
Por el contrario, es posible pintar un K 5 con 2 colores sin crear ningún K 3 monocromático , lo que demuestra que R (3, 3) > 5 . El color único [a] se muestra a la derecha. Por tanto R (3, 3) = 6 .
