La conjetura de Steinberg es…¡falsa!

La teoría de grafos es una de las ramas de las matemáticas que más movimiento está teniendo en los últimos años, en lo que se refiere a investigación y a aplicaciones a problemas “reales”.

Dentro de la teoría de grafos, los problemas relacionados con coloración de grafos tienen gran interés dentro de los especialistas de esta rama.

Y dentro de los problemas de coloración de grafos, la conjetura de Steinberg ha sido uno de los problemas abiertos que más han interesado a los estudiosos en la materia.

Bien, pues (parece ser que) tenemos resultado para este problema: la conjetura de Steinberg es falsa. En lo que sigue, vamos a dar una idea sobre qué es eso de la coloración de grafos y hablaremos de esta interesante conjetura.

Aunque en Gaussianos ya hemos hablado en otra ocasiones sobre grafos, no está mal recordar algo sobre ellos. Un grafo es un conjunto V (distinto del vacío) de puntos, llamados vértices, y un conjunto de líneas A, llamadas aristas, cada una de las cuales une dos de sus vértices. Si dos vértices están unidos con al menos una arista, se dice que dichos vértices están conectados.

Un grafo plano es un grafo que puede dibujarse en un plano con la condición de que dos aristas cualesquiera no se cortan en ningún punto que no sea un vértice. En la siguiente imagen podéis ver un grafo plano y uno que no lo es (de hecho es el famoso grafo de Kuratowski K_{3,3}):

plano-noplano

Un ciclo en un grafo es una sucesión de vértices v_1, \ldots ,v_n, v_1 en la que cada vértice de la lista está conectado con el siguiente y donde no hay vértices repetidos (excepto el primero y el último). Vamos, lo que todos esperaríamos que fuera un ciclo. La longitud de un ciclo es el número de vértices distintos (equivalentemente, el número de aristas) que contiene. Un ciclo de longitud n se suele denominar n-ciclo. Aquí tenéis dos ciclos, uno de longitud 3 (el verde) y otro de longitud 5 (el rojo):

ciclos

Una coloración de un grafo es una asignación de etiquetas (colores) a los vértices de dicho grafo de manera que dos vértices conectados tengan distinto color. Si el número de etiquetas es pequeño, suelen usarse colores para etiquetar los vértices. Si este número es grande, suelen usarse números enteros positivos: 1,2, \ldots , m. Si en la coloración se usan k colores, se dice que tenemos una k-coloración. Aquí tenéis como ejemplo una 3-coloración del grafo anterior:

3coloracion

The Three Color Problem

Ya tenemos todo lo necesario para introducir el tema principal de esta entrada. La cuestión central de toda esta historia es el coloreado de mapas. El resultado más conocido en relación con esto, como muchos ya sabréis, es el famosísimo teorema de los cuatro colores, demostrado por Kenneth Appel y Wolfgang Haken en 1976.

La primera noticia que se tiene sobre la coloración de mapas con tres colores es un paper de Arthur Cayley de 1879. Ese mismo año, Alfred Kempe también lo trata en su trabajo sobre el teorema de los cuatro colores (que, por cierto, contenía una demostración incorrecta de este resultado); y, más adelante, Percy Heawood también habla de él en sendos trabajos que datan de 1890 y 1898, respectivamente.

Pero es en 1958 cuando el Three Color Problem pasa a tener entidad de problema propio gracias a Herbert Grötzsch, siendo Oystein Ore en 1967 quien lo elevó a los altares. Recomiendo el paper The state of the Three Color Problem [Annals of Discrete Mathematics, 55, 21 1-248 (1993)], de Richard Steinberg, a quienes estén interesados en más datos relacionados con la historia de este problema.

El Three Color Problem pregunta, básicamente, lo siguiente:

¿Bajo qué condiciones pueden ser coloreadas las regiones de un mapa plano con tres colores de manera que no haya dos regiones con frontera común que tengan asignado el mismo color?

Como cada región de un mapa puede interpretarse como un vértice y la frontera común de dos regiones puede asociarse con una arista, un problema de coloreado de mapas puede interpretarse como un problema de coloreado de grafos.

Y por ahí va la cosa, por coloreado de grafos. En 1976, el propio Richard Steinberg establece la conjetura que actualmente lleva su nombre:

Conjetura de Steinberg:

Todo grafo plano que no contenga ni 4-ciclos ni 5-ciclos es 3-coloreable.

Es decir, si un grafo no tiene ciclos de longitud 4 ni ciclos de longitud 5, entonces pueden colorearse sus vértices con 3 colores de manera que no haya vértices conectados que compartan color.

