Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

Resumo Técnico: Certificados Primos para Números de Ramsey Exatos de Coprimos em Vértices

Declaração do Problema
O artigo investiga o número de Ramsey misto de coprimos em vértices, denotado por $R_{cop}(k_1, \dots, k_c)$, definido no grafo de coprimos $G_n$. O conjunto de vértices de $G_n$ é $\{1, \dots, n\}$, onde uma aresta existe entre vértices distintos $a$ e $b$ se e somente se $\gcd(a, b) = 1$. O problema solicita o menor inteiro $n$ tal que toda $c$-coloração dos vértices de $G_n$ contenha um clique monocromático de tamanho $k_i$ na cor $i$ para algum $i \in \{1, \dots, c\}$. Equivalentemente, busca-se o limiar onde qualquer partição de $\{1, \dots, n\}$ em $c$ conjuntos deve conter um conjunto de $k_i$ inteiros coprimos dois a dois em pelo menos uma parte.

Metodologia e Mecanismo Central
Os autores resolvem este problema identificando um "certificado" estrutural que colapsa o espaço de busca, contrastando-o com a complexidade exponencial de codificações SAT diretas. A metodologia baseia-se em duas construções complementares baseadas em divisores primos:

1. Limite Superior (Clique Primo): O conjunto $\{1\} \cup \{p \le n : p \text{ é primo}\}$ forma um clique em $G_n$ de tamanho $\pi(n) + 1$, onde $\pi(n)$ é a função de contagem de primos. Pelo princípio da casa dos pombos, se a capacidade total das classes de cores (soma de $k_i - 1$) for menor que o tamanho deste clique, um clique monocromático do tamanho requerido é forçado.
2. Limite Inferior (Partição de Binários Primos): Para $n$ abaixo do limiar, os autores constroem uma coloração válida que evita cliques monocromáticos. Isso é alcançado particionando os primos disponíveis em "binários" com capacidades correspondentes a $k_i - 1$ (com um ajuste para o vértice universal 1). Cada número composto é colorido com base em um divisor primo escolhido que cai em um desses binários. Como inteiros coprimos dois a dois não podem compartilhar um divisor primo, o tamanho de qualquer clique monocromático é limitado pela capacidade do binário contendo seus primos testemunha.

Esta abordagem é generalizada para grafos de disjunção de suportes, onde os vértices carregam suportes (subconjuntos de átomos) e a adjacência é definida por suportes disjuntos. O grafo de coprimos é uma instância específica onde os átomos são números primos.

Contribuições e Resultados Chave

• Fórmula Mista Exata: O artigo prova a fórmula exata para o número de Ramsey misto de coprimos em vértices:
  $$R_{cop}(k_1, \dots, k_c) = p_M$$
  onde $M = \sum_{i=1}^c (k_i - 1)$ e $p_M$ é o $M$-ésimo número primo. Este resultado vale para todo $c \ge 1$ e $k_i \ge 2$.
• Redução de Coloração de Arestas: O artigo distingue a coloração de vértices da coloração de arestas no mesmo grafo hospedeiro. Estabelece uma redução exata para o número de Ramsey de coprimos de arestas $R_{cop}^{edge}$ para os números de Ramsey clássicos de grafos completos $R_{cl}$:
  $$R_{cop}^{edge}(k_1, \dots, k_c) = p_{R_{cl}(k_1, \dots, k_c) - 1}$$
  Isso demonstra que os valores de coprimos de arestas não são novas constantes aritméticas, mas sim números de Ramsey clássicos vistos através de um mapa de índice primo.
• Limiar Balanceado de Duas Cores: Os autores abordam a preocupação de que a construção do limite inferior possa depender de classes de cores altamente desbalanceadas. Eles provam que, para o caso diagonal de duas cores, o limiar balanceado (onde os tamanhos das classes de cores diferem por no máximo 1) é idêntico ao limiar irrestrito: $L_{bal}(k; 2) = p_{2k-2} - 1$. Isso é alcançado via uma divisão determinística de binários primos e uma desigualdade fraca de lacuna de índice primo ($2p_m < p_{2m} < 3p_m$).
• Equilíbrio Multicolorido e Casos Limite:
  • Para $c \ge 3$, o limiar balanceado não é exato para $k$ pequeno, mas torna-se exato para todo $k$ suficientemente grande (exatidão eventual), provado via um argumento do tipo Hall e estimativas de Selberg–Delange.
  • O artigo analisa intervalos deslocados $\{m+1, \dots, m+n\}$. Sem o vértice universal 1 e o clique primo inicial, a fórmula exata falha, e o limiar depende de estruturas locais de fatores primos.
• Primitiva Algorítmica: É proposta uma primitiva de extração de certificados em tempo polinomial para verificar se um grafo dado admite um certificado de disjunção de suportes. Se verificado, o limiar de Ramsey e as colorações extremas são determinados sem busca.

Significado e Escopo
O artigo reivindica uma solução completa para o problema de coloração de vértices no grafo de coprimos inteiro, substituindo buscas computacionais em grande escala (por exemplo, codificações SAT com milhões de cláusulas) por um pequeno certificado explícito de índice primo.

• Insight Estrutural: O trabalho destaca que a rigidez aritmética do grafo de coprimos (controlada por divisores primos) permite que o problema de Ramsey colapse em um simples problema de empacotamento em binários sobre primos, ao contrário dos problemas de Ramsey de arestas clássicos assintoticamente difíceis em grafos completos.
• Esclarecimento de Trabalhos Anteriores: Os autores esclarecem que resultados computacionais anteriores sobre "números de Ramsey de coprimos" (especificamente os de Towell) referiam-se à variante de coloração de arestas, que o artigo mostra ser equivalente aos números de Ramsey clássicos. A fórmula de coloração de vértices apresentada aqui não estava presente em fontes públicas verificadas.
• Limitações: O artigo declara explicitamente que não melhora os limites clássicos de Ramsey de arestas nem propõe um solucionador geral assistido por IA. Os resultados são específicos ao grafo de coprimos e suas variantes de disjunção de suportes. O artigo identifica problemas abertos relacionados a alvos de arestas não completos (caminhos, ciclos), equilíbrio multicolorido com restrição de densidade para $k$ pequeno e limiares de Ramsey para outros grafos aritméticos onde a propriedade de disjunção de suportes não explica totalmente a adjacência.

Em resumo, o artigo fornece uma prova definitiva e elementar para uma classe específica de números de Ramsey aritméticos, demonstrando que, para este grafo hospedeiro, a "obstrução" é um clique primo explícito e não uma configuração oculta de tipo aleatório.