Extreme Graph Theory

Extremal graph teoria on graafiteorian haara . Äärimmäinen graafiteoria tutkii graafien äärimmäisiä (maksimi- tai minimi-) ominaisuuksia , jotka täyttävät tietyt ehdot. Äärimmäisyydellä voi viitata erilaisiin graafin invarianteihin , kuten järjestykseen, kokoon tai ympärysmittaan. Abstraktimmassa mielessä teoria tutkii, kuinka graafin globaalit ominaisuudet vaikuttavat graafin paikallisiin alirakenteisiin [1] .

Esimerkkejä

Esimerkiksi yksinkertainen kysymys äärimmäisessä graafiteoriassa on "Millä n -pisteen asyklisillä graafilla on maksimimäärä reunoja?" Tämän kysymyksen äärigraafit ovat n -vertex- puita , joissa on n − 1 reunaa [2] . Yleisempi tyypillinen kysymys on: Kun annetaan graafin ominaisuus P , invariantti u [3] ja joukko kaavioita H , haluamme löytää minimiarvon m siten, että jokaisella H :n graafilla, jonka u on suurempi kuin m , on ominaisuus P . Yllä olevassa esimerkissä H oli graafien joukko, joissa on n kärkeä, P oli syklin ominaisuus ja u oli graafin reunojen lukumäärä. Siten minkä tahansa graafin, jossa on n kärkeä ja enemmän kuin n − 1 reunaa, täytyy sisältää sykli.

Jotkut funktionaaliset tulokset äärimmäisen graafin teoriassa ovat edellä mainitun kaltaisia kysymyksiä. Esimerkiksi kysymykseen, kuinka monta n -pisteisen graafin reunaa täytyy olla graafissa, jotta se sisältää välttämättä aligraafina k -koon klikkin , vastaa Turanin lause . Jos samankaltaisessa kysymyksessä klikkien sijaan kysytään täydellisiä moniosaisia graafisia, vastaus saadaan Erdős-Stone-lauseella .

Historia

Äärimmäinen graafiteoria tiukimmassa merkityksessä on graafiteorian haara, jota rakastetaan ja kehitetään Unkarissa.

- Bollobas, 2004

Äärimmäisen graafin teoria syntyi vuonna 1941, kun Turan osoitti lauseensa määrittelevänsä kertaluvun n graafit, jotka eivät sisällä täydellistä k:n graafia K k ja ovat koon suhteen äärimmäisiä (eli niillä on mahdollisimman vähän reunoja) [4] . Seuraava ratkaiseva vuosi oli 1975, jolloin Szémeredi osoitti lauseensa , tärkeän työkalun äärimmäisten ongelmien ratkaisemiseksi [4] .

Kaavion tiheys

Tyypillinen äärigraafiteorian tulos on Turanin lause . Lause vastaa seuraavaan kysymykseen. Mikä on suurin mahdollinen reunojen lukumäärä suuntaamattomassa graafissa G , jossa on n kärkeä ja joka ei sisällä K 3 :a (kolme kärkeä A , B , C , joiden reunat AB , AC , BC , eli kolmio) aligraafina? Täydellinen kaksiosainen graafi , jossa osat eroavat enintään 1, on ainoa äärimmäinen graafi, jolla on tämä ominaisuus. Count sisältää

\left\lfloor {\frac {n^{2}}{4}}\right\rfloor

kylkiluut. Samanlaisia kysymyksiä on esitetty useista muista H:n aligraafista K 3 : n sijaan . Esimerkiksi Zarankiewicz-tehtävä kysyy suurinta (reunojen lukumäärän mukaan) graafia, joka ei sisällä kiinteää täydellistä kaksiosaista graafia osagraafina, ja parillisen ääriviivan lauseessa kysytään suurinta graafia, joka ei sisällä parillisia kiinteä pituus. Turan löysi myös (ainutlaatuisen) suurimman graafin, joka ei sisällä K k :tä ja joka on nimetty hänen mukaansa, nimittäin Turan-graafin . Tämä kuvaaja on "k-1" riippumattomien joukkojen täydellinen liitto ja sillä on maksimi

\left\lfloor {\frac {(k-2)n^{2}}{2(k-1)}}\right\rfloor =\left\lfloor \left(1-{\frac {1 }{k-1}}\oikea){\frac {n^{2}}{2}}\oikea\rfloor

kylkiluut. Suurin n -pisteinen graafi, joka ei sisällä C 4 :ää, on

\left({\frac {1}{2}}+o(1)\right)n^{3/2}

kylkiluut.

Vähimmäistutkintoehdot

Mainitut lauseet antavat edellytykset pienten esineiden esiintymiselle (mahdollisesti) suuren graafin sisällä. Vastakkaisina ääripäinä voidaan etsiä ehtoa, joka pakottaa olemassa olevan rakenteen, joka kattaa kaikki kärjet. Mutta kaavio

{\binom {n-1}{2}}

reunoilla voi olla erillisiä pisteitä, vaikka lähes kaikki mahdolliset reunat ovat graafissa, mikä tarkoittaa, että edes erittäin tiheillä graafilla ei välttämättä ole kiinnostavaa rakennetta, joka kattaisi kaikki kärjet. Yksinkertainen reunamäärään perustuva ehto ei anna tietoa siitä, kuinka reunat jakautuvat graafissa, joten usein tällainen ehto antaa epämiellyttäviä tuloksia erittäin suurille rakenteille. Sen sijaan otamme käyttöön vähimmäistutkinnon käsitteen. Graafin G minimiaste määritellään seuraavasti

\delta (G)=\min _{v\in G}d(v).

Suuren vähimmäisasteen määrittäminen poistaa vastalauseen, että "patologisia" huippuja voi olla olemassa. Jos graafin G minimiaste on esimerkiksi 1, ei siinä voi olla eristettyjä pisteitä (vaikka G :ssä olisi hyvin vähän kulmia).

Klassinen tulos on Diracin lause , jonka mukaan mikä tahansa graafi G , jossa on n kärkeä ja minimiaste vähintään n/2 , sisältää Hamiltonin syklin .

Katso myös

Ramseyn teoria

Muistiinpanot

↑ Diestel, 2010 .
↑ Bollobás, 2004 , s. 9.
↑ Yleisesti ottaen graafin ja invariantin ominaisuus ovat yksi ja sama.
↑ 1 2 Bollobás, 1998 , s. 104.

Kirjallisuus

Bela Bollobas. Extreme Graph Theory. - New York: Dover Publications , 2004. - ISBN 978-0-486-43596-1 .
Bela Bollobas. Moderni graafiteoria. - Berliini, New York: Springer-Verlag , 1998. - s. 103-144. - ISBN 978-0-387-98491-9 .
Reinhard Diestel. graafiteoria . – 4. — Berliini, New York: Springer-Verlag, 2010. — s. 169–198. — ISBN 978-3-642-14278-9 . Arkistoitu 28. toukokuuta 2017 Wayback Machineen
- Reinhard Distel. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo, 2002. - ISBN 5-86134-101-X UDC 519.17.
M. Simonovits. Diat Chorinin kesäkoulun luennoista, 2006. .