Contele de Turan

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 octombrie 2021; verificarea necesită 1 editare .

Contele de Turan

Numit după	Pal Turan
Vârfurile	n
coaste	$\left\lfloor {\frac {(r-1)n^{2}}{2r}}\right\rfloor$
Rază	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.$
Diametru	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.$
Circumferinţă	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text {altfel)} \end{matrice}}\right.$
Număr cromatic	r
Desemnare	= T ( n , r )
Fișiere media la Wikimedia Commons

Un grafic Turan T ( n , r ) este un grafic format prin descompunerea n vârfuri în r submulțimi, cu dimensiunea cât mai apropiată, iar vârfurile din acest grafic sunt legate printr-o muchie dacă aparțin unor submulțimi diferite. Graficul va avea subseturi de dimensiune și subseturi de dimensiune . Deci acesta este un graf complet r -partit $(n\,{\bmod {\,}}r)$ $\lceil n/r\rceil$ $r-(n\,{\bmod {\,}}r)$ $\lfloor n/r\rfloor$

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

Fiecare vârf are grad fie , fie . Numărul de muchii este $n-\lceil n/r\rceil$ $n-\lfloor n/r\rfloor$

{\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}}.

Un grafic este regulat dacă n este divizibil cu r .

Teorema lui Turan

Graficele Turan sunt numite după Pal Turan , care le-a folosit pentru a demonstra teorema lui Turan , un rezultat important în teoria grafurilor extreme .

După principiul lui Dirichlet , orice set de r + 1 vârfuri dintr-un grafic Turan include două vârfuri din aceeași fracțiune a graficului. Astfel, graficul Turan nu conține o clică de dimensiunea r + 1. Conform teoremei Turan, graficul Turan are numărul maxim posibil de muchii dintre toate graficele fără clicuri de dimensiunea r + 1 care au n vârfuri. Kivash și Sudakov (Keevash și Sudakov, 2003) au arătat că graficul Turan este singurul grafic fără clicuri de dimensiune r + 1 de ordin n în care orice submulțime de α n vârfuri are cel puțin muchii dacă α este suficient de aproape de 1 . Teorema Erdős–Stone extinde teorema Turan prin limitarea numărului de muchii dintr-un graf care nu are un graf Turan fix ca subgraf. Ca o consecință a acestei teoreme, în teoria grafurilor extreme, pentru orice subgraf interzis, se pot demonstra limite similare în funcție de numărul cromatic al subgrafului. ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Ocazii speciale

Unele valori ale parametrului r al graficelor Turan conduc la grafice remarcabile, care sunt studiate separat.

Graficul Turan T (2 n , n ) poate fi obținut prin eliminarea unei potriviri perfecte din graficul complet K 2 n . După cum arată Roberts ( Roberts 1969 ), cadrul acestui grafic este exact n . Acest conte este uneori denumit Contele de Roberts . Acest grafic este, de asemenea, un schelet 1 cograf n - dimensional . De exemplu, graficul T (6,3) = K 2,2,2 este graficul unui octaedru regulat . Dacă n cupluri vin la o petrecere și fiecare persoană dă mâna cu toată lumea, cu excepția partenerului, atunci acest grafic descrie un set de strângeri de mână. Din acest motiv, el este denumit și Numărul Cocktail Party .

Graficul Turan T ( n ,2) este un grafic bipartit complet , iar dacă n este par, este un grafic Moore . Dacă r este un divizor al lui n , graficul Turan este simetric și puternic regulat , deși unii autori consideră că graficele Turan sunt un caz trivial de regularitate puternică și, prin urmare, le exclud din definiția graficelor puternic regulate.

Graficul Turana are 3 a 2 b clicuri cele mai mari , unde 3 a + 2 b = n și b ≤ 2. Fiecare clică cea mai mare se formează prin alegerea unui vârf din fiecare cotă. Acest număr de clicuri cele mai mari este cel mai mare posibil dintre toate graficele cu n vârfuri, indiferent de numărul de muchii din grafic (Moon și Moser, 1965). Aceste grafice sunt uneori numite grafice Moon-Moser . $T(n,\lceil n/3\rceil )$

