Compactness and degeneracy conjectures en teoría extremal de grafos

Este resultado es, en realidad, doble: la IA habría refutado dos conjeturas distintas de teoría extremal de grafos:

La conjetura de compactness de Erdős–Simonovits.
Una conjetura de Erdős sobre grafos bipartitos $𝑟$ -degenerados.

La idea común es muy RMS:

Se creía que ciertas restricciones locales en grafos —prohibir una familia finita, o tener degeneración baja— imponían límites globales previsibles sobre el número de aristas. La IA construye contraejemplos donde esa intuición falla.

1. Primero: qué estudia la teoría extremal de grafos

La teoría extremal de grafos pregunta cosas como:

¿Cuántas aristas puede tener un grafo de $𝑛$ vértices si prohibimos que contenga cierto patrón?

Ese máximo se llama número extremal:

ex (𝑛, 𝐻)

y significa:

máximo número de aristas que puede tener un grafo de $𝑛$ vértices sin contener una copia de $𝐻$ .

Si en vez de prohibir un solo grafo $𝐻$ prohibimos toda una familia $𝐹$ , escribimos:

ex (𝑛, 𝐹)

El manuscrito de OpenAI define exactamente $ex (𝑛, 𝐹)$ como el máximo número de aristas de un grafo de $𝑛$ vértices que no contiene ningún miembro de $𝐹$ .

Ejemplo sencillo:

Si prohibes triángulos, el grafo más denso posible es básicamente bipartito completo.
Si prohibes ciclos cortos, la densidad máxima baja.
Si prohibes patrones más complejos, la pregunta se vuelve muy delicada.

2. Primer resultado: compactness conjecture

La conjetura de compactness de Erdős y Simonovits decía, de forma intuitiva:

Si prohibir una familia finita de grafos reduce mucho el número máximo de aristas, entonces debería haber al menos un grafo concreto dentro de la familia que ya explique esa reducción.

Es decir, si tienes una familia finita:

𝐹 = {𝐹_{1}, 𝐹_{2}, \dots, 𝐹_{𝑘}}

la esperanza era que:

ex (𝑛, 𝐹)

fuera comparable, salvo constantes, a:

ex (𝑛, 𝐹_{𝑖})

para algún miembro individual $𝐹_{𝑖}$ .

En lenguaje sencillo:

Prohibir varios patrones a la vez no debería ser mucho más potente que prohibir el patrón individual más restrictivo.

La forma corregida de la conjetura preguntaba si, para toda familia finita no vacía de grafos con ciclos, existía algún $𝐹 \in 𝐹$ y una constante $𝐶$ tal que $ex (𝑛, 𝐹) \leq 𝐶 ex (𝑛, 𝐹)$ para $𝑛$ grande. El manuscrito indica que la IA refuta esta versión incluso cuando todos los grafos de la familia son conectados y bipartitos.

3. Qué construye la IA contra compactness

La IA construye una familia finita $𝐹$ de grafos conectados, bipartitos y con ciclos, tal que:

ex (𝑛, 𝐹) = 𝑂 (𝑛^{4 / 3 - 1 / 48})

pero, para cada miembro individual $𝐹 \in 𝐹$ ,

ex (𝑛, 𝐹) = Ω (𝑛^{4 / 3})

Esto es brutal porque significa:

Cada prohibición individual permite grafos con unas $𝑛^{4 / 3}$ aristas, pero prohibir la familia completa baja el exponente a $4 / 3 - 1 / 48$ .

El abstract del capítulo lo formula así: existe una familia finita $𝐹$ de grafos bipartitos conectados, cada uno con un ciclo, para la que el número extremal conjunto baja a $𝑂 (𝑛^{4 / 3 - 1 / 48})$ , mientras que cada miembro individual mantiene $Ω (𝑛^{4 / 3})$ .

La separación es polinómica:

𝑛^{1 / 48}

No es solo una diferencia de constantes. Es una diferencia real de escala.

4. Intuición del contraejemplo de compactness

La construcción no dice simplemente: “meto muchos grafos prohibidos y ya está”.

La IA diseña una familia $𝐹$ con dos tipos de piezas:

$𝐶_{4}$ y $𝐶_{6}$ , ciclos cortos.
Ciertos grafos más elaborados construidos a partir de plantillas llamadas $𝐽$ y $𝐾$ , que vienen de subdividir grafos bipartitos completos y permitir ciertos cocientes admisibles. El manuscrito describe que la familia se compone de $𝐶_{4}$ , $𝐶_{6}$ y cocientes admisibles de dos plantillas basadas en subdivisiones de $𝐾_{3, 2}$ y $𝐾_{3, 3}$ .

