Graficul Turan

Graficul lui Turán T (13,4).

Graficul Turan T ( n , r ) este un grafic format prin împărțirea unui set de n vârfuri în subseturi r , cu dimensiuni cât mai egale posibil și conectarea a două vârfuri de o margine ori de câte ori aparțin unor subseturi diferite. Graficul va avea $(n\,{\bmod {\,}}r)$ ${\ displaystyle (n \, {\ bmod {\,}} r)}$ ${\ displaystyle (n \, {\ bmod {\,}} r)}$ subseturi de dimensiuni $\lceil n/r\rceil$ ${\ displaystyle \ lceil n / r \ rceil}$ ${\ displaystyle \ lceil n / r \ rceil}$ , Și $r-(n\,{\bmod {\,}}r)$ ${\ displaystyle r- (n \, {\ bmod {\,}} r)}$ ${\ displaystyle r- (n \, {\ bmod {\,}} r)}$ subseturi de dimensiuni $\lfloor n/r\rfloor$ ${\ displaystyle \ lfloor n / r \ rfloor}$ ${\ displaystyle \ lfloor n / r \ rfloor}$ . Adică, este un grafic complet al părții r

K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\ldots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.

{\ displaystyle K _ {\ lceil n / r \ rceil, \ lceil n / r \ rceil, \ ldots, \ lfloor n / r \ rfloor, \ lfloor n / r \ rfloor}.}

{\ displaystyle K _ {\ lceil n / r \ rceil, \ lceil n / r \ rceil, \ ldots, \ lfloor n / r \ rfloor, \ lfloor n / r \ rfloor}.}

Fiecare vârf are gradul o $n-\lceil n/r\rceil$ ${\ displaystyle n- \ lceil n / r \ rceil}$ ${\ displaystyle n- \ lceil n / r \ rceil}$ sau $n-\lfloor n/r\rfloor$ ${\ displaystyle n- \ lfloor n / r \ rfloor}$ ${\ displaystyle n- \ lfloor n / r \ rfloor}$ . Numărul muchiilor este

{\frac {1}{2}}(n^{2}-(n\,{\bmod {\,}}r)\lceil n/r\rceil ^{2}-(r-(n\,{\bmod {\,}}r))\lfloor n/r\rfloor ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}.

{\ displaystyle {\ frac {1} {2}} (n ^ {2} - (n \, {\ bmod {\,}} r) \ lceil n / r \ rceil ^ {2} - (r- ( n \, {\ bmod {\,}} r)) \ lfloor n / r \ rfloor ^ {2}) \ leq \ left (1 - {\ frac {1} {r}} \ right) {\ frac { n ^ {2}} {2}}.}

{\ displaystyle {\ frac {1} {2}} (n ^ {2} - (n \, {\ bmod {\,}} r) \ lceil n / r \ rceil ^ {2} - (r- ( n \, {\ bmod {\,}} r)) \ lfloor n / r \ rfloor ^ {2}) \ leq \ left (1 - {\ frac {1} {r}} \ right) {\ frac { n ^ {2}} {2}}.}

Este un grafic regulat , dacă n este divizibil cu r .

Teorema lui Turán

Graficele Turan sunt numite după Pál Turán , care le-a folosit pentru a demonstra teorema lui Turan , o realizare importantă în teoria graficelor extremale .

Prin principiul sertarului , fiecare set de vârfuri r + 1 din graficul Turan include două vârfuri în același subset de partiție; prin urmare, graficul Turan nu conține o clică de dimensiune r + 1. Conform teoremei Turan, graficul Turan are numărul maxim posibil de muchii dintre toate graficele fără ( r + 1) -crafe cu n vârfuri. Keevash și Sudakov (2003) arată că graficul Turan este, de asemenea, singurul grafic fără ( r + 1) -creuri de ordinul n în care fiecare subset de α n vârfuri îmbrățișează cel puțin ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$ ${\ displaystyle {\ frac {r \, {-} \, 1} {2r}} (2 \ alpha -1) n ^ {2}}$ ${\ displaystyle {\ frac {r \, {-} \, 1} {2r}} (2 \ alpha -1) n ^ {2}}$ muchii, dacă α este suficient de apropiată de 1. Teorema Erdős - Stone extinde teorema Turan prin limitarea numărului de margini ale unui grafic care nu are un grafic Turan fix ca subgraf. Prin această teoremă, limite similare în teoria graficelor extreme pot fi dovedite pentru orice subgraf exclus, în funcție de numărul cromatic al subgrafului.

Cazuri speciale

Octaedrul, un politop încrucișat ale cărui margini și vârfuri formează un grafic Turan T (6,3).

Diverse alegeri ale parametrului r într-un grafic Turan conduc la grafice particulare care au fost studiate independent.

Graficul Turan T (2 n , n ) poate fi format prin eliminarea unei potriviri perfecte dintr-un grafic complet K _{2 n} . După cum a arătat Roberts (1969) , acest grafic are bossicitate exact n ; este uneori cunoscut sub numele de grafic Roberts . Acest grafic este, de asemenea, scheletul 1 al unui politop transversal n- dimensional; de exemplu, graficul T (6,3) = K _2,2,2 este graficul octaedric , graficul octaedrului regulat. Dacă n cupluri merg la o petrecere și fiecare persoană dă mâna cu fiecare persoană, cu excepția partenerului său, atunci acest grafic descrie setul de strângeri de mână care au loc; din acest motiv se mai numește și graficul cocktail - urilor .

Graficul Turan T ( n , 2) este un grafic bipartit complet și, atunci când n este egal, un grafic Moore . Când r este un divizor al lui n , graficul Turan este simetric și puternic regulat , deși unii autori consideră graficele Turán ca un caz banal de regularitate puternică și, prin urmare, le exclud din definiția unui grafic puternic regulat.

Graficul Turan $T(n,\lceil n/3\rceil )$ ${\ displaystyle T (n, \ lceil n / 3 \ rceil)}$ ${\ displaystyle T (n, \ lceil n / 3 \ rceil)}$ are 3 ^a 2 ^b fisuri maxime , unde 3 a + 2 b = n și b ≤ 2; fiecare clică maximă este formată prin alegerea unui vârf din fiecare subset de partiție. Acesta este cel mai mare număr de fisuri maxime posibile dintre toate graficele n- vertex, indiferent de marginile din grafic ( Moon și Moser (1965) ); aceste grafice sunt uneori numite grafice Moon-Moser .

Alte proprietăți

Fiecare grafic Turan este un cograf ; adică se poate forma pornind de la vârfurile unice prin intermediul unei secvențe de operații disjuncte de unire și complement . Mai exact, o astfel de secvență poate începe prin formarea fiecăruia dintre seturile independente ale graficului Turan ca o uniune disjunctă de vârfuri izolate. Apoi, graficul general este complementul unirii disjuncte a complementelor acestor seturi independente.

Chao și Novacky (1982) arată că graficele Turán sunt unice din punct de vedere cromatic : niciun alt grafic nu are aceleași polinoame cromatice . Nikiforov (2005) folosește grafice Turán pentru a furniza o limită inferioară pentru suma valorilor proprii k- esimi ale unui grafic și complementul acestuia.

Falls, Powell și Snoeyink dezvoltă un algoritm eficient pentru gruparea grupurilor de gene ortoloage în datele genomice, trasând datele sub forma unui grafic și căutând subgrafe mari Turan.

Graficele Turan au, de asemenea, câteva proprietăți interesante legate de teoria graficelor geometrice . Pór și Wood (2005) dau o limită inferioară de Ω (( rn ) ^3/4 ) la volumul oricărei rețele tridimensionale încorporate a graficului Turán. Witsenhausen (1974) presupunere că suma maximă a distanțelor la pătrat, între n puncte cu unitate diametru cuprins în R ^d, este atinsă pentru o configurație formată prin încorporarea unui grafic turan pe vârfurile unui simplex regulat.

Un grafic G cu n vârfuri este un subgraf al unui grafic Turan T ( n , r ) dacă și numai dacă G admite o colorare egală cu r culori. Partiția graficului Turan în seturi independente corespunde partiției lui G în clase de culori. În special, graficul Turan este singurul grafic maxim pe n vârfuri cu o culoare egală cu r culori.

Bibliografie

Chao, CY; Novacky, GA, Despre graficele maxim saturate , în Discrete Mathematics , vol. 41, nr. 2, 1982, pp. 139–143, DOI : 10.1016 / 0012-365X (82) 90200-X .
Falls, Craig; Powell, Bradford; Snoeyink, Jack, Calculul COG-urilor de înaltă stringență utilizând grafice de tip Turan ( PDF ).
Keevash, Peter; Sudakov, Benny, Densitatea locală în grafice cu subgrafe interzise , în Combinatorică, Probabilitate și Calcul , vol. 12, nr. 2, 2003, pp. 139–153, DOI : 10.1017 / S0963548302005539 .
Moon, JW și Moser, L. , Despre clici în grafice , în Israel Journal of Mathematics , vol. 3, 1965, pp. 23-28, DOI : 10.1007 / BF02760024 .
Nikiforov, Vladimir, Eigenvalue problems of Nordhaus-Gaddum type , 2005, arXiv : math.CO/0506260 .
Pór, Attila; Wood, David R., Proc. Int. Symp. Graph Drawing (GD 2004) , No-three-in-line-in-3D , Lecture Notes in Computer Science nr. 3383, Springer-Verlag, 2005, pp. 395–402, DOI : 10.1007 / b105810 .
Roberts, FS , Despre boxicitatea și cubicitatea unui grafic , în Recent Progress in Combinatorics , Academic Press, 1969, pp. 301-310.
Turán, P. , Despre o problemă extremă în teoria graficelor , în Matematiko Fizicki Lapok , vol. 48, 1941, pp. 436-452.
Witsenhausen, HS, Despre suma maximă a distanțelor pătrate sub o constrângere de diametru , în American Mathematical Monthly , vol. 81, nr. 10, The American Mathematical Monthly, Vol. 81, No. 10, 1974, pp. 1100-1101, DOI : 10.2307 / 2319046 , JSTOR 2319046 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre graficul lui Turán

linkuri externe

(EN) Eric W. Weisstein,Cocktail Party Graph în MathWorld Wolfram Research.
(EN) Eric W. Weisstein, Octahedral Graph în MathWorld Wolfram Research.
( EN ) Eric W. Weisstein, Turán Graph , în MathWorld , Wolfram Research.

Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica