Топ-100
Indietro

ⓘ 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 ..




                                     

ⓘ 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.

                                     

1. Caso unidimensionale

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:

  • aggiungiamo un vertice di colore A tra due di colore B o viceversa, in tal caso i segmenti completi aumentano di due unità
  • 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 laltro 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 laggiunta di un n+1 -esimo vertice. Questo conclude la dimostrazione per induzione.
  • aggiungiamo un vertice di colore A tra due di colore A, allora il numero di segmenti completi rimane inalterato
  • aggiungiamo un vertice di colore B tra due di colore B, è un caso identico a quello appena analizzato
                                     

2. Caso bidimensionale

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.
                                     

2.1. Caso bidimensionale 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 allesterno 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à:

  • Ci sono poi dei cammini che rimangono sempre allinterno: per il discorso appena fatto questi cammini devono iniziare dentro un triangolo completo e concludersi dentro un altro triangolo completo.
  • 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.
  • Questi cammini non possono mai avere biforcazioni poiché un triangolo non può contenere più di due lati con colori R e V.
  • 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 allinterno e si trovano in un triangolo non completo allora deve necessariamente esserci un altro lato con colori R e V.

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 allinterno, 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é:

  • 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;
  • 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.


                                     
  • strato inferiore e si toccano. Triangolazione Teorema di Pick Lemma di Sperner Partizione geometrica di un insieme Insiemi trasversali geometrici Vedi anche:
  • dimostrare il teorema di Brouwer combinando fatti topologici elementari con un risultato della teoria dei grafi noto come lemma di Sperner Considerando per
  • Esistono tuttavia numerose altre dimostrazioni, ad esempio a partire dal lemma di Sperner Il teorema della palla pelosa ha applicazioni non solo in ambito matematico