Thresholds for colouring the random Borsuk graph

Los autores determinan los umbrales de coloración para el grafo de Borsuk aleatorio, demostrando que la transición de ser $k$-colorable a requerir más de $k$ colores ocurre cuando el grado promedio es constante para $2 \leq k \leq d$, y establecen la existencia de umbrales agudos para estos casos, incluyendo una expresión explícita para$k=2$ basada en la percolación de AB.

Lo esencial

Imagina que tienes una esfera gigante, como un planeta perfecto, y lanzas al azar miles de puntos sobre su superficie. Ahora, imagina que conectas dos puntos con una cuerda (una "arista") solo si están casi en lados opuestos del planeta. Es decir, si la distancia entre ellos es muy grande, casi como si uno estuviera en el Polo Norte y el otro en el Polo Sur.

A este dibujo de puntos y cuerdas lo llamamos Gráfico de Borsuk Aleatorio.

El gran misterio que resuelve este artículo es: ¿De cuántos colores necesitas pintar todos los puntos para que dos puntos conectados por una cuerda nunca tengan el mismo color? A esto se le llama el "número cromático".

Aquí está la explicación sencilla de lo que descubrieron los autores, usando analogías de la vida real:

1. El Juego de los Colores y la "Distancia de Enemistad"

Piensa en los puntos como personas en una fiesta.

• Si dos personas están muy lejos una de la otra (casi en lados opuestos de la habitación), se vuelven "enemigos" y se conectan con una cuerda.
• La regla es: Enemigos no pueden tener el mismo color de camisa.
• El parámetro $\alpha$ es como un "botón de sensibilidad". Si giras el botón para que la distancia requerida para ser enemigos sea muy pequeña, tendrás muchísimas cuerdas (muchos enemigos). Si lo giras al revés, tendrás pocas cuerdas.

2. El Descubrimiento Principal: El "Punto de Quiebre"

Antes de este trabajo, sabíamos que si la habitación estaba muy llena de cuerdas (muchos enemigos), necesitabas muchos colores (al menos $d+2$). Pero los autores descubrieron algo sorprendente: El cambio de color ocurre mucho antes de lo que pensábamos.

Imagina que estás llenando un vaso de agua (el vaso es tu esfera).

• Antes: Pensábamos que el vaso se desbordaba (necesitabas un color extra) solo cuando estaba casi lleno (cuando el número promedio de cuerdas por punto era muy alto, como el logaritmo de $n$).
• Ahora: Descubrieron que el vaso se desborda cuando solo tiene un poco de agua (cuando el número promedio de cuerdas es una constante pequeña).

La analogía del "Umbral":
Es como si estuvieras intentando cruzar un río.

• Si el río es muy estrecho (pocas cuerdas), puedes saltar de piedra en piedra con solo 2 colores (como un camino simple).
• Pero el artículo demuestra que, en cuanto el río alcanza un ancho específico y constante (no necesita ser enorme), de repente se vuelve imposible cruzar con solo 2 colores. Necesitas un tercer color. Y si el río crece un poco más, necesitas un cuarto, y así sucesivamente.

3. La Magia de la "Percolación" (El Efecto Dominó)

Para entender por qué de repente necesitas 3 colores, los autores usaron una idea llamada Percolación Continua AB.

Imagina que tienes dos tipos de partículas en el suelo: Rojas y Azules.

• Si una partícula Roja está cerca de una Azul, se conectan.
• Si hay muy pocas partículas, se quedan aisladas en pequeños grupos.
• Pero si llegas a una densidad crítica, de repente se forma una cinta gigante que conecta todo el suelo.

En el gráfico de Borsuk, cuando la "sensibilidad" ($\alpha$) alcanza un valor crítico, se forma un ciclo impar (un camino que vuelve a empezar después de un número impar de pasos).

• Analogía: Imagina que intentas pintar un camino de baldosas alternando Blanco y Negro. Si el camino es un círculo par (4 baldosas), funciona. Pero si el camino es un círculo impar (3 baldosas), te quedas atascado: la última baldosa necesita ser Negra, pero está conectada a la primera que es Blanca. ¡Choque! Necesitas un tercer color para romper el ciclo.

El artículo demuestra que, en el momento exacto en que la densidad de puntos alcanza cierto nivel, aparecen estos "círculos imposibles" (ciclos impares) y el número de colores salta de 2 a 3.

4. El Resultado Sorprendente: "Casi" Siempre

Para los casos más complejos (necesitar 4, 5 o más colores), los autores no pudieron probar que el cambio ocurre exactamente en el mismo momento para todos los tamaños de la fiesta ($n$).

• La analogía: Es como si dijéramos: "Para casi todas las fiestas del mundo, el momento en que necesitas un color extra es predecible. Solo en raras ocasiones, en fiestas muy específicas, el momento cambia un poco".
• A esto lo llaman un "Umbral Nítido para casi todos los $n$". Es una forma elegante de decir: "Es una regla casi perfecta, con muy pocas excepciones extrañas".

