Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

Resumen Técnico: Certificados Primos para Números de Ramsey Exactos de Vértices Coprimos

Enunciado del Problema
El artículo investiga el número de Ramsey mixto de vértices coprimos, denotado $R_{cop}(k_1, \dots, k_c)$, definido sobre el grafo coprimo $G_n$. El conjunto de vértices de $G_n$ es $\{1, \dots, n\}$, donde existe una arista entre vértices distintos $a$ y $b$ si y solo si $\gcd(a, b) = 1$. El problema solicita el menor entero $n$ tal que toda $c$-coloración de los vértices de $G_n$ contenga un clique monocromático de tamaño $k_i$ en el color $i$ para algún $i \in \{1, \dots, c\}$. Equivalentemente, busca el umbral donde cualquier partición de $\{1, \dots, n\}$ en $c$ conjuntos debe contener un conjunto de $k_i$ enteros coprimos dos a dos en al menos una parte.

Metodología y Mecanismo Central
Los autores resuelven este problema identificando un "certificado" estructural que colapsa el espacio de búsqueda, contrastándolo con la complejidad exponencial de las codificaciones SAT directas. La metodología se basa en dos construcciones complementarias basadas en divisores primos:

1. Cota Superior (Clique Primo): El conjunto $\{1\} \cup \{p \le n : p \text{ es primo}\}$ forma un clique en $G_n$ de tamaño $\pi(n) + 1$, donde $\pi(n)$ es la función de conteo de primos. Por el principio del palomar, si la capacidad total de las clases de color (suma de $k_i - 1$) es menor que el tamaño de este clique, se fuerza un clique monocromático del tamaño requerido.
2. Cota Inferior (Partición de Binarios Primos): Para $n$ por debajo del umbral, los autores construyen una coloración válida que evita cliques monocromáticos. Esto se logra particionando los primos disponibles en "binarios" con capacidades correspondientes a $k_i - 1$ (con un ajuste para el vértice universal 1). Cada número compuesto se colorea basándose en un divisor primo elegido que cae en uno de estos binarios. Dado que los enteros coprimos dos a dos no pueden compartir un divisor primo, el tamaño de cualquier clique monocromático está acotado por la capacidad del binario que contiene sus primos testigo.

Este enfoque se generaliza a grafos de disjunción de soportes, donde los vértices portan soportes (subconjuntos de átomos) y la adyacencia se define por soportes disjuntos. El grafo coprimo es un caso específico donde los átomos son números primos.

Contribuciones y Resultados Clave

• Fórmula Mixta Exacta: El artículo prueba la fórmula exacta para el número de Ramsey mixto de vértices coprimos:
  $$R_{cop}(k_1, \dots, k_c) = p_M$$
  donde $M = \sum_{i=1}^c (k_i - 1)$ y $p_M$ es el $M$-ésimo número primo. Este resultado se cumple para todo $c \ge 1$ y $k_i \ge 2$.
• Reducción de Coloración de Aristas: El artículo distingue la coloración de vértices de la coloración de aristas en el mismo grafo anfitrión. Establece una reducción exacta para el número de Ramsey coprimo de aristas $R_{cop}^{edge}$ hacia los números de Ramsey clásicos de grafos completos $R_{cl}$:
  $$R_{cop}^{edge}(k_1, \dots, k_c) = p_{R_{cl}(k_1, \dots, k_c) - 1}$$
  Esto demuestra que los valores coprimos de aristas no son nuevas constantes aritméticas, sino números de Ramsey clásicos vistos a través de un mapa de índice primo.
• Umbral Balanceado de Dos Colores: Los autores abordan la preocupación de que la construcción de la cota inferior podría depender de clases de color altamente desequilibradas. Proban que para el caso diagonal de dos colores, el umbral balanceado (donde los tamaños de las clases de color difieren en a lo sumo 1) es idéntico al umbral sin restricciones: $L_{bal}(k; 2) = p_{2k-2} - 1$. Esto se logra mediante una división determinista de binarios primos y una desigualdad débil de brecha de índice primo ($2p_m < p_{2m} < 3p_m$).
• Equilibrio Multicolor y Casos Límite:
  • Para $c \ge 3$, el umbral balanceado no es exacto para $k$ pequeños, pero se vuelve exacto para todo $k$ suficientemente grande (exactitud eventual), demostrado mediante un argumento tipo Hall y estimaciones de Selberg–Delange.
  • El artículo analiza intervalos desplazados $\{m+1, \dots, m+n\}$. Sin el vértice universal 1 y el clique primo inicial, la fórmula exacta falla, y el umbral depende de las estructuras locales de factores primos.
• Primitiva Algorítmica: Se propone una primitiva de extracción de certificados en tiempo polinomial para verificar si un grafo dado admite un certificado de disjunción de soportes. Si se verifica, el umbral de Ramsey y las coloraciones extremas se determinan sin búsqueda.

Significado y Alcance
El artículo afirma una solución completa para el problema de coloración de vértices en el grafo coprimo de enteros, reemplazando búsquedas computacionales a gran escala (por ejemplo, codificaciones SAT con millones de cláusulas) con un certificado pequeño y explícito de índice primo.

• Insight Estructural: El trabajo destaca que la rigidez aritmética del grafo coprimo (controlada por divisores primos) permite que el problema de Ramsey colapse en un simple problema de empaquetado en binarios sobre primos, a diferencia de los problemas de Ramsey de aristas clásicos asintóticamente difíciles en grafos completos.
• Clarificación de Trabajo Previo: Los autores aclaran que los resultados computacionales anteriores sobre "números de Ramsey coprimos" (específicamente los de Towell) se referían a la variante de coloración de aristas, la cual el artículo muestra que es equivalente a los números de Ramsey clásicos. La fórmula de coloración de vértices presentada aquí no estaba presente en fuentes públicas verificadas.
• Limitaciones: El artículo declara explícitamente que no mejora los límites de Ramsey de aristas clásicos ni propone un solucionador general asistido por IA. Los resultados son específicos del grafo coprimo y sus variantes de disjunción de soportes. El artículo identifica problemas abiertos relacionados con objetivos de aristas no completos (caminos, ciclos), equilibrio multicolor con restricción de densidad para $k$ pequeños, y umbrales de Ramsey para otros grafos aritméticos donde la propiedad de disjunción de soportes no explica completamente la adyacencia.

En resumen, el artículo proporciona una prueba definitiva y elemental para una clase específica de números de Ramsey aritméticos, demostrando que para este grafo anfitrión, la "obstrucción" es un clique primo explícito en lugar de una configuración oculta similar a la aleatoria.