Don't take life too seriously: it's just a temporary situation

Il teorema dei 4 colori afferma che 4 colori bastano per colorare qualsiasi mappa sul piano o sulla sfera, in modo che due regioni confinanti (non in un singolo punto) siano di colori diversi.

 

La storia del teorema inizia nel 1852, quando Francis Gutrie (Londra, 22/1/1831 – Claremont, Cape Town, 19/10/1899) nel colorare una mappa delle contee dell’Inghilterra si pose il problema se 4 colori potessero bastare per qualsiasi mappa; propose il problema a suo fratello Frederick e questi lo passò al suo maestro Augustus De Morgan (27/6/1806 – 18/3/1871). De Morgan dimostrò che non è possibile disegnare 5 regioni sul piano, in modo che ciascuna condivida una parte di confine con tutte le altre, ma non risolse il problema della colorazione delle mappe e menzionò il problema a Sir Williams Rowan Hamilton (4/8/1805 – 2/9/1865) in una lettera del 23/10/1852.

Nel 1854 il problema fu proposto sulla rivista (letteraria) inglese The Athenaeum e ivi riproposto da De Morgan nel 1860, ma non suscitò grande interesse.

Il problema acquistò notorietà solo il 13/6/1878, quando Arthur Caley (Richmond, UK, 16/8/1821 – Cambridge, UK, 26/1/1895) chiese ai membri della London Mathematical Society di risolverlo, dichiarando di non essere riuscito nell’impresa.

 

Alfred Bray Kempe (Kensington, Londra, 6/7/1849 – Londra, 21/4/1922) pubblicò nel 1879 una dimostrazione, semplice e ingegnosa, che convinse tutti, anche perché nel frattempo l’evidenza sperimentale aveva mostrato che era sempre possibile colorare una mappa con 4 colori, e che gli valse la nomina a Fellow della Royal Society.

Solo nel 1890 Percy John Heawood (Newport, Inghilterra, 8/9/1861 – Durham, Inghilterra, 24/1/1955) scoprì un sottile ma fatale errore nella dimostrazione di Kempe, passato sino a quel momento inosservato. Heawood modificò la dimostrazione di Kempe, arrivando a mostrare che 5 colori sono sufficienti, ma non riuscì a correggere l’errore e il problema si riaprì.

 

Anche Peter Guthrie Tait (28/4/1831 – 4/7/1901) aveva pubblicato nel 1880 una dimostrazione del teorema, che fu demolita 11 anni dopo da Julius Petersen (Sorø, Danimarca, 16/6/1839 – Copenhagen, 5/8/1910). L’errore in questo caso era più evidente, ma nessuno doveva averla considerata con molta attenzione, perché tutti sapevano dell’esistenza di un’altra dimostrazione (quella di Kempe), precedente, completamente diversa e valida.

Tait aveva stabilito una corrispondenza tra le mappe e i grafi planari (ossia disegnabili sul piano senza incroci) trivalenti (ossia con ogni punto connesso ad altri 3) e privi di un “istmo”, ossia di un arco che non può essere rimosso senza dividere il grafo in due parti disgiunte. Il matematico aveva mostrato che una mappa è colorabile con 4 colori se e solo se gli archi del grafo corrispondente possono essere colorati con 3 colori in modo che in ogni nodo concorra un arco di ciascun colore.

Il primo esempio di grafo trivalente non colorabile con 3 colori fu pubblicato da Petersen nel 1898 e da allora è noto come “grafo di Petersen”. Questo grafo, mostrato di seguito, non essendo planare, non costituisce un controesempio all’ipotesi di Tait.

 

Grafo di Petersen 

 

Tait aveva dimostrato che se un grafo trivalente ha un circuito hamiltoniano, ossia un percorso che passa esattamente una volta da tutti i nodi, è colorabile con 3 colori e dava per scontato che un percorso del genere esistesse in ogni grafo trivalente planare e privo di istmo.

