Arlecchino e il problema dei quattro colori

C’era una volta un bambino molto povero che si chiamava Arlecchino e viveva con la sua mamma in una misera casetta. Arlecchino andava a scuola e, per Carnevale, la maestra organizzò una bella festa e propose a tutti i bambini della scuola di vestirsi in maschera.

Tutti i bambini, eccitati, descrivevano i vestiti colorati che avrebbero indossato per l’occasione. Soltanto Arlecchino, solo, in disparte, non partecipava all’entusiasmo generale; zitto zitto, in un angolino, sapeva che la sua mamma era povera e non avrebbe mai potuto comprargli un costume per Carnevale. Ma agli altri bimbi dispiacque vedere Arlecchino tanto triste, così alcuni di loro decisero di portare alla mamma di Arlecchino dei pezzetti di stoffa avanzata dai loro costumi colorati. La mamma lavorò tutta la notte, cucì fra loro tutti i pezzi diversi e ne fece un abito.

Al mattino Arlecchino ebbe un bellissimo costume di colori diversi. Così, alla festa della scuola, fu proprio lui la maschera più bella e più festeggiata, tutto questo grazie all’aiuto dei suoi compagni! La maestra chiese allora ad Arlecchino: “Arlecchino, perché non ringrazi i compagni che ti hanno regalato i pezzetti di stoffa colorati? Sai quanti sono?”

Arlecchino, che già era una mascherina intelligente, sorrise alla maestra e le rispose: “Non lo so signorina, ma di sicuro i miei generosi compagni devono essere stati non più di quattro. Siccome nessuna pezza ne tocca un’altra dello stesso colore, ciò può succedere solo con al più quattro colori. Quattro bastano!”

Arlecchino si riferiva probabilmente al teorema dei quattro colori, il quale afferma che, data qualsiasi suddivisione del piano in regioni contigue che produce una figura chiamata mappa, non più di quattro colori sono necessari per colorare le regioni della mappa in modo tale che due regioni adiacenti non abbiano lo stesso colore. Due regioni sono chiamate adiacenti se condividono un segmento di confine comune che non sia un angolo, dove gli angoli sono i punti condivisi da tre o più regioni. Ad esempio, nella mappa degli Stati Uniti, lo Utah e l’Arizona sono adiacenti, mentre lo Utah e il Nuovo Messico non lo sono, perché condividono un solo punto, che appartiene anche all’Arizona e al Colorado.

Nonostante il riferimento geografico, il teorema non è di particolare interesse per i cartografi, perché nella maggior parte delle carte politiche si utilizzano più di quattro colori e nei libri di cartografia o di storia della costruzione di mappe non si fa cenno a questa proprietà. Per le mappe più semplici bastano addirittura solo tre colori, e un quarto colore diventa necessario solo in casi particolari, come quando in una mappa una regione è circondata da un numero dispari di altre regioni che si toccano reciprocamente. Un’altra considerazione da fare è che i bravi cartografi non hanno le preoccupazioni dei matematici e per loro una buona carta geografica, per essere comprensibile, deve soddisfare un certo gusto estetico e la questione del numero di colori non è fondamentale.

Il problema dei quattro colori fu posto per la prima volta dal matematico e botanico sudafricano Francis Guthrie nel 1852: egli, ancora laureando, era intento a colorare la mappa delle contee inglesi, quando si accorse che erano sufficienti quattro colori differenti per fare in modo che due contee confinanti non avessero lo stesso colore. Suo fratello Friedrick era allora allievo di Augustus De Morgan all’University College di Londra e riportò l’osservazione all’illustre professore, il quale lo stesso giorno (23 ottobre 1852) ne parlò in una lettera a William R.Hamilton a Dublino:

“Un mio studente mi ha domandato oggi di spiegargli il motivo di un fatto che non sapevo essere un fatto e che ignoro tuttora. Egli sostiene che, se una figura viene suddivisa in qualsiasi modo e i compartimenti ottenuti vengono colorati con colori diversi in modo tale che ogni linea di confine comune separi due colori diversi, sono sufficienti quattro colori, non uno di più (…)”.

Francis Guthrie rese pubblica la sua congettura in una lettera che comparve su The Athenaeum il 10 giugno 1854. Brendan D. McKay, dell’Australian National University di Canberra, la riporta in una nota recentemente apparsa su ArXiv:

“Nel colorare le mappe, è preferibile, per il bene della chiarezza, utilizzare il minor numero di colori possibile, e nel contempo non si dovrebbero colorare allo stesso modo due regioni confinanti. Ora, ho scoperto per esperienza diretta che per questo scopo sono necessari e sufficienti quattro colori, ma non sono in grado di provare che ciò sia vero, a meno che il numero totale di divisioni non sia superiore a cinque. Mi piacerebbe vedere (o sapere dove posso trovare) una dimostrazione di questa proposizione apparentemente semplice, che sono sorpreso di non aver mai incontrato in nessuna opera matematica. F.G. “

