IA : Avances matemáticos en Multicolor Ramsey numbers — números de Ramsey multicolor,

Multicolor Ramsey numbers — números de Ramsey multicolor,

La idea central es:

La IA habría demostrado que los números de Ramsey multicolor para triángulos crecen superexponencialmente:

$${𝑅}_{𝑘}(3)={𝑘}^{\mathrm{\Theta }(𝑘)}$$

resolviendo el problema de si el crecimiento era solo exponencial o realmente más rápido.

OpenAI lo presenta como una cota inferior superexponencial para los números de Ramsey multicolor de triángulos, resolviendo el problema 183 de Erdős.

1. Qué es ${𝑅}_{𝑘}(3)$

El número:

$${𝑅}_{𝑘}(3)$$

significa lo siguiente:

Es el menor número $𝑁$ tal que, si coloreas todas las aristas del grafo completo ${𝐾}_{𝑁}$ usando $𝑘$ colores, inevitablemente aparece un triángulo con sus tres aristas del mismo color.

Ejemplo intuitivo: tienes muchos puntos y unes todos con líneas. Cada línea recibe uno de $𝑘$ colores. Ramsey pregunta: ¿a partir de cuántos puntos es inevitable que aparezca un triángulo monocromático?

Para $𝑘=2$, el caso clásico es:

$${𝑅}_2(3)=6$$

Con 6 personas, si coloreas cada relación como “se conocen” o “no se conocen”, siempre hay tres que se conocen mutuamente o tres que no se conocen mutuamente.

Pero el resultado de la IA no va sobre $𝑘=2$, sino sobre qué pasa cuando el número de colores $𝑘$ crece mucho.

2. Qué se sabía antes

Había dos mundos separados.

Por abajo, existían construcciones que evitaban triángulos monocromáticos usando muchos colores, pero daban básicamente crecimiento exponencial con base fija. El manuscrito dice que antes de este trabajo la mejor cota inferior conocida era del tipo:

$${𝑅}_{𝑘}(3)\ge {380}^{𝑘\mathrm{/}5}-𝑂(1)$$

Por arriba, había cotas factoriales, aproximadamente del orden de $𝑘!$, y el récord citado en el manuscrito era:

$${𝑅}_{𝑘}(3)\le (𝑒-\frac{1}{6})𝑘!+1$$

para $𝑘\ge 4$.

La gran pregunta era:

¿Está ${𝑅}_{𝑘}(3)$ más cerca de una exponencial ${𝐶}^{𝑘}$, o crece como algo parecido a ${𝑘}^{𝑘}$?

Erdős había planteado la cuestión de si el límite:

$$𝐿=\underset{𝑘\to \mathrm{\infty }}{\lim }{𝑅}_{𝑘}(3{)}^{1\mathrm{/}𝑘}$$

era finito o infinito. El manuscrito recuerda que Erdős ofreció premios por determinar ese valor y por decidir si era finito.

3. Qué demuestra la IA

El resultado afirma que existe una constante absoluta $𝑐>0$ tal que, para todo $𝑘\ge 2$:

$${𝑅}_{𝑘}(3)\ge {\left(\frac{𝑐{𝑘}^{1\mathrm{/}3}}{\log 𝑘}\right)}^{𝑘}$$

Esto implica que:

$${𝑅}_{𝑘}(3{)}^{1\mathrm{/}𝑘}\to \mathrm{\infty }$$

y, combinado con la cota superior factorial, da:

$${𝑅}_{𝑘}(3)={𝑘}^{\mathrm{\Theta }(𝑘)}$$

El paper lo resume como:

$${𝑘}^{(1\mathrm{/}3-𝑜(1))𝑘}\le {𝑅}_{𝑘}(3)\le {𝑘}^{(1+𝑜(1))𝑘}$$

Es decir: el crecimiento es superexponencial. No se sabe todavía el exponente exacto dentro de ese intervalo, pero se resuelve la cuestión cualitativa principal: no hay una base exponencial fija.

4. Qué significa una cota inferior en Ramsey

Una cota inferior para ${𝑅}_{𝑘}(3)$ significa que eres capaz de construir un grafo completo muy grande cuyas aristas están coloreadas con $𝑘$ colores sin crear ningún triángulo monocromático.

Es decir, no demuestras inevitabilidad; demuestras resistencia.

