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

Lovász (congettura di)

Congetture  Teoria dei grafi 

Nel 1969 László Lovász avanzò la congettura che ogni grafo finito, connesso, transitivo rispetto ai vertici abbia un cammino hamiltoniano (cioè un percorso che passa da ogni nodo esattamente una volta).

Due vertici di un grafo sono simili se esiste un automorfismo del grafo (una funzione che fa corrispondere a ogni nodo del grafo un altro nodo, preservando la struttura) che fa corrispondere al primo vertice il secondo, ottenendo un grafo uguale a quello di partenza. Per esempio, due vertici qualsiasi di un ciclo sono simili tra loro, mentre il nodo estremo di un grafo lineare di 3 o più vertici è simile all’altro nodo estremo, ma non ai nodi intermedi.

Un grafo è transitivo rispetto ai vertici se tutti i vertici sono simili tra loro, il che implica che il grafo sia regolare, ossia che ogni nodo sia estremo dello stesso numero di archi.

 

Si conoscono 5 eccezioni alla versione più forte della congettura, che afferma che ogni grafo finito, connesso, transitivo rispetto ai vertici abbia un ciclo hamiltoniano (ossia un cammino hamiltoniano chiuso): il grafo completo K2, il grafo di Petersen (v. congettura della doppia copertura con cicli), il grafo di Coxeter (un grafo con 28 nodi e 42 archi) e i due grafi ottenuti dagli ultimi due, rimpiazzando ogni nodo con un triangolo.

L’eccezione del grafo completo K2 è ovvia: si tratta di due nodi uniti da un arco e chiaramente un percorso chiuso è impossibile; per gli altri dimostrare che un percorso hamiltoniano chiuso non esiste è più complicato.

 

Un caso particolare interessante è quello dei grafi di Cayley, che sono generati a partire da un gruppo finito: dato un gruppo G e un insieme S di generatori (elementi tali che tutti gli elementi del gruppo possono essere ottenuti come combinazione di un numero finito di elementi di S), si fa corrispondere un noto a ogni elemento g di G e un arco (con direzione) da g a gs, per ogni elemento s di S.

In un certo senso quindi un grafo di Cayley rapresenta la struttura del gruppo.

I grafi di Cayley sono più facili da trattare, tanto che una versione meno forte della congettura è che essa valga solo per i grafi di Cayley.

 

La congettura è stata dimostrata vera per alcune categorie di grafi di Cayley:

  • quelli ottenuti da gruppi abeliani (ossia nei quali l’operazione di prodotto è commutativa);

  • quelli ottenuti da p-gruppi, per i quali esiste un primo p, tale che l’ordine di ogni elemento sia una potenza di p, non necessariamente la stessa per tutti gli elementi (vale a dire che il prodotto di pn copie di ogni elemento, e non di meno, è uguale all’identità per qualche intero n).

 

Robert Alexander Rankin dimostrò che la congettura non vale in generale per i grafi di Cayley direzionati (nei quali gli archi si possono percorrere in un solo senso), costruendo vari controesempi.

Contattami

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