La lógica es:

Una parte de la familia impide que haya demasiadas configuraciones con “dos centros”.
Otra parte impide que los vértices buenos se conecten entre sí.
Juntas, esas restricciones fuerzan que un conjunto pequeño de vértices “malos” cubra todas las aristas.
Eso reduce globalmente la densidad del grafo.

En los walkthroughs se explica que evitar la familia $𝐽$ hace escasas ciertas extensiones de dos centros, mientras que evitar la familia $𝐾$ convierte los vértices excepcionales en una cubierta de aristas. Ninguna de las dos familias por separado basta; el efecto fuerte aparece por la combinación.

5. La idea de “vértices buenos” y “vértices malos”

La prueba clasifica vértices en:

buenos, si aparecen como centro de cierta configuración;
malos, si no aparecen así.

Luego demuestra dos cosas.

Primero, no puede haber demasiados vértices malos, porque los conteos de caminos cortos obligan a muchos vértices a participar en configuraciones de dos centros.

Segundo, toda arista debe tocar un vértice malo. Es decir:

los vértices malos forman una cubierta de aristas.

Esto es muy potente: si todos los bordes tienen que pasar por un conjunto controlado de vértices malos, entonces el número total de aristas se limita.

Los walkthroughs explican que, si una arista uniera dos vértices buenos, aparecería una copia prohibida de la segunda plantilla; por tanto, toda arista toca un vértice malo. Después, usando una estimación del grado máximo, se obtiene la desigualdad que fuerza el exponente $21 / 16$ .

21 / 16 = 1.3125

mientras que:

4 / 3 = 1.3333 \dots

La diferencia exacta es:

4 / 3 - 21 / 16 = 1 / 48

Ese es el ahorro polinómico que rompe la conjetura.

6. Por qué cada miembro individual sigue teniendo muchos grafos que lo evitan

Para que el contraejemplo funcione, no basta con demostrar que prohibir toda la familia reduce mucho las aristas. También hay que demostrar que cada grafo individual de la familia, por separado, todavía permite grafos densos.

Aquí entran los cuadrángulos generalizados.

La IA usa grafos de incidencia de ciertos objetos de geometría finita, llamados cuadrángulos generalizados. Estos grafos tienen muchas aristas, del orden:

𝑛^{4 / 3}

y además tienen estructura suficiente para evitar cada prohibición individual adecuada.

El walkthrough dice que se usan grafos de incidencia del cuadrángulo generalizado simpléctico $𝑊 (𝑞)$ , con $𝑒_{𝑞} \geq 2^{- 4 / 3} 𝑛_{𝑞}^{4 / 3}$ , y que según la característica del campo —par o impar— se obtienen testigos distintos para miembros distintos de la familia.

Este detalle es crucial:

No hay un único grafo denso que evite toda la familia. Para cada miembro individual se elige un testigo distinto.

Eso es precisamente lo que rompe compactness.

En lenguaje RMS:

cada restricción aislada puede ser esquivada por una arquitectura;
pero el conjunto de restricciones, actuando simultáneamente, cierra todas las salidas.

7. Segundo resultado: degeneracy conjecture

Ahora viene la segunda conjetura.

Un grafo es $𝑟$ -degenerado si en todo subgrafo no vacío hay algún vértice de grado como mucho $𝑟$ .

Intuitivamente, un grafo 2-degenerado parece “poco denso internamente”. Puedes ir eliminando vértices de grado 1 o 2 hasta vaciarlo.

Erdős conjeturó que todo grafo bipartito fijo $𝑟$ -degenerado debería satisfacer:

ex (𝑛, 𝐻) = 𝑂 (𝑛^{2 - 1 / 𝑟})

Para $𝑟 = 2$ , eso predice:

ex (𝑛, 𝐻) = 𝑂 (𝑛^{3 / 2})

El manuscrito afirma que la IA refuta esta conjetura incluso en el primer caso abierto relevante, $𝑟 = 2$ . Construye un grafo bipartito conectado y 2-degenerado $𝐻$ , junto con constantes $𝑐, 𝜀 > 0$ , tal que $ex (𝑛, 𝐻) \geq 𝑐 𝑛^{3 / 2 + 𝜀}$ para todo $𝑛$ suficientemente grande.

Es decir:

Existe un grafo aparentemente “simple” desde el punto de vista local —2-degenerado— que, sin embargo, puede evitarse en grafos más densos de lo esperado.

8. Por qué la degeneracy conjecture parecía plausible

Parecía razonable por una intuición de embedding.

