Utilizamos cookies propias y de terceros para mejorar nuestros servicios y facilitarte el uso de la web mediante el análisis de tus preferencias de navegación. También compartimos la información sobre el tráfico por nuestra web a los medios sociales y de publicidad con los que colaboramos. Si continúas navegando, consideramos que aceptas nuestra Política de cookies .

Cómo colorear un grafo infinito

¿Hasta dónde podemos generalizar el teorema de Ramsey?

CORTESÍA DEL AUTOR

Dibuje en un papel 4 puntos y conecte cada uno de ellos con todos los demás. Obtendrá un grafo de 4 vértices y 6 aristas. Si hace lo mismo con 6 nodos, el resultado será un grafo con 6 vértices y 15 aristas. En general, al conectar n nodos de tal manera que todos queden unidos con todos, generaremos un grafo Gn de n vértices y n(n – 1)/2 aristas.

Consideremos ahora el grafo G6 y procedamos a colorear de rojo o azul cada una de sus aristas. Si intenta hacerlo en casa, le aseguro que encontrará al menos un triángulo monocromático: un conjunto de tres vértices tales que todas las aristas que los conectan están coloreadas de un mismo color. No importa cuánto desorden tratemos de imponer al pintar las aristas de G6 con dos colores: siempre encontraremos un mínimo de armonía; en este caso, un triángulo monocromático.

Si tomamos G18 y repetimos la operación, no solo hallaremos un triángulo monocromático, sino un subgrafo monocromático de cuatro vértices.

Artículos relacionados

Puedes obtener el artículo en...

¿Tienes acceso?

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.