Matemática: Una prueba gráfica del teorema de Ramsey

Una prueba visual simple de una idea poderosa

El teorema de Ramsey predice una sorprendente (y útil) consistencia en la organización de grafos. Aquí hay una simple prueba visual de cómo funciona.



Lucy Reading-Ikkanda / Quanta Magazine; Fuente: Jonathan Jedwab, Universidad Simon Fraser

Kevin Hartnett | Quanta Magazine


Un avance reciente en la geometría hace un uso intensivo del teorema de Ramsey, una idea importante en otra teoría del campo-gráfico. El teorema de Ramsey indica que en cualquier gráfico donde todos los puntos están conectados por líneas rojas o líneas azules, se garantiza que tiene un gran subconjunto del gráfico que es completamente uniforme, es decir, todo rojo o todo azul.

Equivalentemente, puedes ir por el otro lado: selecciona el tamaño que deseas que tu subconjunto uniforme sea. El teorema de Ramsey indica que en algún lugar hay un grafo en el que debe surgir un subconjunto de ese tamaño.

No es obvio por qué esto es cierto. ¿Por qué no puede haber un grafo en el que las líneas de diferentes colores queden completamente mezcladas entre sí?

Le hice esta pregunta a Jonathan Jedwab, matemático de la Universidad Simon Fraser en la Columbia Británica. Él respondió con este ejemplo, que proporciona una intuición gráfica de por qué el teorema es verdadero.

Tomemos un caso simple en el que usted está buscando un subconjunto de al menos tres líneas que son completamente uniformes. Un grafo hexagonal está garantizado para darle ese subconjunto. ¿Cómo?

Comience con seis puntos que representan a seis personas en una fiesta. Cualquier persona en la fiesta se conoce o no se conoce. Si se conocen, colorea la línea roja. Si no se conocen, colorea la línea entre ellos azul. Cada punto tendrá entonces cinco líneas que salen de él; Al menos tres de esas cinco líneas deben ser de color rojo o azul.

Una demostración del teorema de Ramsey significaría demostrar que no importa cómo se conecte a la gente, se garantiza que termina con un triángulo (un subconjunto uniforme con tres líneas) que es todo azul o todo rojo.



Pensemos en la Persona 1. Al menos tres de sus cinco líneas van a ser de color rojo o azul. Dado que, imagine que conoce a las personas en las posiciones 2, 4 y 5, y el color de las líneas de color rojo.



Ahora, piense en la Persona 2 y la Persona 5. Si se conocen, colorearemos el enlace en rojo y tendremos un triángulo de todo un color, que estamos tratando de evitar. Así que colorea ese enlace azul.



Luego piense en la relación entre la Persona 4 y la Persona 5. Una vez más, para evitar un triángulo rojo, tenemos que colorear ese enlace azul.



Por último, tenemos la relación entre la Persona 2 y la Persona 4. O bien se conocen o no lo hacen, haciendo que el enlace entre ellos sea rojo o azul. De cualquier manera, estamos obligados a crear un triángulo que es todo un color, y el teorema de Ramsey se confirma.



En los grafos más grandes - casos con un millón de personas, o miles de millones - el teorema de Ramsey garantiza que todos los puntos de un gran subconjunto del grafo estarán conectados con líneas del mismo color. Pero, ¿cuán vasto es "vasto"? Los matemáticos no están seguros. En particular, no conocen el tamaño mínimo que puede tener un grafo antes de que se garantice un subconjunto de un tamaño determinado (para todos los tamaños posibles). De esta manera, el teorema de Ramsey es como muchas herramientas que usamos todos los días - es útil, incluso si no entendemos todo acerca de cómo funciona.