Il problema Hadwiger-Nelson è forse uno dei più conosciuti nel campo della geometria discreta. Si tratta della seguente domanda: qual è il numero minimo di colori che occorrono per dipingere l’aereo, in modo tale che sempre, quando si prendono due punti qualsiasi, distanti tra loro una unità, siano sempre stati dipinti con colori diversi? Anche se è una domanda apparentemente innocente, è rimasta senza risposta per più di 70 anni. Tuttavia, grazie agli strumenti di machine learning, sono stati compiuti recenti progressi nella sua comprensione.
Finora è noto che il numero di colori necessari può essere cinque, sei o sette. Per studiare il numero minimo di colori necessari è sufficiente trovare specifiche configurazioni di punti sul piano che non possono essere dipinti con un numero – chiamiamoli n – di colori e soddisfano la proprietà indicata. Quindi, sappiamo che abbiamo bisogno di più, almeno n+1 colori per dipingere l’intero piano – che include quello specifico disegno – se vogliamo che la proprietà sia verificata.
Innanzitutto è facile intuire che occorrono almeno tre colori. Infatti, prendendo una disposizione semplice come quella dei tre vertici di un triangolo equilatero il cui lato misura uno, abbiamo già bisogno di tre colori per colorarli, in modo che non ci siano due vertici adiacenti con lo stesso colore – altrimenti questi punti non soddisferebbero il requisito proprietà desiderata: sarebbero a distanza 1 e avrebbero lo stesso colore.
Affinando questo tipo di argomentazioni, agli inizi degli anni ’60 del secolo scorso, i fratelli Leo e William Moser trovarono una configurazione concreta di soli sette punti del piano che necessita di almeno quattro colori per realizzare la proprietà da noi desiderata, la quale dimostra che il minimo il numero è quattro. Più recentemente, nel 2018, il matematico dilettante Aubrey de Gray ha trovato una configurazione con più di 1.000 punti sul piano in cui era necessario utilizzare almeno cinque colori affinché fosse soddisfatta la condizione desiderata.
Inoltre, è noto che il numero di colori non può essere superiore a sette, perché conosciamo le strategie per colorare l’aereo con questi colori che raggiungono il nostro obiettivo. Ad esempio, basta prendere una tassellatura a nido d’ape e dipingere un esagono di un colore e i sei adiacenti di colori diversi. Poiché il diametro di ciascun esagono è inferiore a ½, due punti qualsiasi a distanza cadono sempre in esagoni diversi e adiacenti, quindi dipinti di colore diverso.
Ma questo non risolve il mistero, potrebbe esserci un’altra colorazione, che ancora non conosciamo, che richiede meno colori e soddisfa comunque la proprietà. Quindi la risposta potrebbe essere cinque, sei o sette e, al momento, nessuno sa come risolvere questo enigma.
Per far avanzare ulteriormente la ricerca, una strategia comune in matematica è imporre vincoli più deboli e risolvere il problema risultante. Questo spesso ci consente di trovare approcci per risolvere la domanda originale. Nel nostro caso, per studiare il problema debole di Hadwiger Nelson, analizziamo cosa succede se permettiamo che alcuni dei punti dipinti con lo stesso colore si trovino a distanza diversa da uno. Per fare ciò, introduciamo la nozione di configurazione valida di una colorazione del piano di n colori, con distanze (d1, d2, … dn) associate a ciascun colore.
Ad esempio, se n=4, i colori sono blu, verde, giallo e arancione, e le distanze 1,5 –associato al colore blu–, 0,2 –al verde–, 1 –al giallo–, 3,7 –all’arancio– , una configurazione valida con questi valori è un insieme di punti in cui ogni coppia di punti colorati con lo stesso colore si trova ad una distanza maggiore della distanza associata a quel colore. Nell’esempio, non possono esserci due punti blu a una distanza inferiore a 1,5 o due punti verdi a una distanza inferiore a 0,2.
Pertanto, trovare una configurazione valida di sei colori con distanze associate (1,1,1,1,1,1) significherebbe dimostrare che la risposta al problema di Hadwiger-Nelson è, al massimo, sei. Trovare una configurazione a cinque colori e con distanze (1,1,1,1,1) sarebbe ancora meglio, poiché risolverebbe completamente il problema. E, anche se meno ambiziosi, trovare configurazioni di questo tipo ci permette di aumentare la nostra conoscenza del problema generale.
Recentemente, un team di ricercatori dello Zuse Institute Berlin (ZIB) e della Technische Universität Berlin (TU Berlin) ha fatto progressi in questa direzione. Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel e Max Zimmer hanno trovato una configurazione valida di sei colori (1,1,1,1,1,d), dove il valore di D È compreso tra 0,354 e 0,657. In altre parole, i punti colorati con i primi cinque colori mantengono la condizione con una distanza unitaria, mentre per il sesto colore la condizione è rilassata: possono esserci una coppia di punti dipinti con questo colore a una distanza minore, compresa tra 0,354 e 0,657 . Questo risultato migliora i risultati precedenti del 1996, ampliando il margine di scelta possibile D.
Ma ciò che è veramente interessante è anche il ruolo che il machine learning ha avuto nell’ottenimento di questo risultato. La sua idea, in generale, è stata quella di addestrare una rete neurale a trovare rappresentazioni che soddisfino le condizioni desiderate, cercando di sfruttare il valore di D era il più possibile. Questo tipo di reti neurali non sono in grado di risolvere esattamente il problema, ma ottengono invece proposte di soluzioni approssimate, testando un numero enorme di combinazioni possibili, compito irraggiungibile per l’uomo.
La rete neurale funziona quindi come un “oracolo approssimativo”, ed è compito dei ricercatori interpretare le informazioni generate e trasformare questo percorso di esplorazione in una possibile soluzione. Con queste tecniche gli autori sono riusciti ad ottenere diverse costruzioni che migliorano tutte quelle finora conosciute. Ad esempio, hanno costruito una tassellatura periodica (nell’immagine) che utilizza sei colori, in cui il sesto colore, il rosso, è quello che soddisfa le condizioni più permissive.
Questo tipo di tecniche computazionali sono molto promettenti ed è possibile che in futuro permettano di affrontare altri problemi oggi inavvicinabili, come, ad esempio, lo studio dello stesso problema nello spazio – anziché nell’ambiente aereo -, ovvero il problema di Hadwiger-Nelson nel suo insieme.
Juanjo Rué È professore a contratto del Dipartimento di Matematica dell’ Università Politecnica della Catalogna (UPC), membro della Istituto di matematica UPC (IMTech) e ricercatore assegnato a Centro di ricerca matematica (CRM).
Agata A. Timón G Longoriacoordinatore del Unità di Cultura Matematica dell’ICMAT.
Caffè e teoremi è una sezione dedicata alla matematica e all’ambiente in cui nasce, coordinata dall’Istituto di Scienze Matematiche (ICMAT), in cui ricercatori e membri del centro descrivono gli ultimi progressi di questa disciplina, condividono punti di incontro tra la matematica e gli altri ambiti sociali ed espressioni culturali e ricordano coloro che ne segnarono lo sviluppo e seppero trasformare il caffè in teoremi. Il nome evoca la definizione del matematico ungherese Alfred Rényi: “Un matematico è una macchina che trasforma il caffè in teoremi”.
Redazione, traduzione e coordinamento: Agata Timón García-Longoria. È coordinatrice del Unità di Cultura Matematica dell’Istituto di Scienze Matematiche (ICMAT)