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

Alspach (congettura di)

Congetture  Teoria dei grafi 

Nel 1981 Brian Alspach propose la congettura che ogni grafo completo Kn (nel quale ogni nodo è connesso a tutti gli altri) con n dispari si possa scomporre in qualsiasi insieme prefissato di cicli disgiunti (ossia senza archi in comune) di lunghezza massima n, con esattamente n * (n – 1) / 2 archi (e altrettanti nodi) in tutto.

La condizione che n sia dispari è necessaria, perché ogni nodo di Kn deve essere estremità di un numero pari di archi, dato che nei cicli ogni nodo è estremità di due archi; la condizione sul numero di archi indica semplicemente che il numero totale di archi nei cicli è uguale al numero di archi nel grafo da scomporre. Queste condizioni sono necessarie perché la scomposizione sia possibile, la congettura è che siano anche sufficienti.

 

Oltre un secolo fa Walecki aveva dimostrato che ogni grafo completo può essere scomposto in cicli separati; la congettura afferma che si può specificare l’insieme dei cicli.

 

La congettura può essere estesa ai grafi completi Kn con n pari, richedendo che la scomposizione tralasci un insieme di archi disgiunti che tra tutti hanno esattamente un estremo in ciascun nodo.

 

Nel 2014 Darryn Bryant, Daniel Horsley e William Pettersson dimostrarono che la congettura è vera, sia per n pari, che per n dispari.

 

La congettura non equivale al problema di Oberwolfach né lo implica, perché nella congettura di Alspach si permette a cicli diversi di condividere un nodo, mentre nel problema di Oberwolfach il grafo va diviso in copie di un insieme di cicli, ma i cicli di una copia dell’insieme non devono avere nodi in comune.

Contattami

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