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

Erdös – Gyárfás (congettura di)

Congetture  Teoria dei grafi 

La congettura avanzata nel 1995 da Paul Erdös e András Gyárfás afferma che ogni grafo con grado minimo 3 (ossia tale che ogni nodo sia estremità di almeno 3 archi) contiene un percorso chiuso semplice (ossia che non passa due volte dallo stesso nodo) la cui lunghezza (ossia il numero di archi che lo compongono) è una potenza di 2.

 

Nel 2004 Gordon Royle e Klas Markström dimostrarono con l’aiuto di un calcolatore che un eventuale controesempio deve avere almeno 17 nodi, e almeno 30 se il grafo è trivalente, cioè tale che ogni nodo sia estremità di esattamente 3 archi.

 

Nel 2011 P. Salehi Nowbandegani e H. Esfandiari dimostrarono che un eventuale controesempio in un grafo bipartito (ossia tale che i nodi siano suddivisi in due insiemi e ciascuno sia connesso solo ai nodi dell’altro insieme) ha almeno 32 nodi.

 

Nel 2013 Christopher Carl Heckman e Roi Krakovski dimostrarono che la congettura è vera per i grafi trivalenti, 3-connessi (ossia tali che non si dividano in parti separate rimuovendo due nodi qualsiasi) e planari (ossia disegnabili sul piano senza incroci); più precisamente i due matematici dimostrarono che tali grafi contengono un ciclo la cui lunghezza è una potenza di 2 tra 22 = 4 e 27 = 128.

Heckman e Krakovski ritenevano che la lunghezza massima necessaria possa essere ridotta e questo stimolò la ricerca del minimo grafo trivalente, 3-connesso e planare nel quali il minimo ciclo di lunghezza uguale a una potenza di 2 sia lungo 2n archi, per n da 2 a 7.

Si conoscono grafi con 10 nodi che non hanno cicli di lunghezza 4; Klas Markström dimostrò nel 2004 che il minimo grafo privo di cicli di lunghezza 4 e 8 ha 24 nodi.

Nel 2013 Geoffrey Exoo costruì tre grafi trivalenti, 3-connessi e planari:

  • uno con 420 vertici, ottenuto sostituendo ogni nodo del grafo corrispondente alla struttura della molecola del fullerene C60 con un piccolo grafo con 7 nodi, privo di cicli di lunghezza 4, 8 e 16;

  • uno con 78 nodi, privo di cicli di lunghezza 4, 8 e 16.

  • uno con 450 nodi, privo di cicli di lunghezza 4, 8, 16 e 32.

Non è noto se esistano grafi con meno nodi con la stessa proprietà, né se esista un grafo privo di cicli di lunghezza 4, 8, 16, 32 e 64.

Chiamando f(n) il minimo numero di nodi di un grafo che non contenga cicli di lunghezza 2k per kn, possiamo riassumere i risultati noti nella tabella seguente.

n

f(n)

2

10

3

24

4

54 .. 78

5

≤ 450

6

?

7

Nessuno

 

 

Nel 2005 J. Verstraëte dimostrò che esiste un insieme S di interi, con un numero di elementi minori di n che non cresce più di n0.99, tale che ogni grafo con un numero medio di archi per nodo almeno uguale a 10 ha un circuito la cui lunghezza è in S.

Contattami

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