LAS REDES ALEATORIAS DEJAN DE SER COLOREABLES A UNA DENSIDAD FIJA
Tomemos un grafo —puntos unidos por enlaces— y una caja de colores. Una coloración propia con q colores asigna a cada punto uno de los q colores de modo que dos puntos enlazados nunca compartan el mismo. Con pocos enlaces, es fácil. Con muchos, se vuelve imposible.
Ahora construyamos el grafo al azar: n puntos, cada par enlazado de forma independiente con una pequeña probabilidad, de modo que un punto tiene d vecinos de media. A medida que d crece, el grafo aleatorio pasa de «casi seguramente coloreable con q colores» a «casi seguramente no». ¿Dónde se produce exactamente el cambio? Esa pregunta, para cualquier número fijo de colores q a partir de tres, es el tema de un nuevo artículo de Gaia Carenini, de la Universidad de Cambridge.
Un cambio que podría oscilar
En un artículo de 1999 que figura en la bibliografía, Achlioptas y Friedgut demostraron que la transición es abrupta: para cada tamaño n, existe un grado medio crítico d_q(n) tal que, un poco por debajo, el grafo es casi seguramente coloreable y, un poco por encima, casi seguramente no. La ventana en la que se produce el cambio se reduce a nada.
Pero eso dejaba un resquicio. Nada impedía que el propio valor crítico oscilara a medida que los grafos crecían: que se situara en un lugar para grafos de un tamaño, ligeramente en otro para grafos mayores, sin estabilizarse nunca. La conjetura de convergencia de Achlioptas–Friedgut afirma que esto no ocurre: para cada q, existe una única constante d_q, por debajo de la cual los grafos aleatorios son coloreables y por encima de la cual no lo son.
Lo que predijeron los físicos
La física estadística tenía una imagen de lo que ocurre. A medida que se añaden enlaces, las coloraciones válidas se agrupan en cúmulos (clusters): las coloraciones de un mismo cúmulo se parecen entre sí, mientras que dos cúmulos difieren en muchos puntos. Después, en una etapa llamada condensación, un puñado de grandes cúmulos reúne una parte sustancial de todas las coloraciones, y solo más tarde el conjunto de coloraciones queda vacío. Esa organización explica por qué los argumentos de conteo tienen dificultades cerca del umbral.
Para muchos colores, trabajos anteriores ya habían acotado el umbral en un intervalo estrecho: se sitúa entre aproximadamente 2q log q − log q − 2 log 2 y 2q log q − log q − 1, una brecha de anchura 2 log 2 − 1 a medida que q crece. Pero «estrecho» no es «fijo», y para números pequeños de colores, como tres, la pregunta seguía abierta.
Un problema gemelo, abordado primero
La coloración tiene un gemelo: la satisfacibilidad, el problema de elegir valores verdadero o falso para unas variables de modo que se cumplan todas las restricciones lógicas de una lista aleatoria. También allí se sabía que existía un umbral abrupto, sin prueba de que se estabilizara. En un informe de 2026 citado en el artículo, Carenini anunció una demostración de que sí lo hace, para toda longitud de las restricciones a partir de tres, mostrando que la ventana de transición es muy estrecha. El nuevo artículo adapta ese argumento a la coloración.
Pares congelados juntos
La demostración avanza mediante una cadena de reducciones. Al añadir enlaces aleatorios uno a uno, sea H el momento en que el grafo deja de ser coloreable. Si H varía poco de un grafo aleatorio a otro —dentro de una ventana de unos n/(log n)² enlaces—, entonces el umbral debe estabilizarse. Una desigualdad clásica convierte esto en una pregunta sobre el último grafo coloreable: de media, ¿cuántos enlaces aleatorios nuevos resiste?
Aquí entra la noción clave: los pares congelados. Dos puntos forman un par congelado cuando toda coloración válida les da el mismo color. Un enlace nuevo es fatal exactamente cuando une un par así. Un punto por sí solo no puede quedar congelado en un color concreto, ya que intercambiar los colores entre sí siempre da otra coloración válida; lo que queda forzado es una relación entre dos puntos. Carenini sigue cómo crecen estas clases congeladas a medida que se añaden enlaces, suprimiendo un enlace o un punto entero y observando las opciones que reaparecen. Las estimaciones muestran que el último grafo coloreable no puede resistir mucho tiempo, lo que estrecha la ventana lo suficiente para demostrar la conjetura.
Lo que sigue sin saberse
El teorema afirma que el umbral d_q existe para todo q ≥ 3. No dice dónde está: el artículo no da ningún valor, ni siquiera para tres colores. El artículo es una prepublicación de autoría única y no ha pasado una revisión por pares. Termina con una breve declaración según la cual ninguno de sus argumentos matemáticos fue generado por un gran modelo de lenguaje.