Si un grafo $𝐻$ es 2-degenerado, puedes ordenarlo de forma que cada nuevo vértice dependa de como máximo dos anteriores. Entonces, si el grafo anfitrión tiene mucha densidad, uno esperaría poder insertar $𝐻$ paso a paso:

Colocas los primeros vértices.
Cada nuevo vértice necesita ser vecino de uno o dos vértices ya colocados.
Si hay muchos pares con muchos vecinos comunes, parecería que siempre puedes continuar.

El walkthrough dice que esta era la trampa: en un grafo con grado medio alrededor de $𝑛^{1 / 2}$ , la convexidad fuerza muchos pares con vecinos comunes, y una incrustación greedy parece plausible. Pero los pares útiles para una etapa no tienen por qué coincidir con los pares útiles para la etapa siguiente.

Esa es la grieta.

La densidad global no garantiza compatibilidad secuencial entre las restricciones locales.

9. La clave: degeneración no es lo mismo que bajo grado en un lado

Esta distinción es fundamental.

Si tienes un grafo bipartito donde una de las dos partes tiene grado máximo 2, entonces sí hay resultados que dan la cota esperada.

Pero 2-degenerado no significa eso.

Un grafo 2-degenerado puede eliminarse en un orden donde los vértices de grado bajo van alternando entre los dos lados de la bipartición. El walkthrough subraya que la construcción explota exactamente esa alternancia: los pasos de degeneración pueden exigir compatibilidades primero en un lado y luego en el otro.

En lenguaje simple:

No falla porque haya vértices localmente muy densos; falla porque las exigencias de vecindad común alternan entre lados y no pueden satisfacerse simultáneamente.

10. Cómo construye la IA el contraejemplo degenerado

La IA construye un grafo fijo $𝐻$ en capas.

La regla es:

en cada nueva capa, se añade un vértice por cada par de vértices de la capa anterior.

Eso crea un grafo 2-degenerado, porque cada vértice nuevo nace conectado solo a dos padres anteriores.

Pero la estructura por capas hace que cualquier embedding de $𝐻$ en un grafo anfitrión tenga que encontrar, repetidamente, vecinos comunes compatibles para muchos pares.

El manuscrito resume la estrategia así: para la conjetura de degeneracy, se construye $𝐻$ en capas, añadiendo un vértice por cada par de vértices de la capa anterior; luego se usa un grafo anfitrión basado en distancia de Hamming y muestreo aleatorio de vértices para lograr muchas aristas pero evitar $𝐻$ .

11. El grafo anfitrión: dos cubos de Hamming

El grafo que evita $𝐻$ se construye así:

Tomas dos copias del cubo binario:

{0, 1}^{𝑚}

Unes dos palabras, una en cada lado, si están cerca en distancia de Hamming.
Después haces un muestreo: conservas cada vértice con cierta probabilidad.

El walkthrough indica que se toman dos copias disjuntas del cubo binario y se unen palabras de lados opuestos cuando su distancia de Hamming es como mucho $𝜏 𝑚$ . El grado viene dado por el tamaño de una bola de Hamming, aproximadamente $2^{ℎ (𝜏) 𝑚}$ .

Eso produce un grafo con:

muchos vértices;
muchas aristas;
una geometría interna muy rígida;
pero sin el patrón $𝐻$ .

12. La idea entrópica

Esta es la parte más bonita del segundo contraejemplo.

Si intentas incrustar $𝐻$ en el grafo de Hamming, cada nueva capa debe estar cerca de sus dos padres en distancia de Hamming.

Eso limita cuánta libertad tiene la nueva capa.

La prueba introduce un potencial de entropía por capas. Cada capa tiene una especie de “diversidad coordenada” medida mediante entropía binaria.

La idea es:

cada vez que avanzas una capa de $𝐻$ , si quieres sobrevivir al muestreo aleatorio, necesitas suficiente entropía; pero la restricción de estar cerca de dos padres obliga a que esa entropía aumente de manera controlada. Después de suficientes capas, el potencial tendría que superar su máximo posible.

El walkthrough lo resume muy bien: un embedding de $𝐻$ aumentaría un potencial de entropía acotado una cantidad fija en cada capa; tras suficientes capas, eso es imposible.

En lenguaje sencillo:

Para copiar $𝐻$ , el sistema tendría que ganar libertad capa tras capa. Pero la libertad total disponible está limitada entre 0 y 1. Llega un momento en que la copia no puede existir.

13. Por qué el muestreo mantiene muchas aristas

La prueba no solo debe evitar $𝐻$ ; también necesita conservar más de $𝑛^{3 / 2}$ aristas.

Para eso se usa un argumento de segundo momento. El grafo de Hamming original tiene muchos bordes. Luego se retienen vértices aleatoriamente. Aunque las aristas resultantes no son independientes —dos aristas pueden compartir un vértice—, se controla la varianza.

El walkthrough explica que el número esperado de aristas supervivientes es aproximadamente $𝑝^{2} 𝑄 𝐷_{𝑚}$ , y que la varianza queda controlada; de ahí se obtiene con alta probabilidad un grafo $𝐻$ -free con unas $𝑛^{3 / 2 + 𝜀}$ aristas.

Así se consigue:

ex (𝑛, 𝐻) \geq 𝑐 𝑛^{3 / 2 + 𝜀}

para todo $𝑛$ grande.

14. Qué NO significa

No significa que la teoría extremal de grafos esté “rota”.

No significa que todo grafo 2-degenerado tenga número extremal mayor que $𝑛^{3 / 2}$ .

No significa que la degeneración deje de ser útil.

Lo que significa es más fino:

La degeneración por sí sola no basta para determinar el exponente extremal esperado.

Y para compactness:

Una familia finita de prohibiciones puede tener un efecto colectivo más fuerte que cualquiera de sus miembros individuales.

Son resultados contra intuiciones estructurales amplias, no contra toda la teoría existente.

15. Por qué esto es importante

Porque afecta a dos creencias metodológicas profundas.

La primera creencia era:

en una familia finita, algún miembro debería explicar el comportamiento extremal dominante.

La IA demuestra que no necesariamente. Puede haber efectos colectivos entre prohibiciones.

La segunda creencia era:

si un grafo prohibido es localmente poco denso, por ejemplo 2-degenerado, debería ser fácil forzar su aparición en grafos suficientemente densos.

La IA demuestra que tampoco necesariamente. La dificultad puede estar en la compatibilidad dinámica de las capas, no en la densidad local.

16. Lectura RMS / pensamiento complejo

Este resultado es quizá el más “sistémico” de todos los de grafos.

Compactness

Recursos: grafos prohibidos, ciclos, plantillas $𝐽$ y $𝐾$ , cuadrángulos generalizados, caminos cortos, vértices buenos/malos.

Mecanismos: prohibición simultánea, conteo de caminos, cubiertas de aristas, separación por característica del campo, testigos individuales distintos.

Sistema: una familia finita cuyas restricciones no se suman de manera lineal; interactúan y producen un efecto global superior al de cada pieza.

La lección RMS:

El comportamiento del sistema no está contenido en una sola restricción. Está en la interacción entre restricciones.

Degeneracy

Recursos: grafo 2-degenerado, capas, pares de padres, cubo de Hamming, distancia, muestreo aleatorio, entropía.

Mecanismos: alternancia de bipartición, vecindades comunes incompatibles, aumento de potencial entrópico, thinning aleatorio, segundo momento.

Sistema: un patrón localmente simple que se vuelve globalmente difícil de incrustar porque sus dependencias alternan y consumen libertad capa tras capa.

La lección RMS:

Una propiedad local débil no garantiza control global si las dependencias se encadenan de forma adversa.

Síntesis final

La IA habría resuelto el bloque de compactness and degeneracy conjectures construyendo dos contraejemplos separados en teoría extremal de grafos.

Primero, refuta la compactness conjecture de Erdős–Simonovits con una familia finita $𝐹$ de grafos conectados, bipartitos y con ciclos: prohibir toda la familia reduce el número extremal a $𝑂 (𝑛^{4 / 3 - 1 / 48})$ , pero cada miembro individual permite $Ω (𝑛^{4 / 3})$ aristas. La clave es que las restricciones actúan colectivamente: una parte controla configuraciones de dos centros y otra convierte vértices excepcionales en una cubierta de aristas.

Segundo, refuta la conjetura de Erdős sobre grafos bipartitos $𝑟$ -degenerados ya para $𝑟 = 2$ : construye un grafo 2-degenerado fijo $𝐻$ con $ex (𝑛, 𝐻) \geq 𝑐 𝑛^{3 / 2 + 𝜀}$ . La clave es una construcción por capas y un grafo anfitrión basado en cubos de Hamming: cualquier copia de $𝐻$ tendría que aumentar un potencial de entropía en cada capa hasta superar su límite máximo.

En clave RMS, el mensaje es fuerte: lo local no siempre controla lo global; una familia puede ser más que la suma de sus miembros; y una estructura simple puede volverse compleja cuando sus dependencias se encadenan en capas

notistecnicas

traductor

domingo, 2 de agosto de 2026

IA: Avances matemáticos: Compactness and degeneracy conjectures en teoría extremal de grafos