Lo scorso 11 Aprile, Aubrey de Gray, un biologo appassionato di matematica ricreativa, ha postato su arXiv un articolo dal titolo “The chromatic number of the plane is at least 5” dove descrive la costruzione di un grafo di 1577 vertici con numero cromatico 5. Ci spiega di cosa si tratta Emanuele Munarini, professore di geometria presso il Politecnico di Milano.

Il risultato di Aubrey de Gray dà un forte scossone all’annoso problema di Hadwiger-Nelson (o problema del numero cromatico del piano):

«Quanti colori sono necessari per colorare i punti del piano in modo che due qualsiasi punti a distanza 1 abbiano colori diversi?»

Il problema risale al 1950, quando Edward Nelson, ancora studente all’Università di Chicago, lo formulò esplicitamente per la prima volta, senza però pubblicarlo. Per la pubblicazione, dobbiamo aspettare il 1960 quando Martin Gardner lo divulga nei sui “Mathematical Games” su Scientific American. In realtà, un problema analogo era già stato preso in considerazione da Hugo Hadwiger in un suo articolo del 1945.

Fin da subito la comunità dei matematici si è appassionata a questo problema ottenendo i primi fondamentali risultati, che hanno costituito quanto si sapeva fino a poco tempo fa. Il primo passo per affrontare il problema della colorazione del piano consiste nell’utilizzare il teorema di De Bruijn-Erdős (1951), secondo il quale il numero cromatico χ(G) di un grafo infinito G (purchè χ(G) sia finito) coincide con il massimo numero cromatico dei sui sottografi finiti. Attenzione, però: la dimostrazione di questo teorema usa l’assioma della scelta.

In questo modo, quindi, possiamo passare dal piano, visto come grafo infinito (dove i vertici sono i punti e i lati sono le coppie di punti a distanza 1), ai suoi  sottografi finiti (unit distance graphs). A questo punto, quindi, si tratta di determinare il massimo valore del numero cromatico dei sottografi del piano. In particolare, se si trova un sottografo G con numero cromatico k, allora il numero cromatico del piano sarà almeno k.

Di conseguenza, l’esistenza di triangoli equilateri implica immediatamente che il numero cromatico del piano non può essere 2, (ossia che il piano non è un grafo bipartito).

Infatti un triangolo (che come grafo è il grafo completo K$$_3$$) non può essere colorato usando solo due colori, ne servono almeno 3. Di conseguenza, il numero cromatico del piano è almeno 3, ma, naturalmente, non è detto che sia esattamente 3. E infatti non è 3, poiché esistono dei sottografi del piano con numero cromatico 4. Un primo esempio è dato dal grafo di Moser (Moser spindle) trovato dai fratelli Leo Moser e William Moser nel 1961:

Grafo di Moser

Questo grafo, formato da sette vertici e da undici lati, è il più piccolo sottografo del piano con numero cromatico 4. Un altro esempio di questo tipo è dato dal grafo di Golomb, trovato da Solomon W. Golomb tra il 1960 e il 1965 (cfr. Soifer 2008, p. 19):

L’esistenza di questi grafi implica che il numero cromatico del piano è almeno 4. Un limite superiore, invece, è stato trovato da John R. Isbell (cfr. Soifer, 2008) utilizzando un’opportuna tassellazione del piano mediante esagoni regolari (di diametro poco inferiore a 1) che può essere colorata con 7 colori.

Colorazione del piano con 7 colori

Abbiamo così che il numero cromatico del piano è necessariamente compreso tra 4 e 7, ossia può essere solo 4, 5, 6 o 7. Questo è quanto si conosceva fin dagli anni ’60 del secolo scorso. Da allora non sono stati fatti molti progressi nella soluzione di questo problema. Poi è arrivato Aubrey de Gray che, con la costruzione del suo grafo, ormai chiamato grafo di de Gray, ha provocato un piccolo terremoto nella comunità matematica, riportando prepotentemente alla ribalta il problema di Hadwiger-Nelson, vecchio di 68 anni.

Amalgamando in modo opportuno numerose copie del grafo di Moser, de Gray costruisce un enorme sottografo del piano formato da 20.425 vertici, con numero cromatico 5. Poi, da questo grafo riesce ad estrarre un grafo un po’ più piccolo formato solo da 1.581 vertici, anch’esso con numero cromatico 5.

Il grafo resta comunque estremamente grosso e poco maneggevole. De Grey, tuttavia, è riuscito a verificare che effettivamente non è colorabile con soli quattro colori mediante l’ausilio del calcolatore. A questo punto, quindi, possiamo dire che il numero cromatico del piano è compreso tra 5 e 7.

L’articolo di de Grey, pubblicato l’11 Aprile 2018, ha scatenato una vera e propria gara per migliorare il risultato ottenuto. Lo stesso de Gray ha posto a Terence Tao, un matematico della University of California di Los Angeles, il problema di trovare il più piccolo dei sottografi del piano con numero cromatico 5, osservando che quel problema sembrava adattarsi molto bene a Polymath, un progetto nato un decina di anni fa ad opera di Timothy Gowers, un matematico dell’Università di Cambridge, con l’obiettivo di incrementare e facilitare le collaborazioni online nell’ambito della ricerca matematica. È nato così l’ambizioso Polymath16 project che si propone la semplificazione dei risultati di de Grey e il loro utilizzo per ottenere ulteriori progressi. E, infatti, i primi risultati non si sono fatti attendere. Immediatamente Dustin Mixon e Boris Alexeev, due matematici dell’Ohio State University, hanno trovato un grafo con 1577 vertici.

Pochi giorni dopo, Marijn Heule, un informatico della University of Texas di Austin, ha trovato un primo grafo di 874 vertici (14 Aprile 2018) e poi un secondo grafo di 826 vertici (16 Aprile 2018). Innfine, il 1° Maggio 2018, Geoffrey Exoo, della Indiana State University di Terre Haute, e Dan Ismailescu, della Hofstra University di Hempstead, hanno postato su arXiv un articolo, intitolato “The chromatic number of the plane is at least 5 – a new proof“, in cui presentano una dimostrazione alternativa a quella di de Gray. In conclusione, il problema di Hadwiger-Nelson resta aperto, ma certamente in poche settimane si sono fatti enormi progressi, più che nei passati 50 anni. Non ci sarebbe da stupirsi se i prossimi giorni ci riserveranno altri colpi di scena che porteranno un po’ più vicini alla soluzione.

Emanuele Munarini