Questa ipotesi però andava dimostrata per rendere valida l’intera prova e Tait omise di farlo. In realtà non avrebbe potuto, perché era falsa!

Nel 1946 William Thomas Tutte (14/5/1917 – 2/5/2002) pubblicò un controesempio, ossia un grafo planare trivalente privo di circuito hamiltoniano. Il grafo di Tutte era colorabile con 3 colori e non costituiva un controesempio al teorema dei 4 colori: l’esistenza di un circuito hamiltoniano si era rivelata condizione sufficiente, ma non necessaria perché un grafo fosse colorabile con 3 colori.

La possibilità di colorare un grafo planare trivalente con 3 colori è equivalente al teorema dei 4 colori, ma venne dimostrata solo a partire da questo, non indipendentemente.

 

Nel 1922 Philip Franklin (5/10/1898 – 27/1/1965) dimostrò che è possibile colorare con 4 colori ogni mappa con non più di 26 regioni, indicando la strada che avrebbe in seguito condotto al successo: dimostrare che ogni mappa contiene almeno una configurazione di un certo insieme di regioni che è riducibile, ossia riconducibile a una configurazione con meno regioni colorabile con 4 colori, che può poi essere sostituita con la configurazione originale lasciando invariato il contorno. Quindi si può ridurre la configurazione originale, eliminando regioni sino ad arrivare a una configurazione colorabile, per poi ripristinare le regioni eliminate. Kempe aveva fallito, perché aveva usato un insieme di configurazioni troppo piccolo, con 3 soli elementi, ma Franklin suggerì che forse con un insieme di dimensioni maggiori di configurazioni riducibili si poteva dimostrare che ogni mappa deve contenere una configurazione dell’insieme.

 

Nel 1950 Heinrich Heesch (25/6/1906 – 26/7/1995) scoprì un metodo per dimostrare la riducibilità di varie configurazioni, ma non arrivò alla dimostrazione del teorema, perché stimò che un insieme minimo di configurazioni inevitabili dovesse contenere circa 10000 configurazioni: decisamente troppe per procedere manualmente.

 

Il teorema dei 4 colori venne finalmente dimostrato nel 1976 da Kenneth Appel e Wolfgang Hachen con un monumentale lavoro: la dimostrazione è lunga 900 pagine, richiese 1000 ore di calcoli da parte dei più potenti elaboratori dell’epoca per considerare circa 100000 configurazioni di mappe e non può realmente essere verificata da un essere umano, perché la verifica manuale dei vari casi richiederebbe più di una vita. Di fatto i due dimostrarono che esiste un insieme di 1936 (numero poi ridotto a 1405) configurazioni inevitabili e che ciascuna è riducibile.

Molti matematici storsero il naso, alcuni non la considerarono neppure valida, ma la dimostrazione segnò l’ingresso trionfale dei calcolatori nella matematica.

La dimostrazione si basa sul fatto che una mappa che richieda 5 colori dovrebbe contenere una configurazione di un insieme “inevitabile”, ciascuna delle quali però è anche “riducibile”, ossia permette di ricolorare l’intera mappa con un colore in meno.

Nel 1994 Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas trovarono una prova analoga, ma che richiedeva l’esame di un numero minore di configurazioni; grazie anche ai progressi dell’elettronica, la verifica richiede ora solo poche ore su un comune calcolatore personale. La verifica con programmi e macchine differenti ha inoltre convinto gli scettici della correttezza della prova originale.

A tutt’oggi molti continuano a ricercare, per ora invano, una dimostrazione più semplice, umanamente verificabile.

 

Il teorema è strettamente connesso alla congettura di Hadwiger, ancora irrisolta.

 

Le estensioni a mappe infinite sono rese semplici dal teorema di De Buijn – Erdös (1951), che afferma che se ogni sottografo finito di una grafo infinito è colorabile con n colori, la proprietà vale anche per l’intero grafo.

 

Dopo questa lunga ma inevitabile premessa, arriviamo ai numeri di Heawood.