5. ¿Por qué es importante?

Este trabajo conecta dos mundos que parecían separados:

1. Geometría: Cómo se distribuyen los puntos en una esfera.
2. Teoría de Percolación: Cómo se conectan las cosas en un sistema aleatorio (como el agua filtrándose por la tierra o una enfermedad propagándose).

En resumen:
El artículo nos dice que en un mundo de puntos aleatorios conectados por "enemistad a distancia", el caos (necesidad de muchos colores) no llega cuando la fiesta está abarrotada, sino mucho antes, tan pronto como hay una conexión constante entre los vecinos. Y ese momento exacto está gobernado por leyes matemáticas profundas que conectan la forma de la esfera con la probabilidad de que se formen "nudos" imposibles de resolver con pocos colores.

¡Es como descubrir que el mundo se vuelve "colorido" mucho antes de lo que imaginábamos, solo por un pequeño cambio en la distancia entre vecinos!

Resumen técnico

1. Introducción y Planteamiento del Problema

El artículo estudia el número cromático ($\chi$) del grafo Borsuk aleatorio, denotado como $G(n, \alpha)$. Este grafo se construye de la siguiente manera:

• Se seleccionan $n$ puntos $X_1, \dots, X_n$ de forma independiente y uniformemente distribuida en la esfera $d$-dimensional $S^d$.
• Dos vértices $X_i$ y $X_j$ están conectados por una arista si y solo si su distancia geodésica es mayor que $\pi - \alpha$, es decir, $\text{dist}(X_i, X_j) > \pi - \alpha$.
• El parámetro $\alpha = \alpha(n)$ depende de $n$ y controla la densidad de las aristas.

Contexto previo:
El grafo Borsuk (no aleatorio) fue introducido por Erdős y Hajnal en 1967 como un ejemplo de grafo con un número cromático alto ($d+2$) pero sin ciclos impares cortos. Recientemente, Kahle y Martinez-Figueroa (2020) demostraron que para el grafo aleatorio, la transición de ser $(d+1)$-colorable a requerir $\ge d+2$ colores ocurre cuando el grado promedio es de orden logarítmico ($\ln n$).

Objetivo del trabajo:
Los autores buscan caracterizar los umbrales precisos para la colorabilidad $k$-colorable (donde $2 \le k \le d+1$) en el **régimen termodinámico**, es decir, cuando el grado promedio es constante (orden$O(1)$).

---

2. Metodología y Herramientas Principales

El paper emplea una combinación sofisticada de técnicas de geometría estocástica, teoría de percolación y análisis de funciones booleanas.

A. Proyección Estereográfica y Geometría

Para manejar la geometría de la esfera $S^d$, los autores utilizan la proyección estereográfica $\pi: S^d \setminus \{N\} \to \mathbb{R}^d$. Esto permite mapear el problema localmente a un espacio euclidiano $\mathbb{R}^d$, facilitando el análisis de distancias y la comparación con modelos de percolación continua.

• Se demuestra que, localmente, el grafo Borsuk aleatorio en el régimen termodinámico se comporta como un modelo de percolación AB continua en $\mathbb{R}^d$.

B. Modelo de Percolación AB Continua

Se introduce un modelo de percolación donde existen dos procesos de Poisson homogéneos independientes, $Z_A$ y $Z_B$, en $\mathbb{R}^d$ con intensidad $\lambda$. Se conectan los puntos de $Z_A$ con los de $Z_B$ si su distancia es $\le 1$.

• Existe un valor crítico de intensidad $\lambda_c$ tal que si $\lambda < \lambda_c$, todos los componentes conexos son finitos (subcrítico), y si $\lambda > \lambda_c$, existe un componente infinito (supercrítico).
• Este modelo es crucial para analizar la 2-colorabilidad (bipartitud), ya que la existencia de un ciclo impar en el grafo Borsuk se relaciona con la existencia de un componente infinito en este modelo de percolación.

C. Técnicas de "Sprinkling" y Umbrales Agudos

Para probar la existencia de ciclos impares en el régimen supercrítico, los autores adaptan la técnica de "sprinkling" (riego) de Grimmett y Marstrand, originalmente desarrollada para percolación en "slabs" (barras). Esto permite unir configuraciones locales para garantizar la existencia global de ciclos impares con alta probabilidad.

Además, para el caso general $k \ge 3$, utilizan un resultado de umbrales agudos para funciones booleanas (Proposición 7, basado en Müller [33]), que permite demostrar la existencia de umbrales agudos para propiedades monótonas en grafos aleatorios, incluso si la propiedad no es localmente trivial.

D. Construcción de Subgrafos (Teorema 1)

