Greve av Turana

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 oktober 2021; verifiering kräver 1 redigering .

Greve av Turana

Döpt efter	Pal Turan
Toppar	n
revben	$\left\lfloor {\frac {(r-1)n^{2}}{2r}}\right\rfloor$
Radie	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{annars}}\end{array}}\right.$
Diameter	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{annars}}\end{array}}\right.$
Omkrets	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{annars)) \end{array}}\right.$
Kromatiskt nummer	r
Beteckning	= T ( n , r )
Mediafiler på Wikimedia Commons

En Turan-graf T ( n , r ) är en graf som bildas genom att sönderdela n hörn i r delmängder, med storleken så nära som möjligt, och hörnen i denna graf är förbundna med en kant om de tillhör olika delmängder. Grafen kommer att ha delmängder av storlek och delmängder av storlek . Så detta är en komplett r -partite graf $(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 }.

Varje vertex har grad antingen , eller . Antalet kanter är $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))\lgolv n/r\rgolv ^{2})\leq \left(1-{\frac {1}{r}}\right){\frac { n^{2}}{2}}.

En graf är regelbunden om n är delbart med r .

Turans sats

Turan-grafer är uppkallade efter Pal Turan , som använde dem för att bevisa Turans sats , ett viktigt resultat inom extremalgrafteorin .

Enligt Dirichlets princip inkluderar varje uppsättning r + 1 hörn i en Turan-graf två hörn från samma bråkdel av grafen. Turan-grafen innehåller alltså inte en klick med storleken r + 1. Enligt Turan-satsen har Turan-grafen maximalt antal kanter bland alla grafer utan klick med storleken r + 1 som har n hörn. Kivash och Sudakov (Keevash och Sudakov, 2003) visade att Turan-grafen är den enda grafen utan klicker av storleken r + 1 av ordningen n där varje delmängd av α n hörn har åtminstone kanter om α är tillräckligt nära 1 . Erdős–Stone theorem utökar Turan-satsen genom att begränsa antalet kanter i en graf som inte har en fast Turan-graf som subgraf. Som en konsekvens av detta teorem, i teorin om extrema grafer, för varje förbjuden subgraf, kan man bevisa liknande gränser beroende på subgrafens kromatiska nummer . ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Särskilda tillfällen

Vissa värden på parametern r i Turan-grafer leder till anmärkningsvärda grafer, som studeras separat.

Turan-grafen T (2 n , n ) kan erhållas genom att ta bort en perfekt matchning från hela grafen K 2 n . Som visas av Roberts ( Roberts 1969 ) är ramverket för denna graf exakt n . Denna earl kallas ibland för Earl of Roberts . Denna graf är också en 1- skelett n - dimensionell kograf . Till exempel är grafen T (6,3) = K 2,2,2 grafen för en vanlig oktaeder . Om n par kommer till en fest och varje person skakar hand med alla utom sin partner, så beskriver denna graf en uppsättning handslag. Av denna anledning kallas han också för Cocktail Party Count .

Turan-grafen T ( n ,2) är en komplett tvådelad graf , och om n är jämn är det en Moore-graf . Om r är en divisor av n är Turan-grafen symmetrisk och starkt regelbunden , även om vissa författare anser att Turan-grafer är ett trivialt fall av stark regelbundenhet och därför utesluter dem från definitionen av starkt regelbundna grafer.

Turana-grafen har 3 a 2 b största klick , där 3 a + 2 b = n och b ≤ 2. Varje största klick bildas genom att välja en vertex från varje aktie. Detta antal största klick är det största möjliga av alla grafer med n hörn, oavsett antalet kanter i grafen (Moon och Moser, 1965). Dessa grafer kallas ibland Moon-Moser-grafer . $T(n,\lceil n/3\rceil )$

Andra egenskaper

Varje Turan-graf är en kograf . Således kan den bildas från individuella hörn genom en sekvens av operationer av disjunkt förening och komplement . I synnerhet kan en sådan sekvens startas genom att bilda alla oberoende uppsättningar av Turan-grafen som en disjunkt förening av isolerade hörn. Då är hela grafen komplementet till den disjunktiva föreningen av komplementen till dessa oberoende uppsättningar.

Chao och Novacky (1982) visade att Turan-grafer är kromatiskt unika - inga andra grafer har samma kromatiska polynom . Nikiforov (Nikiforov, 2005) använde Turan-grafer för att hitta den nedre gränsen för summan av k -te egenvärden för en graf och dess komplement.

Falls, Powell och Snoeyink utvecklade en effektiv algoritm för att hitta kluster av ortologa gengrupper i genomet genom att representera data som en graf och söka efter stora Turan-subgrafer.

Turan-grafer har också ett antal intressanta egenskaper relaterade till geometrisk grafteori . Pór och Wood (2005) ger en nedre gräns Ω(( rn ) 3/4 ) för varje tredimensionell Turan-grafinbäddning. Witsenhausen (1974) antog att den maximala summan av kvadrerade avstånd mellan n punkter inuti en boll i Rd av enhetsdiameter uppnås på den konfiguration som bildas av inbäddningen av Turan-grafen i hörnen på en vanlig simplex.

En graf G med n hörn är en subgraf till Turan-grafen T ( n , r ) om och endast om G medger en rättvis färgning i r färger. Nedbrytningen av Turan-grafen i oberoende uppsättningar motsvarar nedbrytningen av G i färgklasser. I synnerhet är Turan-grafen den enda maximala grafen för n -vertex med en rättvis färgning i r färger.

Anteckningar

Litteratur

C.Y. Chao, G.A. Novacky. På maximalt mättade grafer // Diskret matematik. - 1982. - T. 41 , nr. 2 . — S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Beräknar högstringenta COGs med hjälp av grafer av Turán-typ.
Peter Keevash, Benny Sudakov. Lokal densitet i grafer med förbjudna subgrafer // Combinatorics, Probability and Computing. - 2003. - T. 12 , nr. 2 . — S. 139–153 . - doi : 10.1017/S0963548302005539 .
JW Moon, L. Moser. Om klick i grafer // Israel Journal of Mathematics. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
Vladimir Nikiforov. Egenvärdesproblem av Nordhaus-Gaddum-typ . - 2005. - arXiv : math.CO/0506260 .
Attila Pór, David R Wood. Proc. Int. Symp. Grafritning (G.D. 2004) . — Föreläsningsanteckningar i datavetenskap nr. 3383, Springer-Verlag, 2005, s. 395–402. - doi : 10.1007/b105810 .
FS Roberts. Nya framsteg i kombinatorik. - Academic Press, 1969. - S. 301-310.
P. Turan. Om ett extremt problem inom grafteori // Matematiko Fizicki Lapok. - 1941. - T. 48 . — S. 436–452 .
HS Witsenhausen. På maximum av summan av kvadrerade avstånd under en diameterbegränsning // American Mathematical Monthly . — The American Mathematical Monthly, Vol. 81, nr. 10, 1974. - V. 81 , nr. 10 . - S. 1100-1101 . - doi : 10.2307/2319046 . — .

Länkar

Weisstein, Eric W. Cocktail Party Graph på Wolfram MathWorld .
Weisstein, Eric W. Octahedral Graph (engelska) på Wolfram MathWorld- webbplatsen .
Weisstein, Eric W. Turán Graph (engelska) på Wolfram MathWorld- webbplatsen .