La IA construye coloraciones enormes donde cada color individual forma un grafo sin triángulos. Como las aristas están todas coloreadas, el problema se puede ver así:

cubrir todas las aristas de ${𝐾}_{𝑁}$ con $𝑘$ grafos sin triángulos, de forma que ningún color genere un triángulo.

La dificultad no es construir un grafo sin triángulos. Eso es fácil. La dificultad es cubrir todas las aristas con muchos colores reutilizados sin que algún color cierre un triángulo.

5. Por qué los métodos clásicos no bastaban

Los métodos clásicos multiplicaban construcciones pequeñas: si tienes una coloración buena con $𝑘$ colores y otra con $\mathrm{\ell }$ colores, puedes combinarlas para obtener una con $𝑘+\mathrm{\ell }$ colores. Eso da crecimiento exponencial, pero con una base fija.

El problema era conseguir que la “base” creciera con $𝑘$.

El walkthrough de OpenAI lo formula así: los intentos de probar que $𝐿<\mathrm{\infty }$ y los intentos de conseguir crecimiento factorial acababan chocando con el mismo ingrediente ausente: reutilizar colores de manera controlada entre bloques diferentes.

Esta frase es clave:

el obstáculo no era tener más colores, sino reutilizarlos sin que la reutilización cree triángulos.

6. La innovación: paletas de colores ausentes

La IA introduce una construcción recursiva por bloques.

En cada etapa $𝑗$, divide los vértices en muchos bloques. Cada bloque se etiqueta con una paleta $𝑃$, que no significa “colores disponibles”, sino justo lo contrario:

$𝑃$ es el conjunto de colores que faltan dentro de ese bloque.

Si un color no está en $𝑃$, está activo dentro del bloque. Si está en $𝑃$, no aparece en las aristas internas de ese bloque.

Esto permite una regla muy potente: cuando coloreas una arista entre dos bloques $𝑃$ y $𝑄$, usas colores de la diferencia simétrica:

$$𝑃\mathrm{△}𝑄$$

Es decir, colores que están ausentes en uno de los bloques pero activos en el otro.

Con eso, cada color de una arista cruzada queda activo en exactamente uno de los dos bloques y ausente en el otro. El manuscrito explica que los bloques se indexan por paletas $𝑃\subset [𝑗𝑡]$, que dentro de cada bloque se coloca una copia de la coloración anterior, y que una familia maximal de paletas garantiza muchas opciones separadas entre sí.

7. El invariante oculto: no basta evitar triángulos

Aquí está la parte más importante.

La IA no mantiene solo el invariante “no hay triángulos monocromáticos”. Mantiene algo más fuerte:

en la etapa $𝑗$, el grafo de cada color es propiamente $(𝑗+1)$-coloreable.

Es decir, para cada color $𝑐$, las aristas de color $𝑐$ forman un grafo que puede colorearse en pocos niveles internos sin que dos vértices unidos por color $𝑐$ compartan etiqueta.

Este invariante adicional es lo que permite controlar la recursión. El paper dice explícitamente que se construyen coloraciones donde cada grafo de color tiene una coloración propia corta, y que este invariante más fuerte es lo que hace posible la recursión sin triángulos.

En lenguaje sencillo:

para evitar triángulos no basta con saber qué color tiene cada arista; también necesitas saber en qué “clase interna” cae cada vértice para cada color activo.

Esto es muy RMS: el sistema no se controla solo con recursos —colores—, sino con un mecanismo organizativo interno —etiquetas propias por color.

8. El papel de las matrices saturadas

La construcción necesita una regla fija que decida cómo colorear las aristas entre bloques sin improvisar.

Para eso usa un ingrediente tomado de trabajos anteriores sobre matrices saturadas, hat guessing y zero-error list decoding. El propio manuscrito aclara que la construcción de matrices saturadas no es nueva; lo nuevo es su aplicación a $𝑅(3,\dots ,3)$.

La herramienta produce dos funciones:

$$𝑓,𝑔:[𝐻{]}^{𝑠}\to [𝐻{]}^{𝑠}$$

con una propiedad de cobertura: para cualesquiera dos palabras $𝑥,𝑦$, existe una coordenada $𝑑$ tal que:

$${𝑥}_{𝑑}=𝑓(𝑦{)}_{𝑑}$$