Nel 1890 Percy John Heawood (Newport, Inghilterra, 8/9/1861 – Durham, Inghilterra, 24/1/1955) suggerì che il numero di colori necessari per colorare una mappa su una superficie chiusa e orientabile di genus n (in pratica, un toro con n fori) sia Formula di Heawood per il numero di colori necessari, per n > 0, e i numeri di questa forma sono da allora chiamati “numeri di Heawood”.

Più correttamente, n è il numero massimo di curve chiuse che si possono tracciare sulla superficie, senza dividerla in regioni separate o, se preferite, il numero di tagli lungo linee chiuse che si possono separare senza dividere la superficie in parti separate. Questa formulazione permette di tenere conto anche di superfici come la bottiglia di Klein, che non delimitano regioni di spazio.

 

La tabella seguente mostra i primi valori.

n

Numero di Heawood

0

4

1

7

2

8

3

9

4

10

5

11

6

12

7

12

8

13

9

13

10

14

11

15

12

15

13

16

14

16

15

16

16

17

17

17

18

18

19

18

20

19

 

Heawood dimostrò che il numero da lui indicato è sufficiente per n > 0; (per n = 0 abbiamo il teorema dei 4 colori). Nel caso n = 1, ossia per il toro, la congettura indica 7 come numero di colori sufficienti ed Heawood dimostrò che sono anche necessari, perché si può costruire una mappa su un toro, nella quale 7 regioni confinano ciascuna con tutte le altre.

La figura seguente illustra una possibile costruzione, partendo da un rettangolo suddiviso come indicato.

 

Mappa che mostra che 7 colori sono necessari sul toro

 

Bisogna arrotolare il rettangolo, unendo il bordo superiore a quello inferiore, in modo da costruire un tubo. A questo punto bisogna unire le estremità destra e sinistra del tubo, costruendo una ciambella; l’operazione è un po’ complessa partendo da un foglio di carta e anche più difficile con un foglio di gomma, ma la topologia si disinteressa delle questioni pratiche e prevede l’utilizzo di materiali ideali, infinitamente deformabili.

Al termine dell’operazione, ciascuna delle 7 bande diagonali confinerà con altre due lateralmente, due lungo il bordo superiore della striscia e altre due lungo quello inferiore. Per esempio, la regione numero 7 alla fine confina con le regioni 4 e 5 lungo quello che nel rettangolo è il suo lato superiore e con le regioni 2 e 3 lungo il suo lato inferiore. La figura seguente mostra il risultato, col toro proiettato su un piano e la proiezione “aperta” come un libro.

 

Mappa che mostra che 7 colori sono necessari sul toro

 

 

Lajos Szilassi costruì nel 1977 un poliedro, topologicamente equivalente a un toro, con 7 facce esagonali (non convesse), ciascuna con uno spigolo in comune con tutte le altre, che vedete nella figura seguente.

 

Poliedro di Szilassi

 

 

L’unico altro poliedro noto con questa proprietà è il tetraedro, ossia la piramide a base triangolare.

Partendo dalla formula di Eulero, si dimostra che per un poliedro nel quale ogni faccia ha uno spigolo in comune con tutte le altre deve valere h = (f – 4) * (f – 3) / 12, dove f è il numero di facce e h il numero di fori; il tetraedro corrisponde alla soluzione f = 4, h = 0 e il poliedro di Szilassi al caso f = 7, h = 1. L’equazione ha soluzioni intere se e solo se f diviso 12 dà resto 0, 3, 4 o 7; la successiva soluzione corrisponderebbe al caso f = 12, h = 6, ossia a un poliedro con 12 facce, 6 fori, 44 vertici e 66 spigoli. Non è noto se tale mostruosità esista, molti esperti ne dubitano.

 

Heawood non riuscì a dimostrare che per n > 1 il numero di colori indicato dalla formula fosse realmente necessario e questa affermazione divenne quindi nota come “congettura di Heawood”. Lothar Heffter dimostrò che la congettura è vera per n < 7 e in alcuni altri casi e nel 1967 Gerhard Ringel e J.T.W. Youngs completarono la dimostrazione che è effettivamente vera per tutti i valori di n maggiori di zero.

 

