Lemma di Sperner

Il lemma di Sperner è un teorema della teoria dei grafi che ha delle importanti applicazioni in topologia; in particolare, permette quella che è forse la dimostrazione più elementare del teorema del punto fisso di Brouwer.

Caso unidimensionale

Grafo colorato con 5 segmenti completi.

Si consideri un grafo costituito da un numero finito di vertici allineati su un segmento, e consideriamo una colorazione dei vertici con due colori A e B. Chiamiamo "segmento completo" uno spigolo del grafo che abbia i due vertici colorati con A e B.

Il lemma di Sperner stabilisce che

se i vertici estremi del grafo hanno colori differenti allora il numero totale di segmenti completi del grafo è un numero dispari (e in particolare è maggiore o uguale a 1).

Nel disegno a fianco è illustrato un esempio di grafo colorato che soddisfa le ipotesi del lemma di Sperner in cui si possono contare 5 segmenti completi.

La dimostrazione si può ottenere per induzione sul numero di nodi del grafo. Il numero minimo di nodi è 2 e nel caso di due nodi c'è un solo segmento che è completo perché i suoi vertici sono i vertici estremi del grafo. Ora supponiamo che per i grafi di n vertici si abbia un numero dispari di segmenti completi. Un grafo di n+1 vertici lo possiamo ottenere aggiungendo in un vertice sul segmento di un grafo di n vertici. Le possibilità sono le seguenti:

1. aggiungiamo un vertice di colore A tra due di colore A, allora il numero di segmenti completi rimane inalterato
2. aggiungiamo un vertice di colore B tra due di colore B, è un caso identico a quello appena analizzato
3. aggiungiamo un vertice di colore A tra due di colore B o viceversa, in tal caso i segmenti completi aumentano di due unità
4. aggiungiamo un vertice di colore A o B in un segmento completo, allora il segmento AB precedente non c'è più e lascia il posto a due segmenti di cui uno completo e l'altro no, dunque il numero totale di segmenti completi rimane inalterato. In tutti i casi se si aveva un numero dispari di segmenti completi con n vertici il numero rimane dispari anche con l'aggiunta di un n+1-esimo vertice. Questo conclude la dimostrazione per induzione.

Caso bidimensionale

Grafo colorato che soddisfa le ipotesi del lemma di Sperner, in grigio sono evidenziati i triangoli completi

Consideriamo il grafo individuato da vertici e lati di un triangolo T con al suo interno una triangolazione.

Consideriamo quindi una colorazione di questo grafo con tre colori A,B,C.

Chiamiamo triangolo completo un sottografo composto da tre vertici adiacenti tale che i suoi tre vertici siano colorati con i tre colori A, B e C.

Il lemma di Sperner afferma che:

se i tre vertici del triangolo T hanno colori differenti (A, B e C) e i nodi del grafo che si trovano su ciascun lato di T hanno soltanto uno dei due colori dei due vertici che delimitano quel lato (e dunque i lati soddisfano le ipotesi del lemma nel caso unidimensionale), allora il grafo contiene un numero dispari di triangoli completi (in particolare ne contiene almeno uno).

Dimostrazione

Si possono dare diversi tipi di dimostrazioni di questo enunciato. Una possibilità è quella di considerare il grafo duale che ha un nodo dentro ciascun sotto-triangolo e all'esterno di ciascun segmento sui lati, come in figura. Poi si scelgono due colori, diciamo R (rosso) e V (verde). I nodi del grafico duale vengono poi collegati da un arco se e solo se questo arco attraversa un segmento con estremi colorati con R e V (come in figura).

Ora analizziamo i cammini individuati da questi nodi (tracciati nel disegno con un tratto più spesso). Valgono le seguenti proprietà:

1. Questi cammini non possono mai avere biforcazioni poiché un triangolo non può contenere più di due lati con colori R e V.
2. Fra i lati esterni del triangolo possiamo trovare archi del grafo duale solamente su un lato: quello che aveva la colorazione con R e V (per ipotesi gli altri due hanno colorazione verde-blu e rosso-blu).
3. I cammini che partono dal lato esterno possono fermarsi solo in due casi: se entrano dentro un triangolo completo oppure se escono da un lato esterno. Infatti se si trovano all'interno e si trovano in un triangolo non completo allora deve necessariamente esserci un altro lato con colori R e V.
4. Ci sono poi dei cammini che rimangono sempre all'interno: per il discorso appena fatto questi cammini devono iniziare dentro un triangolo completo e concludersi dentro un altro triangolo completo.

Per concludere la dimostrazione ci rifacciamo alla versione unidimensionale del lemma: questa ci assicura che sul bordo esterno c'è un numero dispari di segmenti RV. Dunque - essendo dispari - non tutti i cammini che entrano attraverso questi segmenti possono poi riuscire attraverso un altro segmento RV: deve esserci almeno un cammino che entra da un segmento RV del bordo e si conclude all'interno, in tal caso per le osservazioni fatte sopra (n. 3) deve finire in un triangolo completo. Dunque deve esistere un triangolo completo. Il numero di triangoli completi inoltre deve essere dispari perché:

1. i segmenti RV del bordo che riescono dal bordo devono essere in numero pari, dunque avanza un numero dispari di segmenti che finisce in triangoli completi distinti;
2. ci sono poi triangoli completi interni da cui partono cammini che non escono dal bordo e in tal caso sappiamo che tali cammini devono finire su un altro triangolo completo, quindi il numero di questi triangoli completi addizionali è pari e sommato a quello dei triangoli completi collegati con il bordo dà un numero dispari.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su lemma di Sperner

Collegamenti esterni

• Cut the knot, su cut-the-knot.org.