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

Il numero di Turán T(n, G) è il massimo numero di archi che un grafo con n nodi può contenere, senza che contenga un sottografo isomorfo a G.

Un grafo completo Kn con n nodi ha Numero di archi in un grafo completo K(n) con n nodi archi, il massimo possibile con n nodi; se il numero di archi di un grafo con n nodi è minore di r, il grafo non può contenere Kn, quindi Valore di T(n, K(n)).

 

Il nome è legato al teorema dimostrato da Pál Turán, che afferma che Valore di T(n, K(r + 1)). I grafi col massimo possibile numero di archi sono i grafi di Turán T(n, r), che si ottengono suddividendo gli n nodi in r sottoinsiemi il più equamente possibile (in modo quindi che ciascuno contenga Numero minimo di nodi di un sottoinsiemeNumero massimo di nodi di un sottoinsieme nodi), poi congiungendo ogni nodo a tutti quelli degli altri sottoinsiemi, ma non a quelli dello stesso sottoinsieme. Il numero di archi risultante è Numero di archi in un grafo di Turán.

Un caso particolare di grafo di Turán è il grafo T(2n, n): i nodi rappresentano i vertici di un iperottaedro a n dimensioni e gli archi corrispondono agli spigoli. Il grafo è anche chiamato “grafo del cocktail party”, perché descrive la situazione di n coppie che partecipano a una festa, ciascuno stringendo la mano a tutti gli altri, tranne che al proprio partner: i nodi corrispondono alle persone e gli archi alle strette di mano.

C.Y. Chao e G.A. Novacky dimostrarono nel 1982 che i grafi di Turán sono cromaticamente unici: nessun altro grafo ha lo stesso polinomio cromatico (per la definizione di polinomio cromatico v. costanti di Tutte – Beraha).

 

Nel 1907 Mantel aveva già dimostrato un caso particolare del teorema, cioè che Valore di T(n, K(3)); in altre parole, questo è il numero massimo di archi di un grafo con n nodi che non contenga triangoli.

Una forma più forte dello stesso teorema afferma che un grafo con n nodi e almeno n^2 / 4 archi che contenga un ciclo di lunghezza n o è un grafo bipartito completo, oppure contiene almeno un triangolo ed è panciclico, ossia contiene cicli di tutte le lunghezze da 2 a n.

 

Come nel caso dei numeri di Ramsey, i numeri di Turán sono noti in pochissimi casi e in alcuni altri sono noti limiti superiori, inferiori o asintotici:

  • Limite asintotico per T(n, G), dove dove χ(G) è il numero cromatico di G, ossia il minimo numero di colori necessari per colorare i nodi in modo che non ci siano archi tra due nodi dello stesso colore (v. numeri di Ramsey) (P. Erdös e A.H. Stone, 1946);

  • Limite asintotico per T(n, K(s, t)), dove Ks, t è un grafo bipartito completo, ossia un grafo formato da due insiemi di s e t nodi, nei quali ogni nodo di un insieme è connesso a tutti e soli i nodi dell’altro, per un totale di st archi, con st (Zoltán Füredi, 1996);

  • Limite inferiore per T(n, K(s, t)), per t ≥ (s – 1)! + 1, dove cs, t è una costante che dipende solo da s e t (Noga Alon, Lajos Rónyai e Tibor Szabó, 1999);

  • Limite superiore per T(n, K(2, t)) (T. Kövári, V.T. Sós e P. Turán, 1954) e Limite inferiore per T(n, K(2, t)), per n abbastanza grande (Zoltán Füredi, 1996);

  • Turán suppose che Limite inferiore per T(n, K(s, s)), dove cs è una costante che dipende solo da s; la congettura è stata dimostrata solo per s = 2 (P. Erdös, R. Rényi e V.T. Sós, 1966) e s = 3 (W.G. Brown, 1966); si sa inoltre che Limite inferiore per T(n, K(4, 4)), per qualsiasi costante c;

  • se G è un grafo bipartito, nel quale ogni nodo è connesso al massimo a r altri, Limite superiore per T(n, G), dove c è una costante positiva (Noga Alon, Michael Krivelevich e Benny Sudakov, 2002);

  • se G è un grafo bipartito, nel quale ogni nodo è connesso al massimo a r altri, Limite superiore per T(n, G), per nh (Noga Alon, Michael Krivelevich e Benny Sudakov, 2002).

 

Un caso particolare molto studiato è quello dei grafi ciclici Ck; per cicli di lunghezza dispari è noto che Valore di T(n, C(2 * k + 1)), mentre il problema è irrisolto per i cicli di lunghezza pari; i risultati migliori in questo caso sono: Limite superiore per T(n, C(2 * k)), per n abbastanza grande (O. Pikhurko, 2012) e Limite superiore per T(n, C(2 * k)), per n ≥ (2k)8k2 (B. Bukh e Z. Jiang).

Una congettura di Erdös e Simonovits è che al crescere di n T(n, C2k) tenda a Limite asintotico supposto per T(n, C(2 * k)); la congettura è stata dimostrata vera per k = 2 (P. Erdös, R. Rényi e V.T. Sós, 1966), inoltre Limite superiore per T(n, C(4)) (I. Reiman, 1958), però è stata dimostrata falsa in altri casi:

  • F. Lazebnik, V.A. Ustimenko e A.J. Woldar dimostrarono nel 1999 che Limite inferiore per T(n, C(6)) e che la congettura è falsa anche per k = 5;
  • Zoltán Füredi, Assaf Naor e Jacques Verstraëte dimostrarono che per infiniti valori di n Limite inferiore per T(n, C(6)) e Limite superiore per T(n, C(6)), dove λ è la radice reale dell’equazione 16x3 – 4x2 + x – 3 = 0, per n abbastanza grande.

 

Vedi anche

Numeri di Ramsey.

Contattami

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