Turanin kreivi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 9. lokakuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Turanin kreivi

Nimetty	Pal Turan
Huiput	n
kylkiluut	$\left\lfloor {\frac {(r-1)n^{2}}{2r}}\right\rfloor$
Säde	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.$
Halkaisija	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.$
Ympärysmitta	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\teksti{muuten)) \end{array}}\right.$
Kromaattinen numero	r
Nimitys	= T ( n , r )
Mediatiedostot Wikimedia Commonsissa

Turan-graafi T ( n , r ) on graafi, joka muodostetaan jakamalla n kärkeä r osajoukkoon, jonka koko on mahdollisimman lähellä, ja tämän graafin kärjet on yhdistetty reunalla, jos ne kuuluvat eri osajoukkoon. Kaaviossa on koon osajoukkoja ja koon osajoukkoja . Tämä on siis täydellinen r -osakaavio $(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 }.

Jokaisella kärjellä on aste joko , tai . Reunojen lukumäärä on $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}}.

Graafi on säännöllinen , jos n on jaollinen r :llä .

Turanin lause

Turanin graafit on nimetty Pal Turanin mukaan, joka käytti niitä todistaakseen Turanin lauseen , joka on tärkeä tulos extremaaligrafiikkateoriassa .

Dirichletin periaatteen mukaan mikä tahansa r + 1 -pisteiden joukko Turan-graafissa sisältää kaksi kärkeä samasta graafin murto-osasta. Turan-graafi ei siis sisällä r + 1 -kokoista klikkia . Turan-lauseen mukaan Turan-graafilla on suurin mahdollinen määrä reunoja kaikkien graafien joukossa, joissa ei ole r + 1 -kokoisia klikejä, joilla on n kärkeä. Kivash ja Sudakov (Keevash ja Sudakov, 2003) osoittivat, että Turan-graafi on ainoa graafi, jossa ei ole luokkaa n olevia r + 1 -klikejä, jossa α n -pisteiden osajoukolla on vähintään reunat, jos α on riittävän lähellä 1 :tä. Erdős–Stone-lause laajentaa Turan-lausetta rajoittamalla graafin, jolla ei ole kiinteää Turan-graafia aligraafina, reunojen määrää. Tämän lauseen seurauksena äärimmäisten graafien teoriassa mille tahansa kielletylle osagraafille voidaan osoittaa samanlaiset rajat aligraafin kromaattisesta numerosta riippuen . ${\frac {r\,{-}\,1}{2r}}(2\alpha -1)n^{2}$

Erikoistilaisuudet

Jotkut Turan-kaavioiden parametrin r arvot johtavat merkittäviin kaavioihin, joita tutkitaan erikseen.

Turan-graafi T (2 n , n ) saadaan poistamalla täydellinen vastaavuus täydellisestä graafista K 2 n . Kuten Roberts ( Roberts 1969 ) on osoittanut, tämän graafin kehys on täsmälleen n . Tätä jaarlia kutsutaan joskus Earl of Robertsiksi . Tämä kaavio on myös 1 - runkoinen n - ulotteinen kopio . Esimerkiksi kuvaaja T (6,3) = K 2,2,2 on säännöllisen oktaedrin kuvaaja . Jos n paria tulee juhliin ja jokainen kättelee kaikkia muita paitsi kumppaniaan, tämä kaavio kuvaa kädenpuristussarjaa. Tästä syystä häntä kutsutaan myös Cocktail Party Countiksi .

Turan-graafi T ( n ,2) on täydellinen kaksiosainen graafi , ja jos n on parillinen, se on Mooren graafi . Jos r on n: n jakaja , Turan-graafi on symmetrinen ja vahvasti säännöllinen , vaikka jotkut kirjoittajat pitävät Turan-graafit triviaalina vahvan säännöllisyyden tapauksena ja jättävät ne siksi pois vahvasti säännöllisten graafien määritelmästä.

Turana-graafissa on 3 a 2 b suurinta klikkausta , missä 3 a + 2 b = n ja b ≤ 2. Jokainen suurin klikki muodostetaan valitsemalla jokaisesta osuudesta yksi kärki. Tämä suurimpien klikkien määrä on suurin mahdollinen kaikista graafista, jossa on n kärkeä, riippumatta graafin reunojen lukumäärästä (Moon ja Moser, 1965). Näitä kaavioita kutsutaan joskus Moon-Moser-kaavioiksi . $T(n,\lceil n/3\rceil )$