Hasta hace poco, había habido acercamientos a dicha conjetura. Posiblemente, el más interesante surgió a partir de una sugerencia del gran Paul Erdős. Erdős sugirió buscar si existía una constante k que cumpliera que todo grafo sin ciclos de longitud 4,5, \ldots , k era 3-coloreable. Borodin, Glebov, Raspaud y Salavatipour, mejorando resultados anteriores, demostraron en Planar graphs without cycles of length from 4 to 7 are 3-colorable [J. Combin. Theory Ser. B 93 (2005), 303–331] que k \le 7.

Y más o menos en este punto es en el que estábamos…hasta hace bien poquito (en julio de 2006, se publicaba una supuesta demostración de la veracidad de la conjetura de Steinberg que no fue aceptada como correcta). En abril de este año 2016, Vincent Cohen-Addad, Michael Hebdige, Daniel Král, Zhentao Li y Esteban Salgado ha demostrado que la conjetura de Steinberg es falsa. En su trabajo Steinberg’s Conjecture is False, construyen un contraejemplo para dicha conjetura. Es decir, construyen un grafo plano que no contiene ni 4-ciclos ni 5-ciclos y que no es 3-coloreable. Para ello, comienzan construyendo un grafo G_1 (arriba a la izquierda en la imagen) con ciertas propiedades; a partir de él construyen un segundo grafo G_2 (arriba a la derecha); y para finalizar construyen un grafo G (abajo) a partir de este último que cumple que no tiene ni 4-ciclos ni 5-ciclos y que además no es 3-coloreable:

En el paper que acabo de enlazar podéis ver la demostración de este hecho.


Bien, la conjetura de Steinberg es falsa, problema resuelto. Pero el Three Color Problem sigue abierto, todavía no sabemos si ese k cuya búsqueda sugirió Erdős es 7 ó 6. Estaremos atentos a futuras novedades.


Fuentes y enlaces relacionados:


Esta entrada participa en la Edición 7.5 del Carnaval de Matemáticas, cuyo anfitrión es el blog Series Divergentes.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

8 Comentarios

  1. No acabo de ver claro este último grafo… las aristas marcadas con puntitos son parte del grafo?? por que si es así (a, e, d, c, a) es un 4-ciclo, y (a, e, f, d, c, a) es un 5-ciclo… y si las aristas marcadas con puntitos NO son parte del grafo, (a, c, f, f’) de color 1, (b, e, e’) de color 2, y, (c’, d, d’) de color 3 seria una coloración del grafo a 3 colores.
    Y si no es ni una cosa ni la otra, que aristas si que son parte, y que aristas no?

    Vamos, que estoy un poquito perdido…

    PS: Me encanta este blog, gracias por el curro que le hechas 😉

    Publica una respuesta
    • Roger, gracias a ti por visitar Gaussianos :).

      Creo que tus dudas se despejarán sabiendo que los puntos en negro del último grafo son vértices del grafo G, por lo que (a, e, d, c, a) no es un 4-ciclo ni (a, e, f, d, c, a) es un 5-ciclo (hay vértices de por medio, por decirlo de alguna forma).

      Publica una respuesta
      • Hola Gaussito!: Pronta respuesta! Gracias.
        Puedes ver la imagen del enlace?. Me pregunto que donde cometo el error al colorear el mapa de la demostracion si solo utilizo 3 colores en la imagen del enlace.. Saludos. Gracias nuevamente.

        Publica una respuesta
        • Ahora lo entendí, perdona jejeje.

          En tu imagen, en los cuatro lugares donde pone G_2 está el grafo G_2 (el que ves arriba a la derecha en la imagen del artículo), el cual, a su vez, contiene tres veces al grafo G_1 (el de arriba a la izquierda en la imagen). Por tanto, esas zonas grises no están “vacías”, sino que representan a los grafos anteriores, por lo que ahí también hay aristas y vértices.

          Espero haberme explicado bien.

          Publica una respuesta
          • Ja! Gracias Gaussianos! Bien pequeño desliz el mío ja!. Claro Si dice G2, y en G2 dice G1, bueno, el resultado no me es tan obvio, por lo que le echare unos minutos a tratar de colorear con 3 c, el G1, pero bueno ya se que es vano ja. Gracias, excelente blog, Ok!! Saludos

Trackbacks/Pingbacks

  1. Resumen del Carnaval de matemáticas, edición 7.5 – Series divergentes - […] La conjetura de Steinberg es…¡falsa! […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *