La conjetura de Cereceda

Problema sin resolver en matemáticas

¿Pueden cada dos?${\displaystyle (d+2)}$-coloraciones de un${\displaystyle d}$¿Un grafo degenerado puede transformarse en otro mediante una cantidad cuadrática de pasos que cambian el color de un vértice a la vez?

Más problemas sin resolver en matemáticas

En el ámbito de la coloración de grafos , la conjetura de Cereceda plantea un problema sin resolver sobre la distancia entre pares de coloraciones de grafos dispersos . Establece que, para dos coloraciones diferentes de un grafo de degeneración d , ambas con un máximo de d + 2 colores, debería ser posible reconfigurar una coloración en la otra cambiando el color de un vértice a la vez, mediante un número de pasos que es cuadrático con respecto al tamaño del grafo. La conjetura recibe su nombre de Luis Cereceda, quien la formuló en su tesis doctoral de 2007.

La degeneración de un grafo no dirigido G es el número más pequeño d tal que cada subgrafo no vacío de G tiene al menos un vértice de grado como máximo d . Si se elimina repetidamente un vértice de grado mínimo de G hasta que no queden vértices, entonces el mayor de los grados de los vértices en el momento de su eliminación será exactamente d , y este método de eliminación repetida puede usarse para calcular la degeneración de cualquier grafo en tiempo lineal . El coloreado voraz de los vértices en orden inverso al de esta eliminación producirá automáticamente un coloreado con como máximo d + 1 colores, y para algunos grafos (como los grafos completos y los grafos de ciclos de longitud impar ) este número de colores es óptimo. ^{[ 1 ]}

Para coloraciones con d + 1 colores, puede que no sea posible pasar de una coloración a otra cambiando el color de un vértice a la vez. En particular, nunca es posible pasar entre 2-coloraciones de un bosque (los grafos de degeneración 1) o entre ( d + 1) -coloraciones de un grafo completo de esta manera; se dice que sus coloraciones están congeladas. ^{[ 2 ]} Los grafos cíclicos de longitud distinta de cuatro también tienen familias desconectadas de ( d + 1) -coloraciones. ^{[ 3 ]} Sin embargo, con un color adicional, usando coloraciones con d + 2 colores, todos los pares de coloraciones pueden conectarse entre sí mediante secuencias de movimientos de este tipo. De esto se deduce que un paseo aleatorio diseñado adecuadamente en el espacio de ( d + 2) -coloraciones, usando movimientos de este tipo, es mezclador. Esto significa que el paseo aleatorio eventualmente convergerá a la distribución uniforme discreta en estas coloraciones como su estado estacionario , en el que todas las coloraciones tienen la misma probabilidad de ser elegidas. Más precisamente, el paseo aleatorio procede eligiendo repetidamente un vértice uniformemente aleatorio y eligiendo uniformemente al azar entre todos los colores disponibles para ese vértice, incluido el color que ya tenía; este proceso se llama dinámica de Glauber . ^{[ 4 ]}

El hecho de que la dinámica de Glauber converja a la distribución uniforme en ( d + 2) -coloraciones plantea naturalmente la cuestión de cuán rápidamente converge. Es decir, ¿cuál es el tiempo de mezcla ? Una cota inferior para el tiempo de mezcla es el diámetro del espacio de coloraciones, el máximo (sobre pares de coloraciones) del número de pasos necesarios para cambiar una coloración del par en la otra. Si el diámetro es exponencialmente grande en el número n de vértices en el grafo, entonces la dinámica de Glauber en coloraciones ciertamente no es de mezcla rápida. Por otro lado, cuando el diámetro está acotado por una función polinómica de n , esto sugiere que el tiempo de mezcla también podría ser polinómico. En su tesis doctoral de 2007, Cereceda investigó este problema y encontró que (incluso para componentes conexas del espacio de colores) el diámetro puede ser exponencial para ( d + 1) -coloraciones de grafos d -degenerados. Por otro lado, demostró que el diámetro del espacio de color es como máximo cuadrático (o, en ^notación O grande , O ( n² ) ) para coloraciones que utilizan al menos 2d + 1 colores. Escribió que «queda por determinar» si el diámetro es polinómico para números de colores entre estos dos extremos, o si es «quizás incluso cuadrático». ^{[ 5 ]}

Aunque Cereceda planteó esta pregunta para un rango de colores y no la formuló como una conjetura, en 2018 una forma de esta pregunta se conoció como la conjetura de Cereceda. Esta hipótesis no probada es la posibilidad más optimista entre las preguntas planteadas por Cereceda: que para grafos con degeneración como máximo d , y para ( d + 2) -coloraciones de estos grafos, el diámetro del espacio de coloraciones es O ( n² ) . ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ]} De ser cierto, esto sería lo mejor posible, ya que el espacio de 3-coloraciones de un grafo de caminos ^tiene diámetro cuadrático. ^{[ 10 ]}

Aunque la conjetura de Cereceda permanece abierta incluso para la degeneración d = 2 , se sabe que para cualquier valor fijo de d, el diámetro del espacio de ( d + 2) -coloraciones es polinomial (con un polinomio diferente para distintos valores de d ). Más precisamente, el diámetro es O ( n ^{d + 1} ) . Cuando el número de colores es al menos (3 d + 3)/2 , el diámetro es cuadrático. ^{[ 7 ]}

Una cuestión relacionada se refiere a la posibilidad de que, para números de colores mayores que d + 2 , el diámetro del espacio de coloraciones pueda disminuir de cuadrático a lineal. ^{[ 7 ]} Bousquet y Bartier (2019) sugieren que esto podría ser cierto siempre que el número de colores sea al menos d + 3. ^{[ 9 ]}

La dinámica de Glauber no es la única forma de cambiar coloraciones de grafos entre sí. Las alternativas incluyen la dinámica de Kempe, en la que se encuentran e intercambian repetidamente los colores de las cadenas de Kempe , ^{[ 8 ]} y la dinámica del "baño térmico", en la que se eligen pares de vértices adyacentes y una recoloración válida de ese par. Ambos tipos de movimientos incluyen los movimientos de Glauber de un vértice como un caso especial, ya que cambiar el color de un vértice es lo mismo que intercambiar los colores en una cadena de Kempe que solo incluye ese vértice. Estos movimientos pueden tener propiedades de mezcla más fuertes y un diámetro menor del espacio de coloraciones. Por ejemplo, tanto la dinámica de Kempe como la dinámica del baño térmico se mezclan rápidamente en coloraciones de 3 colores de grafos cíclicos, mientras que la dinámica de Glauber ni siquiera está conectada cuando la longitud del ciclo no es cuatro.