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

Secondo vicinato (congettura del)

Congetture  Teoria dei grafi 

Un grafo orientato è un grafo semplice, nel quale a ogni arco è assegnata una direzione. Una definizione equivalente è un grafo con una direzione assegnata a ogni arco, privo di archi che colleghino un nodo a se stesso e nel quale due nodi qualsiasi sono connessi al massimo da un solo arco.

In un grafo orientato si dicono “vicini” di un nodo i nodi da questo raggiungibili seguendo gli archi uscenti nella loro direzione, “primo vicinato” l’insieme dei vicini, ossia dei nodi a distanza 1 e “secondo vicinato” l’insieme dei nodi a distanza 2. Né il primo né il secondo vicinato di un nodo contengono il nodo stesso.

La congettura della secondo vicinato, proposta nel 1990 da Paul D. Seymour, afferma che in ogni grafo orientato esiste almeno un nodo n il cui secondo vicinato ha almeno tanti elementi quanti il primo.

I nodi per i quali il secondo vicinato ha almeno tanti elementi quanti il primo si chiamano “nodi di Seymour”. La congettura si può quindi esprimete dicendo che ogni grafo orientato ha almeno un nodo di Seymour.

Un nodo senza archi uscenti è automaticamente un nodo di Seymour, perché primo e secondo vicinato hanno zero elementi. In un grafo privo di triangoli, se in un grafo ogni nodo ha almeno n archi uscenti, un nodo con esattamente n archi uscenti è un nodo di Seymour, perché il primo vicinato ha n elementi e il secondo almeno altrettanti.

 

Se consideriamo i nodi come persone e gli archi orientati come amicizie (non ricambiate), possiamo dire che in un gruppo finito di persone ne esiste almeno una i cui amici hanno complessivamente più amici della persona stessa.

 

Nel 2001 Yoshihiro Kaneko e Stephen C. Locke dimostrarono la congettura per i grafi nei quali il minimo numero di archi uscenti da ogni nodo non supera 6, ossia quelli nei quali da almeno un nodo non escono più di 6 archi.

 

Nel 2003 Chen Guantao, Shen Jian e Raphael Yuster dimostrarono che in un grafo orientato esiste almeno un nodo nel quale il numero di elementi del secondo vicinato è almeno γ volte quelli del primo, dove γ è la radice reale dell’equazione 2x3 + x2 – 1 = 0, vale a dire Formula per il calcolo di γ.

 

Nel 2016 Hao Liang e Jun-Ming Xu generalizzarono questo risultato, dimostrando che se un grafo orientato non contiene cicli di lunghezza fino a m, allora γ è la radice reale dell’equazione 2x3 – (m – 3)x2 + (2m – 4)xm + 1 = 0. Nel caso m = 4 la soluzione è Formula per il calcolo di γ ed aumenta, tendendo a 1 per m tendente a infinito.

 

Nel 2009 James Brantner, Greg Brockman, Bill Kay e Emma Snively dimostrarono che la congettura è vera per tutti i grafi che non contegono un triangolo non ciclico (nel quale cioè esiste un nodo A dal quale escono archi che vanno in due nodi B e C ed esiste un arco da B a C) e che se la congettura è falsa, esistono infiniti controesempi non isomorfi.

 

Nel 2009 Tyler Seacrest dimostrò che in qualsiasi grafo la congettura è vera per un sottoinsieme dei nodi e che se esiste un controesempio in un grafo nel quale il minimo numero di archi uscenti da un nodo è d, il controesempio minimo ha al massimo d * (d+ 1) / 2 nodi.

 

Dalla congettura del secondo vicinato seguirebbe un caso particolare della congettura di Caccetta – Häggkvist.

Contattami

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