Graph Puzzles II.1: Counterexamples to Jain's Second Unit Vector Flows Conjecture

Questo articolo presenta due controesempi alla seconda congettura di Jain sui flussi di vettori unitari, dimostrando che l'assegnazione di valori specifici a punti sulla sfera unitaria richiede l'uso di valori aggiuntivi non previsti dall'ipotesi originale.

L'essenziale

Immagina di avere un globo terrestre (la nostra sfera) e di voler distribuire su di esso dei palloncini colorati (i punti). Ogni palloncino deve avere un "valore" assegnato, come se fosse un numero su un termometro.

La sfida, proposta dal matematico K. Jain, era questa:

1. Il globo: Devi posizionare i palloncini in modo che se ne prendi tre che formano un triangolo perfetto su una linea curva del globo (un "cerchio massimo", come l'equatore), la somma dei loro valori sia zero.
2. L'opposto: Se un palloncino ha valore +3, quello esattamente dall'altra parte del globo deve avere valore -3.
3. Il limite: Jain pensava che fosse possibile farlo usando solo numeri piccoli, tra -4 e +4.

Se questo fosse stato vero, avrebbe risolto un mistero matematico enorme e vecchio di 70 anni (la congettura di Tutte sui flussi 5), che riguarda come si possono "colorare" o "fluire" le reti stradali senza creare ingorghi.

Cosa ha scoperto Nikolay Ulyanov?

Nikolay, l'autore di questo articolo, ha detto: "Aspetta, Jain si è sbagliato!".

Ha costruito due "trappole" geometriche, ovvero due modi specifici di posizionare i palloncini sulla sfera, che hanno dimostrato che i numeri da -4 a +4 non bastano. Per risolvere questi puzzle, sei costretto a usare il numero 5 (o -5).

Ecco come funziona con due metafore semplici:

1. L'Esperimento del "Globo Espanso" (Il primo controesempio)

Immagina di prendere un dodecaedro (un dado a 12 facce) e di trasformarlo in una sfera piena di punti.

• L'idea: Ulyanov ha preso i punti originali e ne ha aggiunti altri, creando una rete complessa di 50 punti.
• Il problema: Quando hai tutti questi punti collegati tra loro, le regole matematiche diventano così rigide che i numeri piccoli (fino a 4) si "ingarbugliano". È come se avessi un puzzle dove i pezzi da 1 a 4 non si incastrano mai perfettamente; ti manca sempre un pezzetto.
• La soluzione: Per far quadrare i conti, devi introdurre un nuovo pezzo: il 5. Senza il 5, il puzzle non si chiude.

2. L'Esperimento della "Ricetta Matematica" (Il secondo controesempio)

Questa volta, invece di espandere un dado, Ulyanov ha usato una "ricetta" basata su radici quadrate e numeri strani (come la radice di 3).

• L'idea: Ha generato 36 punti seguendo una formula precisa, come se stesse creando un nuovo tipo di cristallo.
• Il risultato: Anche qui, quando ha provato a mettere i numeri da -4 a +4, il computer ha gridato "Impossibile!". Le equazioni non tornavano.
• La prova: Ha usato un supercomputer (un risolutore SAT) che ha provato miliardi di combinazioni in pochi secondi e ha confermato: "Non esiste nessun modo per farlo con numeri piccoli. Devi usare il 5".

Perché è importante?

Pensa a questo come a un gioco di logica.

• Jain aveva detto: "Potete risolvere questo gioco usando solo le carte da 1 a 4".
• Ulyanov ha risposto: "No, ecco due livelli del gioco che sono impossibili da completare senza la carta 5".

Questo non significa che il gioco di Jain sia "sbagliato" in senso assoluto, ma significa che la sua ipotesi specifica (che bastassero i numeri fino a 4) è falsa.

Cosa significa per il futuro?

1. Il mistero di Tutte: Poiché la congettura di Jain era un pezzo fondamentale per provare la congettura di Tutte (sui flussi 5), ora gli matematici devono ripensare la strategia. Non possono più contare su quel "ponte" matematico.
2. Nuove domande: Ulyanov si chiede: "Esistono trappole ancora più difficili che richiedono il numero 6 o 7?" Finora, il 5 è il massimo che serve, ma non è detto.
3. Il lavoro non è finito: Anche se questo "ponte" è crollato, gli scienziati stanno cercando di costruire un nuovo ponte, forse usando punti sulla sfera con proprietà speciali, per provare comunque la congettura di Tutte.

In sintesi:
Questo paper è come se un architetto avesse detto: "Ho progettato un ponte che regge con mattoni piccoli". Un altro architetto (Ulyanov) è arrivato, ha costruito due modelli in scala e ha detto: "Guarda, questi due modelli crollano se usi solo mattoni piccoli; ti serve un mattone più grande (il 5) per tenerli in piedi". Ora tutti devono ripensare come costruire il ponte finale.

Sommario tecnico

1. Il Problema e il Contesto

Il lavoro si inserisce nel campo della teoria dei grafi e della topologia combinatoria, focalizzandosi sui flussi a vettori unitari e sulla congettura di Tutte sui flussi 5.

• Definizioni chiave:
  • Un flusso a vettori unitari 3D su un grafo $G$ assegna a ogni spigolo un vettore di norma 1 nello spazio $\mathbb{R}^3$ (punti sulla sfera unitaria $S^2$).
  • Congettura 1.1 (Jain): Ogni grafo senza ponti (bridgeless) ammette un flusso a vettori unitari 3D.
  • Congettura 1.2 (Jain, $S^2$ nz5-flow): Esiste una mappa $q: S^2 \to \{-4, -3, -2, -1, 1, 2, 3, 4\}$ tale che:
    1. I punti antipodali hanno valori opposti ($q(-x) = -q(x)$).
    2. La somma dei valori di qualsiasi tre punti equidistanti su un cerchio massimo è zero.
  • Implicazione: Se entrambe le congetture fossero vere, implicherebbero la famosa Congettura di Tutte (1954), che afferma che ogni grafo cubico senza ponti ammette un flusso intero non nullo 5 (nz5-flow).

L'obiettivo del paper è testare la validità della Congettura 1.2. Se questa fallisce, il collegamento logico per dimostrare la congettura di Tutte tramite flussi a vettori unitari viene meno.

2. Metodologia

L'autore utilizza un approccio computazionale rigoroso basato sulla soddisfacibilità booleana (SAT) per verificare l'esistenza di etichettature valide su sottoinsiemi finiti della sfera $S^2$.

• Costruzione di controesempi: L'obiettivo è trovare sottoinsiemi finiti di punti su $S^2$ per cui è impossibile assegnare valori nell'insieme $\{-4, \dots, 4\}$ rispettando i vincoli di somma zero su cerchi massimi e antipodalità. Se un tale insieme richiede necessariamente il valore $\pm 5$, allora non esiste un flusso nz5, ma solo un flusso nz6.
• Codifica SAT:
  • Per ogni punto (rappresentante antipodale), vengono introdotte variabili booleane corrispondenti ai possibili valori di etichetta.
  • Vengono imposti vincoli "esattamente uno" (uno solo dei valori possibili è scelto), vincoli di antipodalità e vincoli di somma zero per le terne di punti su cerchi massimi.
  • Il problema viene convertito in una formula CNF (Conjunctive Normal Form) e risolto utilizzando il solver PicoSAT/pycosat.
• Verifica Formale: Per garantire l'assenza di errori numerici, le costruzioni sono state verificate anche utilizzando il teorema prover Lean 4 con la tattica bv_decide.
• Precisione Numerica: Viene utilizzata una tolleranza $\epsilon = 10^{-7}$ per l'identificazione dei punti e la rilevazione delle terne, con validazione incrociata tramite aritmetica esatta.

3. Contributi Chiave e Risultati

Il paper presenta due controesempi concreti che confutano la Congettura 1.2 di Jain.

Controesempio 1: Espansione a 50 punti dell'Icosidodecaedro

• Costruzione: Si parte dall'insieme di 30 punti dell'icosidodecaedro (un solido archimedeo). Per ogni punto, si considera un piccolo cerchio equidistante. Si intersecano i cerchi corrispondenti a coppie di punti dell'icosidodecaedro distanti $2\pi/5$ sulla sfera.
• Risultato: Si ottiene un insieme di 50 punti con 40 terne su cerchi massimi.
• Analisi Grafica: Quotientando per gli antipodi, la struttura corrisponde a una combinazione del Grafo di Petersen e di una scala di Möbius a 10 vertici.
• Verifica: La formula SAT risultante (200 variabili, 19.765 clausole) è insoddisfacibile. Ciò dimostra che non esiste un'etichettatura con valori in $\{-4, \dots, 4\}$. È necessario l'uso dei valori $\pm 5$ (flusso nz6).

Controesempio 2: Costruzione a 36 punti basata sull'aritmetica delle radici quadrate

• Costruzione: Si generano coordinate basate su combinazioni lineari di radici quadrate ($\sqrt{1}, \sqrt{3}$) con parametri specifici ($v_1=1, v_2=3, w=2$). Si cercano terne che soddisfino l'equazione della sfera unitaria.
• Riduzione: Dopo aver identificato tutte le terne su cerchi massimi e rimosso iterativamente i punti che appartengono a meno di due terne (per garantire connettività e robustezza), si arriva a un sottoinsieme minimo.
• Risultato: Un insieme di 36 punti con 13 terne.
• Verifica: La formula SAT (144 variabili, 6.710 clausole) è insoddisfacibile per i valori $\{-4, \dots, 4\}$. Tuttavia, è soddisfacibile per l'insieme $\{-5, \dots, 5\}$, confermando la necessità di un flusso nz6.

4. Significato e Implicazioni

• Confutazione della Congettura 1.2: Il lavoro dimostra definitivamente che la Congettura 1.2 di Jain è falsa. Non esiste una mappa universale da $S^2$ a $\{-4, \dots, 4\}$ che soddisfi le condizioni geometriche richieste.
• Impatto sulla Congettura di Tutte: Poiché la Congettura 1.2 è falsa, la strategia di combinare le due congetture di Jain per provare la congettura di Tutte sui flussi 5 (nz5) non è valida nella sua formulazione originale. Questo suggerisce che se la congettura di Tutte è vera, la sua dimostrazione non può passare attraverso questo specifico meccanismo di mappatura geometrica su $S^2$ con valori limitati a 4.
• Domande Aperte:
  • È possibile trovare insiemi che richiedano valori $\pm 6$ o superiori?
  • Qual è il più piccolo controesempio possibile?
  • Esiste un sottoinsieme (forse infinito o con coordinate algebriche specifiche) che possa ancora salvare l'idea per la congettura di Tutte?
• Osservazione sui Flussi Modulo: L'autore nota che, nei suoi esperimenti, non c'è stata differenza tra flussi non nulli $k$ e flussi non nulli modulo $k$ in termini del valore minimo $k$ richiesto, un fenomeno che merita ulteriore indagine teorica.

In sintesi, il paper fornisce una prova computazionale rigorosa che i vincoli geometrici imposti dalla Congettura 1.2 sono troppo restrittivi per essere soddisfatti con un insieme di valori limitato a $\pm 4$, costringendo a riconsiderare l'approccio geometrico alla congettura di Tutte sui flussi 5.