Sono state esaminate varianti al problema di base dei quattro colori, la più semplice delle quali è il “problema dell’impero”: stabilire il numero minimo di colori per colorare una mappa (sul piano o sulla sfera) di imperi, ciascuno suddiviso in n regioni distinte. Potendo spezzare ogni regione in parti non contigue, aumenta il numero di confini possibili e quindi il numero di colori.

Heawood dimostrò che 6n colori sono sufficienti per n > 1 (per n = 1 abbiamo il problema dei 4 colori) e necessari per n = 2, costruendo una mappa che ne richiede 12, e propose la congettura che 6n fossero sempre necessari.

Nel 1980 Herbert Taylor costruì mappe che richiedevano 18 colori con n = 3 e 24 con n = 4 e dimostrò che se gli imperi sono disegnati su un toro, 6n + 1 colori sono necessari e sufficienti.

Finalmente nel 1984 B. Jackson e G. Ringel dimostrarono che 6n colori sono necessari sul piano e sulla sfera.

E’ buffo che il problema sia stato completamente risolto, sia per semplici stati che per imperi, prima su una superficie complicata come quella toroidale e solo dopo per il piano e la sfera.

 

Un’altra variante, proposta nel 1959 da Gehrard Ringel, è il “problema Terra – Luna”, ovvero il numero di colori necessari per colorare due mappe, supponendo che ogni stato sulla Terra abbia un possedimento sulla Luna. La soluzione del problema dell’impero dimostra che 12 colori sono sufficienti, tuttavia il fatto che le due parti di ogni “impero” siano confinate su due superfici disgiunte potrebbe far risparmiare colori.

Ringle costruì una mappa che richiedeva 8 colori e quando nel 1962 Joseph Battle, Frank Harary e Yukihiro Kodama dimostrarono che non si poteva costruire una mappa Terra – Luna con 9 regioni, nella quale ogni regione confinasse con tutte le altre (su almeno una delle due superfici), molti, tra i quali lo stesso Ringle, si convinsero che 8 colori fossero sufficienti. Nel 1974 però Tom Sulanke costruì una mappa che richiede 9 colori.

A tutt’oggi non è noto se esistano mappe che richiedano 10, 11 o 12 colori.

 

Il problema si pone solo in due dimensioni perché non può esistere un analogo tridimensionale del teorema dei 4 colori; sono infatti possibili configurazioni di solidi che richiedono un numero grande a piacere di colori: pensate per esempio a un groviglio di cordicelle, intrecciate in modo che ciascuna tocchi tutte le altre.

Bruce Reed e David Allwright dimostrarono nel 2008 che può servire un numero arbrariamente grande di colori anche se i solidi sono limitati a parallelepipedi, con spigoli paralleli agli assi cartesiani.

 

Una variante ancora in attesa di soluzione, nota come “problema di Hadwiger – Nelson”, perché discusso da Hugo Hadwiger e proposto da Edward Nelson nel 1950, chiede quale sia il minimo numero di colori necessari per colorare l’intero piano, in modo che due punti a distanza 1 siano di colori diversi.

Il grafo seguente, noto come “grafo di Moser”, con 7 punti e 11 distanze unitarie, mostra che 4 colori sono necessari.

 

Grafo di Moser 

 

D’altra parte la suddivisione del piano in esagoni di diametro unitario, colorati come nella figura seguente, mostra che 7 colori sono sufficienti.

 

Colorazione del piano che mostra come 7 colori siano sufficienti 

 

Questo problema può essere formulato in 3 o più dimensioni, ma su tali varianti sa sa ben poco. In n dimensioni un grafo analogo a quello di Moser, con punti ai vertici di (iper)tetraedri, mostra che n + 2 colori sono necessari e una tassellatura tramite (iper)cubi dimostra che 3n – 2n – 1 colori sono sufficienti, ma nessuno è riuscito a colmare il divario (crescente col numero di dimensioni) tra questi valori. In 3 dimensioni è stato dimostrato che 6 colori sono necessari e 15 sufficienti.

 

