Prime Certificates for Exact Vertex-Coprime Ramsey Numbers

Riepilogo Tecnico: Certificati Primi per i Numeri di Ramsey Esatti di Vertice Coprimi

Enunciato del Problema
Il documento indaga il numero di Ramsey misto di vertice coprimo, denotato $R_{cop}(k_1, \dots, k_c)$, definito sul grafo coprimo $G_n$. L'insieme dei vertici di $G_n$ è $\{1, \dots, n\}$, dove un arco esiste tra vertici distinti $a$ e $b$ se e solo se $\gcd(a, b) = 1$. Il problema chiede il più piccolo intero $n$ tale che ogni $c$-colorazione dei vertici di $G_n$ contenga una cricca monocromatica di dimensione $k_i$ nel colore $i$ per qualche $i \in \{1, \dots, c\}$. Equivalentemente, cerca la soglia in cui qualsiasi partizione di $\{1, \dots, n\}$ in $c$ insiemi deve contenere un insieme di $k_i$ interi a due a due coprimi in almeno una parte.

Metodologia e Meccanismo Centrale
Gli autori risolvono questo problema identificando un "certificato" strutturale che collassa lo spazio di ricerca, mettendolo in contrasto con la complessità esponenziale delle codifiche SAT dirette. La metodologia si basa su due costruzioni complementari basate sui divisori primi:

1. Limitazione Superiore (Cricca Primi): L'insieme $\{1\} \cup \{p \le n : p \text{ è primo}\}$ forma una cricca in $G_n$ di dimensione $\pi(n) + 1$, dove $\pi(n)$ è la funzione di conteggio dei primi. Per il principio dei cassetti, se la capacità totale delle classi di colore (somma di $k_i - 1$) è inferiore alla dimensione di questa cricca, una cricca monocromatica della dimensione richiesta è forzata.
2. Limitazione Inferiore (Partizione Bin-Primi): Per $n$ al di sotto della soglia, gli autori costruiscono una colorazione valida che evita cricche monocromatiche. Ciò è ottenuto partizionando i primi disponibili in "bin" con capacità corrispondenti a $k_i - 1$ (con un aggiustamento per il vertice universale 1). Ogni numero composto è colorato in base a un divisore primo scelto che rientra in uno di questi bin. Poiché interi a due a due coprimi non possono condividere un divisore primo, la dimensione di qualsiasi cricca monocromatica è limitata dalla capacità del bin contenente i suoi primi testimoni.

Questo approccio è generalizzato ai grafi di disgiunzione dei supporti, dove i vertici portano supporti (sottoinsiemi di atomi) e l'adiacenza è definita da supporti disgiunti. Il grafo coprimo è un caso specifico in cui gli atomi sono i numeri primi.

Contributi e Risultati Chiave

• Formula Esatta Mista: Il documento dimostra la formula esatta per il numero di Ramsey misto di vertice coprimo:
  $$R_{cop}(k_1, \dots, k_c) = p_M$$
  dove $M = \sum_{i=1}^c (k_i - 1)$ e $p_M$ è l'$M$-esimo numero primo. Questo risultato vale per ogni $c \ge 1$ e $k_i \ge 2$.
• Riduzione alla Colorazione degli Archi: Il documento distingue la colorazione dei vertici dalla colorazione degli archi sullo stesso grafo ospite. Stabilisce una riduzione esatta per il numero di Ramsey coprimo degli archi $R_{cop}^{edge}$ ai numeri di Ramsey classici dei grafi completi $R_{cl}$:
  $$R_{cop}^{edge}(k_1, \dots, k_c) = p_{R_{cl}(k_1, \dots, k_c) - 1}$$
  Ciò dimostra che i valori coprimi degli archi non sono nuove costanti aritmetiche, ma sono numeri di Ramsey classici visti attraverso una mappa di indice primo.
• Soglia Bilanciata a Due Colori: Gli autori affrontano la preoccupazione che la costruzione della limitazione inferiore potrebbe fare affidamento su classi di colore altamente sbilanciate. Dimostrano che per il caso diagonale a due colori, la soglia bilanciata (dove le dimensioni delle classi di colore differiscono al più di 1) è identica alla soglia illimitata: $L_{bal}(k; 2) = p_{2k-2} - 1$. Ciò è ottenuto tramite una partizione deterministica bin-primi e una debole disuguaglianza di gap di indice primo ($2p_m < p_{2m} < 3p_m$).
• Bilanciamento Multicolore e Casi Limite:
  • Per $c \ge 3$, la soglia bilanciata non è esatta per piccoli $k$ ma diventa esatta per tutti i $k$ sufficientemente grandi (esattezza eventuale), dimostrata tramite un argomento di tipo Hall e stime di Selberg–Delange.
  • Il documento analizza gli intervalli traslati $\{m+1, \dots, m+n\}$. Senza il vertice universale 1 e la cricca iniziale dei primi, la formula esatta fallisce e la soglia dipende dalle strutture locali dei fattori primi.
• Primitiva Algoritmica: Viene proposta una primitiva di estrazione di certificati in tempo polinomiale per verificare se un dato grafo ammette un certificato di disgiunzione dei supporti. Se verificato, la soglia di Ramsey e le colorazioni estreme sono determinate senza ricerca.

Significato e Ambito
Il documento rivendica una soluzione completa per il problema della colorazione dei vertici sul grafo coprimo degli interi, sostituendo ricerche computazionali su larga scala (ad esempio, codifiche SAT con milioni di clausole) con un piccolo certificato esplicito di indice primo.

• Intuizione Strutturale: Il lavoro evidenzia che la rigidità aritmetica del grafo coprimo (controllata dai divisori primi) permette al problema di Ramsey di collassare in un semplice problema di impacchettamento in bin sui primi, a differenza dei difficili problemi di Ramsey classici sugli archi sui grafi completi.
• Chiarimento del Lavoro Precedente: Gli autori chiariscono che i precedenti risultati computazionali sui "numeri di Ramsey coprimi" (specificamente quelli di Towell) si riferivano alla variante di colorazione degli archi, che il documento mostra essere equivalente ai numeri di Ramsey classici. La formula di colorazione dei vertici presentata qui non era presente nelle fonti pubbliche verificate.
• Limitazioni: Il documento afferma esplicitamente di non migliorare i limiti classici di Ramsey sugli archi o di proporre un solver generale assistito dall'IA. I risultati sono specifici per il grafo coprimo e le sue varianti di disgiunzione dei supporti. Il documento identifica problemi aperti riguardanti target di archi non completi (percorsi, cicli), bilanciamento multicolore vincolato dalla densità per piccoli $k$ e soglie di Ramsey per altri grafi aritmetici dove la proprietà di disgiunzione dei supporti non spiega completamente l'adiacenza.

In sintesi, il documento fornisce una prova definitiva ed elementare per una specifica classe di numeri di Ramsey aritmetici, dimostrando che per questo grafo ospite, l'"ostruzione" è una cricca esplicita di primi piuttosto che una configurazione nascosta simile al caso casuale.