Alte proprietăți

Orice graf Turan este un cograf . Astfel, poate fi format din vârfuri individuale printr-o succesiune de operații de unire și complement disjunc . În special, o astfel de secvență poate fi începută prin formarea tuturor mulțimilor independente ale grafului Turan ca o uniune disjunctă de vârfuri izolate. Atunci întregul grafic este complementul uniunii disjunctive a complementelor acestor mulțimi independente.

Chao și Novacky (1982) au arătat că graficele Turan sunt unice din punct de vedere cromatic - niciun alt grafic nu are aceleași polinoame cromatice . Nikiforov (Nikiforov, 2005) a folosit graficele Turan pentru a găsi limita inferioară pentru suma k --lea valorilor proprii ale unui grafic și complementul acestuia.

Falls, Powell și Snoeyink au dezvoltat un algoritm eficient pentru găsirea de grupuri de grupuri de gene ortologe în genom prin reprezentarea datelor ca un grafic și căutarea subgrafelor Turan mari.

Graficele Turan au, de asemenea, o serie de proprietăți interesante legate de teoria grafurilor geometrice . Pór și Wood (2005) oferă o limită inferioară Ω(( rn ) 3/4 ) pentru orice înglobare tridimensională a graficului Turan. Witsenhausen (1974) a presupus că suma maximă a pătratelor dintre n puncte din interiorul unei bile în R d de diametru unitar se realizează pe configurația formată prin încorporarea graficului Turan în vârfurile unui simplex regulat.

Un grafic G cu n vârfuri este un subgraf al graficului Turan T ( n , r ) dacă și numai dacă G admite o colorare corectă în r culori. Descompunerea grafului Turan în mulțimi independente corespunde descompunerii lui G în clase de culoare. În special, graficul Turan este singurul grafic maxim n -vertex cu o colorare corectă în r culori.

Note

Literatură

C.Y. Chao, G. A. Novacky. Pe grafice maxim saturate // Matematică discretă. - 1982. - T. 41 , nr. 2 . — S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Calcularea COG-urilor de mare rigurozitate folosind grafice de tip Turán.
Peter Keevash, Benny Sudakov. Densitatea locală în grafice cu subgrafe interzise // Combinatorică, probabilitate și calcul. - 2003. - T. 12 , nr. 2 . — S. 139–153 . - doi : 10.1017/S0963548302005539 .
JW Moon, L. Moser. Pe clicuri în grafice // Israel Journal of Mathematics. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
Vladimir Nikiforov. Probleme cu valori proprii de tip Nordhaus-Gaddum . - 2005. - arXiv : math.CO/0506260 .
Attila Pór, David R Wood. Proc. Int. Symp. Desen grafic (G.D. 2004) . — Note de curs în Informatică nr. 3383, Springer-Verlag, 2005, p. 395–402. - doi : 10.1007/b105810 .
FS Roberts. Progrese recente în combinatorică. - Presa Academică, 1969. - S. 301-310.
P. Turan. Despre o problemă extremă în teoria grafurilor // Matematiko Fizicki Lapok. - 1941. - T. 48 . — S. 436–452 .
HS Witsenhausen. Pe maximul sumei distanțelor pătrate sub o constrângere de diametru // American Mathematical Monthly . — The American Mathematical Monthly, Vol. 81, nr. 10, 1974. - V. 81 , nr. 10 . - S. 1100-1101 . - doi : 10.2307/2319046 . — .

Link -uri

Weisstein, Eric W. Cocktail Party Graph la Wolfram MathWorld .
Weisstein, Eric W. Octahedral Graph (engleză) pe site-ul web Wolfram MathWorld .
Weisstein, Eric W. Turan Graph (engleză) pe site-ul web Wolfram MathWorld .