De Morgan ripropose la questione sullo stesso periodico nel 1860. Un ulteriore precoce riferimento alla questione fu fatto nel 1879 da Arthur Cayley, il quale ne attribuì erroneamente la paternità a De Morgan, inducendo così in errore molti commentatori successivi.

Prima della fine del XIX secolo diversi furono gli annunci della dimostrazione della congettura, ma nessuno resistette alla verifica della comunità scientifica. Per diventare teorema, la congettura ha dovuto attendere più di un secolo, perché il problema dei quattro colori è stato uno dei più interessanti e ardui da risolvere per generazioni di matematici, fino a quando l’avvento dei computer ha consentito il trattamento in tempi ragionevoli di ingenti quantità di dati. In questo lungo periodo i tentativi che si sono susseguiti sono tutti falliti, ma hanno consentito lo sviluppo di nuovi concetti topologici e della teoria dei grafi, segnando anche l’ingresso di complessi algoritmi di calcolo nella dimostrazione dei teoremi, resi implementabili solo con l’aiuto delle macchine. Negli anni ’60 il matematico tedesco Heinrich Heesch fu il primo a usare il computer per trovare la dimostrazione del problema. La sua impostazione, che si sarebbe rivelata fondamentale ai fini dell’impresa, richiedeva tuttavia una potenza di calcolo che le macchine del tempo non erano in grado di assicurare.

Passò solo qualche anno e il teorema dei quattro colori fu dimostrato proprio grazie al computer, ad opera di due matematici dell’Università dell’Illinois, Kenneth Appel and Wolfgang Haken, che vi riuscirono nel 1976, battendo sul tempo altri gruppi di lavoro all’opera in tutto il mondo.

Per formulare correttamente il teorema bisogna tener presente che: a) non si devono considerare gli angoli che appartengono a tre o più regioni, e b) ogni regione deve essere contigua cioè semplicemente connessa, fatto che, nel mondo reale non sempre è vero, perché esistono stati che presentano zone separate dal resto del territorio, come capita per l’Alaska rispetto agli Stati Uniti, il territorio di Kaliningrad rispetto alla Russia, o il Nakchivan rispetto all’Azerbaigian. In questi casi, in cui il colore della zona separata deve essere lo stesso della madrepatria, possono essere necessari più di quattro colori. Ad esempio, la mappa schematica rappresentata in figura, dove le zone A appartengono allo stesso stato, richiede cinque colori.

La dimostrazione di Appel e Haken iniziò provando che il numero infinito di mappe possibili può essere ridotto a un particolare insieme di 1936 configurazioni (più tardi ridotte a 1476), ciascuna delle quali non può essere parte di un controesempio del teorema. Questo insieme è chiamato “insieme inevitabile” (unavoidable set), ed è un insieme di configurazioni tale che una qualsiasi mappa planare (indipendentemente dal fatto che sia o non sia un controesempio) deve contenere almeno un elemento dell’insieme. Qualsiasi mappa può infatti essere ricondotta a un numero finito, sebbene assai elevato, di topologie "notevoli" tramite operazioni che modificano le relative posizioni delle regioni che la costituiscono, ma non le proprietà topologiche della mappa stessa.

Il secondo passo dal punto di vista teorico fu l’applicazione del concetto di “configurazione riducibile”: una configurazione di regioni è riducibile se può essere opportunamente modificata in modo da ridurre il numero delle regioni e dei colori necessari per colorarla, fino al numero di quattro soltanto. Sono sempre riducibili ad esempio le configurazioni con una regione con tre vicini o con quattro, mentre se ne hanno cinque la cosa diventa più difficile.

Il metodi di riduzione era già stato concepito dal matematico inglese Alfred Kempe nell’articolo del 1879 nel quale aveva presentato una dimostrazione del teorema, che però, come si scoprì undici anni più tardi, presentava qualche falla. Se ad esempio una regione ha tre vicini, la si può contrarre fino a farla scomparire in modo da ottenere una mappa più semplice, e se tale mappa può essere colorata con quattro colori, ciò è possibile anche per quella di partenza, assegnando alla regione contratta un colore diverso da quello delle tre regioni vicine. Kempe aveva descritto anche un metodo più complesso per contrarre regioni con quattro o cinque vicini: continuando con riduzioni successive, qualsiasi mappa si doveva poter ridurre fino a essere 4-colorabile. Il metodo aveva mostrato di essere attaccabile da numerosi controesempi nel caso di regioni con cinque vicini, ma Appel e Haken avevano a disposizione tecniche più sofisticate e strumenti di calcolo molto più potenti per poter superare queste difficoltà.

