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

Heawood (congettura di)

Congetture  Geometria  Matematica combinatoria 

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) in modo che regioni confinanti siano di colori diversi sia Formula per il numero di colori necessari per una superficie di genus n per n > 0 (v. numeri di Heawood).

Più correttamente, una superficie è di genus n se 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 tracciare, 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.

Il caso n = 0 corrisponde al piano, sul quale qualsiasi curva chiusa lo divide in due regioni, mentre il caso n = 1 corrisponde al toro, sul quale si può praticare un taglio lungo una curva chiusa, trasformandolo in una superficie topologicamente equivalente a un cilindro, ma senza dividerlo in due parti.

Per n = 0 la congettura si riduce al famoso teorema dei 4 colori e la formula dà la risposta giusta: 4 colori bastano per qualsiasi mappa sul piano o sulla sfera, ma quando fu formulata la congettura riguardava solo i valori di n maggiori a zero.

 

Heawood dimostrò che per il toro, ossia per mappe disegnate su ciambelle con un foro, sono necessari 7 colori, costruendo una mappa di 7 regioni, ciascuna confinante con tutte le altre, ma 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”, fino a quando Lothar Heffter riuscì a dimostrare che la congettura è vera per n < 7 e nel 1967 Gerhard Rungel Gerhard Ringel e J.T.W Youngs completarono nel 1968 la dimostrazione che è effettivamente vera per tutti i valori di n maggiori di zero.

 

Per dimostrare la congettura, è necessario costruire mappe che richiedano il numero massimo di colori previsto dalla formula per ogni valore di n. Un metodo possibile è costruire una mappa con il numero indicato di regioni, tali che ciascuna confini con tutte le altre, mostrando quindi che quel numero di colori è necessario.

L’approccio fu di scomporre il problema in 12 casi, corrispondenti a valori della forma n = 12s + k, per k da 0 a 11, oltre a 7 eccezioni sporadiche. I vari casi furono poi affrontati e risolti separatamente.

La tabella seguente riporta i vari passi che portarono al successo, in ordine cronologico.

Caso

Autore e anno

k = 5

Ringel, 1954

k = 3, 7, 10

Ringel, 1961

k = 0, 4

Terry, Welch e Young, 1963

k = 1

Gustin, Youngs, 1964

k = 9

Gustin, 1965

k = 6

Youngs, 1966

k = 2, 8, 11

Ringel, Youngs, 1967

Eccezioni per n = 18, 20, 23

Mayer, 1967

Eccezioni per n = 30, 35, 47, 59

Ringel, Youngs, 1968

 

La formula di Heawood non vale per le superfici non orientabili, ossia quelle sulle quali non è possibile definire in ogni punto un vettore normale alla superficie in modo consistente, cioè tali che muovendosi comunque sulla superficie e tornando allo stesso punto il vettore vari in modo continuo e resti alla fine invariato. Per esempio, su una striscia di Möbius un’associazione del genere non è possibile, perché muovendosi lungo la striscia si può tornare allo stesso punto, ma dall’altro lato della striscia. Una definizione meno rigorosa è che una superficie è orientabile se può essere dipinta con due colori, uno per faccia, senza linee di contatto tra i due colori (i “bordi” non contano). Quindi piano, sfera e toro sono orientabili, bottiglia di Klein e striscia di Möbius no.

 

Per superfici chiuse e connesse (anche non orientabili), la formula può essere scritta come Formula per il numero di colori necessari per una superficie con caratteristica χ, dove χ è la caratteristica di Eulero della superficie; per calcolarla si deve trasformare la superficie in un poliedro (non importa quale, né quanti poligoni si usino, perché è un invariante, che dipende solo dalle caratteristiche topologiche della superficie), poi calcolare χ = VS + F, dove V è il numero di vertici, S quello degli spigoli e F quello delle facce. Per esempio, la caratteristica è 2 per piano e sfera, 2 – 2n per una ciambella con n fori.

Manipolando la caratteristica di Eulero, si può dimostrare che deve esistere almeno una regione confinante con un numero di regioni inferiore al limite indicato dalla formula. Si può quindi rimuovere tale regione, colorare le restanti e riaggiungere la regione, senza superare il numero di colori indicato. Iterando il procedimento, si possono togliere tutte le regioni sino a lasciarne una, poi rimetterle a posto in ordine inverso, sempre senza superare il numero di colori. Pertanto i numeri di colori indicati dalla formula sono anche sufficienti.

 

L’unica eccezione è la bottiglia di Klein, per la quale la formula indica che sono necessari 7 colori, perché ha caratteristica 1, ma già nel 1934 Philip Franklin (5/10/1898 – 27/1/1965) aveva dimostrato 6 sono necessari e sufficienti.

 

Per le superfici non chiuse la situazione è leggermente diversa: per la striscia di Möbius bastano 6 colori, come per tutte le superfici nelle quali vi siano solo due regioni a contatto fuori dal piano, ovvero per tutti i grafi che possono essere disegnati con un solo incrocio tra archi (O.V. Borodin, 1984).

Contattami

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