Trovo poco cortese che i cartografi, dopo aver proposto un problema che ha fatto penare i matematici per un secolo, si siano poi disinteressati della soluzione. Il problema dei 4 colori e le sue varianti, infatti, interessano solo i matematici, ma non hanno mai seriamente interessato i cartografi. I libri di cartografia di solito non menzionano la questione, usare un colore in più non è certo un problema in tempi di cartografia digitale e le mappe che usano solo 4 colori sono rare (e secondo alcuni esperti, quando utilizzano 4 colori, potrebbero in realtà essere colorate con 3). Trovare la colorazione col numero minimo di colori può richiedere una certa pazienza o l’uso di programmi per calcolatori e nessuno se ne prende la briga.

In cartografia, inoltre, vi sono alcuni problemi pratici, in quanto le suddivisioni politiche, arbitrariamente tracciate dagli uomini, creano situazioni alle quali il teorema dei 4 colori non si applica, perché vari stati sono formati da parti non contigue (e si ricade nel problema degli imperi): l’Alaska è separata dal resto degli Stati Uniti, il comune di Campione non è contiguo al resto dell’Italia.

Vi sono poi casi di 4 stati con un punto in comune, come il classico esempio di Utah, New Mexico, Arizona e Colorado negli USA; due stati con un solo vertice in comune potrebbero essere colorati con lo stesso colore, ma i cartografi preferiscono evitare di farlo, per maggiore chiarezza.

Bibliografia

  • Appel, Kenneth;  Haken, Wolfgang;  "Every Planar Map is Four Colorable" in Mathematical Solitaires and Games, Baywood Publishing Co., di Benjamin L. Farmingdale, Schwartz, 1968.
  • Appel, Kenneth;  Haken, Wolfgang;  "La soluzione del problema dei 4 colori" in Le Scienze, Milano, n. 113, gennaio 1978, pag. 54 – 65.
  • Coxeter, H.M.S.;  "The Mathematics of Map Coloring" in Mathematical Solitaires and Games, Baywood Publishing Co., di Benjamin L. Farmingdale, Schwartz, 1968.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 142, giugno 1980, pag. 108 – 111.
  • Gardner, Martin;  "Giochi matematici" in Le Scienze, Milano, n. 5, gennaio 1969, pag. 91.
  • Gardner, Martin;  Enigmi e giochi matematici 6, Firenze, Sansoni, 1969 -

    Traduzione di Martin Gardner’s New Mathematical Diversions from Scientific American, New York, Simon and Schuster, 1966.

  • Heawood, Percy John;  "Map Colour Theorems" in Quarterly Journal of Pure and Applied Mathematics, n. 24, pag. 332 – 338, 1890.
  • Odifreddi, Piergiorgio;  La matematica del Novecento: dagli insiemi alla complessità, Torino, Einaudi, 2000.
  • Odifreddi, Piergiorgio;  Una via di fuga, Milano, Mondadori, 2011.
  • Pegg, Ed Jr.;  Rodgers, Tom;  Schoen, Alan H.;  Homage to a Pied Puzzler, A.K. Peters, 2009 -

    Una sorta di “atti del convegno” relativi al settimo “Gathering for Gardner”, del 2006. Splendida raccolta di problemi, centrati sul tema del convegno, ovvero il numero 7.

  • Ringel, Gehrard;  Färbungsprobleme auf Flachen und Graphen, Berlino, Deutsche Verlag der Wissenschaften, 1959.
  • Stewart, Ian;  Professor Stewart’s Cabinet of Mathematical Curiosities, Basic Books, 2009.
  • Wilson, Robin;  Four Colors Suffice, Princeton University Press, 2002 -

    Storia molto ben documentata del teorema dei 4 colori.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.