Essi si avvalsero di programmi concepiti appositamente per confermare che ognuna delle mappe dell’insieme inevitabile era riducibile. Se la congettura dei quattro colori fosse stata falsa, sarebbe esistita almeno una mappa con il numero più piccolo possibile di regioni che avrebbe richiesto cinque colori, invece Appel e Haken arrivarono alla costruzione di un insieme inevitabile di configurazioni riducibili, dimostrando il teorema.

Un esempio può, semplificando molto, aiutare la comprensione del metodo dei due matematici dell’Illinois. La prima illustrazione mostra una configurazione ideale nella quale la regione rappresentata dal quadrato rosso sembra, in base ai confini condivisi con altre quattro regioni, dover richiedere un quinto colore: in questo caso sarebbe un controesempio del teorema. In realtà, colorando opportunamente le varie regioni circostanti, ci si accorge che il quadrato può essere colorato come le regioni V, X e R della seconda illustrazione, quindi la mappa richiede solo quattro colori.

Per ridurre al minimo la possibilità di errore, il programma fu eseguito su diverse macchine con due algoritmi indipendenti; per completare l'analisi di tutti i casi possibili fu necessario far lavorare i computer per migliaia di ore. Dopo centinaia di pagine di verifiche fatte manualmente caso dopo caso, Appel e Haken conclusero che non esistono controesempi e che quindi il teorema è vero.

Il fatto che la dimostrazione fosse basata sull'analisi di una moltitudine di casi discreti ottenuta grazie all’ausilio del computer (era la prima volta che succedeva) portò alcuni matematici a contestarne l'effettiva validità, sia per l'impraticabilità di una verifica manuale di tutti i casi possibili, sia per l'impossibilità di avere la certezza che l'algoritmo fosse stato implementato correttamente. Il New York Times si rifiutò inizialmente di dare notizia della dimostrazione di Appel e Haken, temendo che essa si sarebbe dimostrata falsa così come era successo alle precedenti.

Secondo la teoria dell'informazione non è infatti possibile dimostrare la correttezza di un algoritmo, ma tuttavia sono sufficienti semplici controprove per dimostrarne la non correttezza. In ogni caso, nonostante il metodo sia poco elegante per i gusti estetici di molti addetti ai lavori, l'algoritmo ha resistito a tutti i tentativi di contestarne la validità.

Nei primi anni ’80 sembrò che il tedesco Ulrich Schmidt, dell’Università Tecnica di Aquisgrana, avesse trovato un errore nella dimostrazione di Appel e Haken durante la preparazione della sua tesi dottorato. Nel 1986 il direttore del Mathematical Intelligencer chiese ai due di scrivere una risposta. Essi redassero un dettagliato articolo nel quale poterono dimostrare che il supposto errore era dovuto a una “cattiva interpretazione” da parte di Schmidt. Due anni dopo seguì un testo di oltre 700 pagine, Every planar map is four colorable, contenente la versione completa e definitiva della loro dimostrazione, oltre alla replica alle numerose osservazioni avanzate nel frattempo. Nell’illustrazione in fondo a questo articolo è contenuta un’ingegnosa sintesi grafica di risposta ai controesempi proposti.

Da allora l’accettazione è stata più ampia, anche se rimasero alcune perplessità, per dissipare le quali nel 1997 fu pubblicata da Robertson, Sanders, Seymour e Thomas una dimostrazione più semplice, basata sulle stesse idee e ancora sul computer, ma più efficiente, perché riduceva la complessità del problema e richiedeva di verificare solamente 633 configurazioni riducibili. Infine, nel 2005, il teorema fu dimostrato in modo formale da Georges Gonthier con il Coq, un software assistente di prova interattivo assai sofisticato, che non richiede di ricorrere a diversi programmi per verificare casi particolari, ma semplicemente al suo kernel. Con macchine del genere e i processori attuali, la dimostrazione con l’algoritmo di Appel e Haken oggi si può realizzare in meno di un’ora.

Arrivati a questo punto si potrebbe obiettare che il giovane Arlecchino ha utilizzato un teorema valevole per il piano, mentre un vestito è tridimensionale. Si tratta di un’osservazione corretta. Le generalizzazioni del teorema per superfici diverse dal piano consentono tuttavia di affermare che anche per la sfera e il cilindro sono sufficienti quattro colori (come per i poliedri convessi aventi la stessa caratteristica di Eulero della sfera, χ = 2), mentre la questione diventa più complicata per figure meno comuni: per il toro sono ad esempio necessari sette colori, mentre il nastro di Möbius ne richiede sei, ma non è il caso di complicare la vita a una mascherina delle scuole primarie, per quanto sia intelligente.

Brendan D. McKay (2012). A note on the history of the four-colour conjecture ArXiv DOI: arXiv:1201.2852v1