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

Caccetta – Häggkvist (congettura di)

Congetture  Teoria dei grafi 

Nel 1970 M. Behzad, G. Chartrand e C. Wall avevano supposto che un grafo orientato nel quale ogni nodo abbia d archi entranti e altrettanti uscenti e nel quale esista un ciclo di lunghezza l debba avere almeno d(l – 1) + 1 nodi.

 

Nel 1978 Louis Caccetta e R. Häggkvist generalizzarono l’affermazione, avanzando la congettura che in un grafo orientato con n nodi, nel quale da ogni nodo escano almeno d archi, con d > 0, la lunghezza del minimo ciclo sia al massimo Massimo intero non superiore a n / d.

 

La congettura è stata provata in alcuni casi particolari:

  • per d ≥ n / d la dimostrazione è semplice;

  • per d = 2 da Caccetta e Häggkvist nel 1978;

  • per d = 3 da Y.O. Hamidoune nel 1987;

  • per d = 4 e 5 da C.T. Hóang e B.A. Reed nel 1987;

  • per n ≥ 2d2 – 3d + 1 da Jian Shen nel 2000.

 

Se fosse provata la congettura del secondo vicinato, seguirebbe la validità per i grafi nei quali ogni nodo ha almeno n / 3 archi entranti e altrettanti uscenti.

 

Nel 1983 V. Chvátal e E. Szemerédi dimostrarono che la lunghezza del minimo ciclo è al massimo 2 * n / (d + 1); Jian Shen dimostrò nel 1998 che è lungo al massimo Lunghezza massima del minimo ciclo dimostrata da Jian Shen.

 

Un approccio alternativo alla congettura consiste nel dimostrare che il minimo ciclo è lungo n / d + c, per una costante c; su questa strada sono stati fatti progressi:

  • nel 1983 V. Chvátal e E. Szemerédi dimostrarono che c è al massimo 2500;

  • nel 1986 T. Nishimura ridusse c a 304;

  • nel 2002 J. Shen dimostrò che c è al massimo 73.

 

Un altro filone di ricerca è quale sia il minimo numero d di archi uscenti da ciascun perché il grafo debba avere un ciclo di lunghezza 3; secondo la congettura di Caccetta – Häggkvist basterebbe d ≥ n / 3; lungo questa via ci si è avvicinati molto al minimo stabilito dalla congettura:

  • Caccetta e Häggkvist dimostrarono nel 1978 che basta d ≥ (3 – sqrt(5)) / 2 * n;

  • J. Bondy dimostrò nel 1997 che basta d ≥ (2 * sqrt(6) – 3) / 5 * n;

  • Jian Shen dimostrò nel 1998 che basta d ≥ (3 – sqrt(7)) * n.

Vedi anche

Congettura di Seymour.

Contattami

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