o bien:

$${𝑦}_{𝑑}=𝑔(𝑥{)}_{𝑑}$$

Esta propiedad garantiza que, al comparar dos vértices de bloques distintos, siempre hay alguna coordenada que permite elegir un color de forma controlada.

La intuición:

las matrices saturadas actúan como un sistema de coordinación: obligan a que dos bloques encuentren una coordenada común donde la regla de color sea compatible.

9. La regla para colorear aristas entre bloques

Supongamos dos bloques con paletas $𝑃<𝑄$.

Como las paletas están bien separadas, hay muchos colores en:

$$𝑄\setminus 𝑃$$

y muchos en:

$$𝑃\setminus 𝑄$$

La construcción elige colores:

$${𝑎}_1,\dots ,{𝑎}_{𝑠}\in 𝑄\setminus 𝑃$$

y:

$${𝑏}_1,\dots ,{𝑏}_{𝑠}\in 𝑃\setminus 𝑄$$

Los ${𝑎}_{𝑑}$ están activos en el bloque $𝑃$ y ausentes en el bloque $𝑄$. Los ${𝑏}_{𝑑}$ están activos en $𝑄$ y ausentes en $𝑃$.

Para un vértice $𝑢\in {𝑉}_{𝑃}$ y otro $𝑣\in {𝑉}_{𝑄}$, se miran sus etiquetas internas y se forman dos palabras:

$$𝑥(𝑢),𝑦(𝑣)\in [𝐻{]}^{𝑠}$$

Si para alguna coordenada $𝑑$:

$${𝑥}_{𝑑}(𝑢)=𝑓(𝑦(𝑣){)}_{𝑑}$$

se colorea la arista $𝑢𝑣$ con ${𝑎}_{𝑑}$. Si no, se usa un ${𝑏}_{𝑑}$ garantizado por la otra condición. El manuscrito subraya que cada arista cruzada queda con un color activo en un extremo y ausente en el otro, y que la etiqueta propia del extremo activo queda determinada por el extremo opuesto.

Ese último detalle es el corazón de la prueba.

10. Por qué no aparecen triángulos monocromáticos

Hay tres casos.

Caso 1: los tres vértices están en el mismo bloque.
No hay triángulo monocromático por inducción: dentro del bloque hay una copia de la construcción anterior.

Caso 2: dos vértices están en un bloque y el tercero en otro.
Supón que las dos aristas cruzadas tienen el mismo color. Si ese color está ausente en el bloque que contiene los dos vértices, la arista interna no puede tener ese color. Si está activo, la regla de coordenadas fuerza que los dos vértices internos tengan la misma etiqueta propia para ese color; por tanto, su arista interna tampoco puede tener ese color. Esta es precisamente la razón de mantener el invariante de colorabilidad propia.

Caso 3: los tres vértices están en tres bloques distintos.
Para que las tres aristas tengan el mismo color $𝑐$, ese color tendría que pertenecer simultáneamente a:

$$𝑃\mathrm{△}𝑄,𝑄\mathrm{△}𝑅,𝑃\mathrm{△}𝑅$$

Pero eso exigiría que tres bits de pertenencia —si $𝑐$ está o no está en cada paleta— fueran todos distintos por pares. Con valores binarios eso es imposible.

Esta es una idea preciosa:

la imposibilidad de un triángulo monocromático entre tres bloques se reduce a una imposibilidad lógica de tres bits.

11. Por qué el crecimiento se vuelve superexponencial

En cada etapa se crean muchos bloques, uno por paleta seleccionada. La clave es que hay muchísimas paletas bien separadas. Si ${𝐵}_{𝑗}$ es el número de paletas en la etapa $𝑗$, el número total de vértices después de $𝐻$ etapas es aproximadamente:

$${𝑛}_{𝐻}=\prod _{𝑗=1}^{𝐻}{𝐵}_{𝑗}$$

Mientras tanto, el número de colores usados es:

$${𝑘}_{𝐻}=𝐻𝑡$$

con:

$$𝑡=𝑠\lceil \log 𝐻\rceil$$

El walkthrough resume el cálculo así: el número de colores acaba siendo aproximadamente:

$${𝑘}_{𝐻}\asymp {𝐻}^3{\log }^3𝐻$$