Para demostrar que el número cromático es alto ($\ge d+1$) con grado constante, construyen un subgrafo que imita un grafo Borsuk de dimensión $d-1$. Utilizan una función Lipschitz impar $h$ para "evitar" las zonas vacías (patches) de la esfera y mapear una esfera $S^{d-1}$ dentro de $S^d$ de manera que los puntos mapeados formen un grafo denso con propiedades topológicas específicas (usando el teorema de Lyusternik-Shnirelmann).

---

3. Resultados Principales

El artículo establece los siguientes teoremas clave sobre los umbrales de coloración:

Teorema 1: Umbral para $\chi \ge d+1$

Existe una constante $c = c(d) > 0$ tal que si $\alpha = c \cdot n^{-1/d}$, entonces:
$$\lim_{n \to \infty} P(\chi(G(n, \alpha)) > d) = 1$$
Esto significa que el grafo deja de ser $d$-colorable mucho antes de lo que se pensaba (cuando el grado promedio es constante, no logarítmico).

Teorema 2: Umbral Agudo para 2-colorabilidad ($k=2$)

Existe una constante $c_2 = c_2(d) > 0$ tal que el umbral para dejar de ser bipartito (2-colorable) es agudo y está dado por:
$$\alpha(n) \approx c_2 \cdot n^{-1/d}$$

• Si $\alpha \ge (c_2 + \varepsilon)n^{-1/d}$, el grafo no es 2-colorable (contiene ciclos impares) con probabilidad 1.
• Si $\alpha \le (c_2 - \varepsilon)n^{-1/d}$, el grafo es 2-colorable con probabilidad 1.
• Significado: La constante $c_2$ está directamente relacionada con la intensidad crítica $\lambda_c$ del modelo de percolación AB continua en $\mathbb{R}^d$.

Teorema 3: Umbral para 1-colorabilidad (Ausencia de aristas)

Se caracteriza el umbral para que el grafo tenga al menos una arista (es decir, dejar de ser 1-colorable). Este es un umbral "grueso" (coarse threshold) que depende de si $n^2 \alpha^d$ tiende a 0, a una constante o a infinito.

Teorema 4: Umbral Agudo "para casi todo $n$" ($3 \le k \le d+1$)

Para $k$ entre 3 y $d+1$, los autores no pueden probar un umbral agudo para todos los $n$, pero demuestran que existe un conjunto de índices $N \subseteq \mathbb{N}$ de densidad 1 tal que, para $n \in N$, la propiedad de tener $\chi > k$ tiene un umbral agudo de la forma $\alpha_k(n)$.

• Esto implica que, aunque podría haber "saltos" irregulares en la secuencia de umbrales para algunos $n$, para la gran mayoría de los casos, la transición es aguda.

---

4. Discusión y Conjeturas

Los autores proponen las siguientes conjeturas que, de probarse, cerrarían las preguntas abiertas:

• Conjetura 55: La propiedad de tener $\chi > k$ tiene un umbral agudo para todos los $n$ (no solo para un subconjunto de densidad 1), para todo $3 \le k \le d+1$.
• Conjetura 57: Existen constantes $c_2 < c_3 < \dots < c_d$ tales que el umbral para $k$-colorabilidad es exactamente $c_k \cdot n^{-1/d}$.
  • Esto respondería positivamente a una pregunta abierta de Kahle y Martinez-Figueroa sobre la existencia de secuencias $\alpha(n)$ donde el número cromático sea exactamente $k$ con alta probabilidad.
• Relación con Percolación: Se especula que las constantes $c_k$ para $k \ge 3$ podrían corresponder a intensidades críticas de eventos de percolación de "orden superior" en el modelo AB, aunque la caracterización exacta de estos eventos (más allá de la existencia de ciclos impares) sigue siendo un desafío.

---

5. Significado e Impacto

1. Refinamiento de Regímenes: El trabajo demuestra que la transición de colorabilidad en grafos Borsuk aleatorios ocurre en el régimen termodinámico (grado constante), mucho antes que la transición hacia el número cromático máximo ($d+2$) que ocurre en el régimen logarítmico.
2. Conexión con Percolación Continua: Establece un vínculo profundo y cuantitativo entre la coloración de grafos geométricos aleatorios en esferas y la teoría de percolación continua (modelo AB), proporcionando una constante explícita ($c_2$) basada en la física estadística.
3. Técnicas Nuevas: La adaptación de técnicas de percolación en "slabs" y el uso de proyecciones estereográficas para construir subgrafos con propiedades topológicas específicas ofrecen herramientas valiosas para el estudio de otros grafos geométricos aleatorios.
4. Resolución Parcial de Problemas Abiertos: Resuelve completamente el caso $k=2$ y ofrece una respuesta casi completa para $k \in \{3, \dots, d+1\}$, dejando como principal desafío la eliminación de la condición de "densidad uno" en el Teorema 4.

En resumen, el artículo avanza significativamente en la comprensión de la estructura combinatoria y topológica de los grafos Borsuk aleatorios, conectando la teoría de grafos aleatorios con la geometría de esferas y la percolación continua.