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

Thrackle (congettura dei)

Congetture  Teoria dei grafi 

Un “thrackle” (termine intraducibile; “treccia” rende vagamente l’idea) è un grafo disegnato in modo tale che ogni arco abbia esattamente un punto in comune con ogni altro; il punto in comune può essere un estremo oppure un incrocio.

La figura seguente mostra un thrackle con 6 nodi e altrettanti archi, equivalente a un ciclo C6.

 

Esempio di thrackle

 

 

Si conoscono alcune proprietà generali dei thrackle:

  • esistono thrackle equivalenti a ogni ciclo, tranne C4;

  • un thrackle non può contenere C4 come sottografo (L. Lovász, J. Pach, e M. Szegedy, 1997);

  • un thrackle non può contenere due cicli di lunghezza dispari separati (L. Lovász, J. Pach, e M. Szegedy, 1997);

  • un thrackle non può contenere due vertici connessi da tre cammini separati di 3 archi ciascuno (L. Lovász, J. Pach, e M. Szegedy, 1997).

 

John Horton Conway avanzò la congettura che in un thrackle il numero degli archi non possa superare quello dei nodi.

 

La congettura era stata dimostrata vera per i grafi tracciati con segmenti da H. Hopf e E. Pannwitz nel 1934, addirittura prima che Conway nascesse, in una forma leggermente diversa e in seguito da Erdős e Perles nella forma proposta da Conway.

 

Negli anni sono stati fatti prograssi verso la dimostrazione della congettura; se n è il numero di nodi:

  • nel 1997 L. Lovász, J. Pach, e M. Szegedy dimostrarono che il numero degli archi è al massimo 2n – 3;

  • nel 2000 G. Cairns e Y. Nikolayevsky dimostrarono che il numero degli archi non supera 3 / 2 * (n – 1);

  • nel 2010 Radoslav Fulek e János Pach dimostrarono che il numero degli archi non supera 167 / 117 * n.

 

Wei Li, Karen Daniels e Konstantin Rybnikov dimostrarono che, come supposto da S. Wehner, un controesempio col minimo numero di nodi, se esiste, deve avere una delle seguenti tre forme:

  • due cicli, connessi da un cammino lineare;

  • due cicli con un nodo in comune;

  • tre cammini lineari tra gli stessi due punti.

 

Un thrackle generalizzato è un grafo disegnato in modo tale che ogni arco abbia un numero dispari di punti in comune con ogni altro, inclusi gli estremi.

L. Lovász, J. Pach e M. Szegedy dimostrarono nel 1997 che:

  • un grafo bipartito può essere tracciato come thrackle generalizzato se e solo se è planare, ossia disegnabile sul piano senza incroci;

  • la congettura non resta valida per i thrackle generalizzati, perché un grafo bipartito planare con n nodi può avere fino a 2n – 4 archi;

  • un thrackle generalizzato con n nodi ha al massimo 3n – 4 archi.

Contattami

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