El origen del teorema de los dos colores de Ramsey

El teorema lleva el nombre de Frank Plumpton Ramsey. Definición de los números de Ramsey Los números de Ramsey se describen de dos maneras en el lenguaje de la teoría de grafos: para una gráfica de todos los N vértices, un grupo de k vértices o un conjunto independiente de l vértices. El número natural más pequeño N con esta propiedad se llama número de Ramsey, denotado como R(k, l, en teoría de coloración, se describe de la siguiente manera: para cualquier coloración de dos lados (e1, e2) del gráfico completo Kn, De modo que Kn [e1] contiene un gráfico subcompleto de orden k, y Kn [e2] contiene un gráfico subcompleto de orden l. El mínimo n que satisface esta condición se llama número de Ramsey. (Nota: según la notación de la teoría de grafos, Ki representa una gráfica completa de orden i). Ramsey demostró que para números enteros positivos k y l dados, la respuesta R(k, l) es única y finita. El número de Ramsey también se puede extender a más de dos números: para cada arista de un gráfico completo Kn, se puede pintar con r colores, representados respectivamente como e1, e2, e3,...er, debe haber en Kn A gráfico subcompleto de orden l1 y color e1, o un gráfico subcompleto de orden l2 y color e2..., o un gráfico subcompleto de orden lr y color er. El número más pequeño n que satisface la condición se registra como R(l1, l2, l3,..., lr; r).

Actualmente hay muy pocos valores conocidos o límites superior e inferior del número de Ramsey. Paul Eldershot utilizó una vez una historia para describir la dificultad de encontrar el número de Ramsey: "Imagínate que el ejército alienígena aterriza. Tierra y exige el valor de R(5,5) de lo contrario destruirán la Tierra. En este caso deberíamos concentrar todas nuestras computadoras y matemáticos en tratar de encontrar este valor para R. (6,6), debemos intentar eliminarlo. los extraterrestres." Fórmulas obvias y que se explican por sí mismas: R(1,s)=1, R(2,s)=s, R(l1,l2,l3,...,lr;r)=R(l2,l1,l3, .. , lr; r) = R (l3, l1, l2, ... , lr; r) (cambiar el orden de li no cambiará el valor del número de Ramsey).

El valor o límites superior e inferior del número de Ramsey r, s 3 4 5 6 7 8 9 10 3 6 9 14 18 23 28 36 40-43 4 9 18 25 35 - 41 49 - 61 56 - 84 73 - 115 92- 149 5 14 25 43 - 49 58 - 87 80 - 143 101 - 216 125 - 316 143-442 6 18 35 - 41 58 - 87 102 - 165 113 - 2.2.2 87 102 - 165 113 - 298 7 - 4 95 169 -780 179-1171 7 23 49 - 61 80 - 143 113 - 298 205 - 540 216 - 1031 233 - 1713 289-2826 8 28 56 - 84 101 - 216 127 - 495 216 - 28 2 - 1 870 317 -3583 317 -6090 9 36 73 - 115 125 - 316 169 - 780 233 - 1713 317 - 3583 565 - 6588 580-12677 10 40-43 92 - 149 143 - 442 179 - 1171 289 - 2826 317 - 60 90 580-12677 798- 23556 R(3 ,3,3)=17

La prueba de que R(3,3) es igual a 6 demuestra: En la figura completa de K6, si cada borde está teñido de rojo o azul, entonces debe haber un triángulo rojo o un triángulo azul. Elija un punto final P que tenga 5 aristas conectadas a otros puntos finales. Según el principio del casillero, al menos 3 de las 5 aristas tienen el mismo color. Sin perder generalidad, deja que el color de estas 3 aristas sea rojo. En los 3 puntos finales de estas 3 aristas, excepto P, hay 3 aristas conectadas entre sí. Si cualquiera de los 3 lados es rojo, entonces los 2 lados conectados a P en los extremos de ese lado forman un triángulo rojo. Si alguno de los 3 lados no es rojo, entonces debe ser azul, formando así un triángulo azul. Y en K5, no necesariamente hay un triángulo rojo o un triángulo azul. Es suficiente siempre que la línea que conecta cada punto final con sus dos puntos finales adyacentes sea roja y la línea que lo conecta con los dos puntos finales restantes sea azul. Una versión popular de este teorema es el teorema de la amistad.