Muut ominaisuudet

Mikä tahansa Turan-graafi on kopiokuva . Siten se voidaan muodostaa yksittäisistä pisteistä hajaliiton ja komplementin operaatioiden sarjalla . Erityisesti tällainen sekvenssi voidaan aloittaa muodostamalla kaikki Turan-graafin itsenäiset joukot eristettyjen pisteiden hajaliitoksi. Tällöin koko graafi on näiden itsenäisten joukkojen komplementtien disjunktiiviliiton komplementti.

Chao ja Novacky (1982) osoittivat, että Turan-graafit ovat kromaattisesti ainutlaatuisia – millään muulla graafilla ei ole samoja kromaattisia polynomeja . Nikiforov (Nikiforov, 2005) käytti Turan-graafia löytääkseen alarajan graafin ja sen komplementin k : nnen ominaisarvon summalle.

Falls, Powell ja Snoeyink kehittivät tehokkaan algoritmin ortologisten geeniryhmien klustereiden löytämiseksi genomista esittämällä tiedot graafina ja etsimällä suuria Turan-aligraafia.

Turaanigrafeilla on myös useita mielenkiintoisia geometriseen graafiteoriaan liittyviä ominaisuuksia . Pór ja Wood (2005) antavat alarajan Ω(( rn ) 3/4 ) mille tahansa kolmiulotteiselle Turan-graafin upotukselle. Witsenhausen (1974) arveli, että yksikköhalkaisijan Rd : n pallon sisällä olevien n pisteen välisten etäisyyksien maksimisumma saavutetaan konfiguraatiossa, joka muodostuu upottamalla Turan-graafi säännöllisen simpleksin kärkiin.

Graafi G , jossa on n kärkeä, on Turan-graafin T ( n , r ) aligraafi , jos ja vain jos G sallii reilun värityksen r värissä. Turan-graafin hajottaminen itsenäisiksi joukoiksi vastaa G :n hajoamista väriluokkiin. Erityisesti Turan-graafi on ainoa n -pisteen maksimigraafi, jolla on reilu väritys r - väreissä.

Muistiinpanot

Kirjallisuus

C.Y. Chao, G.A. Novacky. Maksimikyllästetyillä kaavioilla // Diskreetti matematiikka. - 1982. - T. 41 , no. 2 . — S. 139–143 . - doi : 10.1016/0012-365X(82)90200-X .
Craig Falls, Bradford Powell, Jack Snoeyink. Erittäin vaativien COG-arvojen laskeminen Turán-tyyppisten kaavioiden avulla.
Peter Keevash, Benny Sudakov. Paikallinen tiheys kaavioissa, joissa on kiellettyjä aligraafia // Kombinatoriikka, todennäköisyys ja laskeminen. - 2003. - T. 12 , no. 2 . - S. 139-153 . - doi : 10.1017/S0963548302005539 .
JW Moon, L. Moser. Klikkeistä kaavioissa // Israel Journal of Mathematics. - 1965. - T. 3 . — S. 23–28 . - doi : 10.1007/BF02760024 .
Vladimir Nikiforov. Nordhaus-Gaddum-tyyppiset ominaisarvoongelmat . - 2005. - arXiv : math.CO/0506260 .
Attila Pór, David R Wood. Proc. Int. Symp. Graph Drawing (G.D. 2004) . — Tietojenkäsittelytieteen luentomuistiinpanot nro. 3383, Springer-Verlag, 2005, s. 395–402. - doi : 10.1007/b105810 .
FS Roberts. Viimeaikainen kehitys kombinatoriikassa. - Academic Press, 1969. - S. 301-310.
P. Turan. Äärimmäisestä graafiteorian ongelmasta // Matematiko Fizicki Lapok. - 1941. - T. 48 . — S. 436–452 .
HS Witsenhausen. Halkaisijarajoitteen alaisten etäisyyksien neliösumman maksimiarvosta // American Mathematical Monthly . — The American Mathematical Monthly, Voi. 81, nro. 10, 1974. - V. 81 , no. 10 . - S. 1100-1101 . - doi : 10.2307/2319046 . — .

Linkit

Weisstein, Eric W. Cocktail Party Graph Wolfram MathWorldissä .
Weisstein, Eric W. Octahedral Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .
Weisstein, Eric W. Turán Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .