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

Dean (congettura di)

Congetture  Teoria dei grafi 

Si dicono “tornei” i grafi completi orientati, perché corrispondono a schemi di gironi semplici all’italiana, nei quali ogni squadra (corrispondente a un nodo) incontra tutte le altre, immaginando la direzione come una freccia che va dalla squadra di casa a quella ospite (senza il requisito che una squadra gichi tante volte in casa quante fuori).

La congettura avanzata nel 1995 da Nathaniel Dean è il caso della congettura del secondo vicinato limitata ai tornei. Nei termini dei tornei si può enunciare dicendo che in ogni girone all’italiana semplice esiste almeno una squadra s tale che l’insieme degli avversari incontrati in casa dalle squadre contro le quali s ha giocato in casa contiene almeno tante squadre quante quelle contro le quali s ha giocato in casa.

 

Il quadrato di un grafo è il grafo ottenuto congiungendo ogni nodo a tutti quelli a distanza 1 o due da esso, ovvero aggiungendo archi tra tutte le coppie di nodi distinti connesse tramite due archi.

Nel caso di grafi orientati, vuol dire aggiungere a ogni nodo un arco che lo congiunge ai nodi raggiungibili da esso percorrendo esattamente due archi.

La congettura di Dean può quindi essere espressa come segue: facendo il quadrato di ogni torneo, esiste almeno un nodo il cui vicinato raddoppia almeno di numero.

 

Nathaniel Dean e Brenda J. Latka dimostrarono nel 1995 che la congettura è vera:

  • per i grafi nei quali esiste almeno un nodo dal quale escono al massimo 5 archi;

  • per i grafi nei quali per qualsiasi coppia di nodi la differenza tra il numero di archi uscenti è al massimo uno.

 

La congettura di Dean fu dimostrata da David C. Fischer nel 1996.

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.