mientras que el número de vértices satisface:

$${𝑛}_{𝐻}\ge ({𝑐}_0𝐻{)}^{{𝑘}_{𝐻}}$$

Al despejar $𝐻$ en función de $𝑘$, sale:

$$𝐻\sim \frac{{𝑘}^{1\mathrm{/}3}}{\log 𝑘}$$

y por eso aparece:

$${𝑅}_{𝑘}(3)\ge {\left(\frac{𝑐{𝑘}^{1\mathrm{/}3}}{\log 𝑘}\right)}^{𝑘}$$

El documento explica que el exponente $1\mathrm{/}3$ viene del balance entre tres costes: el tamaño de las matrices saturadas, la cobertura simultánea y la separación de paletas.

12. Qué relación tiene con Shannon capacity

El resultado también implica algo en teoría de la información: existen grafos con número de independencia 2 pero con capacidad de Shannon arbitrariamente grande.

La capacidad de Shannon mide cuántos mensajes pueden transmitirse sin error usando un grafo de confusiones. El paper explica que, mediante la correspondencia Ramsey–Shannon, la divergencia de ${𝑅}_{𝑘}(3{)}^{1\mathrm{/}𝑘}$ produce grafos con independencia 2 y capacidad de Shannon sin cota universal.

En lenguaje simple:

aunque un grafo parezca muy restrictivo a una sola copia, al tomar productos fuertes puede permitir una capacidad de comunicación sin error mucho mayor de lo esperado.

Esto conecta Ramsey, grafos, códigos y teoría de la información.

13. Qué NO significa

No significa que ya sepamos el valor exacto de ${𝑅}_{𝑘}(3)$.

No significa que el exponente $1\mathrm{/}3$ sea óptimo. Ahora sabemos:

$${𝑘}^{(1\mathrm{/}3-𝑜(1))𝑘}\le {𝑅}_{𝑘}(3)\le {𝑘}^{(1+𝑜(1))𝑘}$$

Todavía queda una brecha entre $1\mathrm{/}3$ y $1$ en el exponente.

No significa que se hayan calculado los Ramsey pequeños. Los números de Ramsey concretos para pocos colores siguen siendo problemas computacionales/combinatorios muy difíciles.

Sí significa algo grande:

se resuelve la pregunta cualitativa: ${𝑅}_{𝑘}(3)$ no crece como ${𝐶}^{𝑘}$, sino como ${𝑘}^{\mathrm{\Theta }(𝑘)}$.

14. Lectura RMS / pensamiento complejo

Este resultado es de los más claros para vuestro marco RMS.

Recursos: colores, bloques, paletas, matrices saturadas, etiquetas internas, grafos sin triángulos, diferencias simétricas, coordenadas.

Mecanismos: recursión por etapas, separación de paletas, reutilización controlada de colores, cobertura coordenada, invariante de colorabilidad propia, exclusión de triángulos por casos.

Sistema: una arquitectura de coloración que permite crecer enormemente sin que aparezcan triángulos monocromáticos.

La clave sistémica:

El avance no consiste en añadir colores sin más, sino en crear una regla institucional de reutilización: cada color puede circular entre bloques, pero solo bajo condiciones que impiden cerrar un triángulo.

En términos de Morin/RMS, hay una lección fuerte:

la complejidad no se controla eliminando interacciones, sino organizando las interacciones con invariantes que sobreviven a la recursión.

Síntesis final

La IA habría resuelto el problema de los números de Ramsey multicolor para triángulos demostrando una cota inferior superexponencial:

$${𝑅}_{𝑘}(3)\ge {\left(\frac{𝑐{𝑘}^{1\mathrm{/}3}}{\log 𝑘}\right)}^{𝑘}$$

Combinada con la cota superior factorial, esto establece:

$${𝑅}_{𝑘}(3)={𝑘}^{\mathrm{\Theta }(𝑘)}$$

La idea central fue construir coloraciones recursivas sin triángulos monocromáticos usando paletas de colores ausentes, bloques separados, matrices saturadas y un invariante más fuerte que la simple ausencia de triángulos: cada grafo de color mantiene una coloración propia corta. En clave RMS, la IA no solo encontró una construcción grande; encontró una arquitectura para reutilizar colores sin que el sistema colapse en triángulos monocromaticos