Turanin lause

Turánin lause vastaa kysymykseen graafin reunojen enimmäismäärästä ilman täydellistä n-pisteen aligraafia .

Kielletyn osagraafin ongelman esitti ensimmäisen kerran unkarilainen matemaatikko Pal Turan vuonna 1941 .

Sanamuoto

Merkintä

Merkitään täydellisellä n-pisteen graafilla. $K_n$

Määrittelemme graafin , jossa on kärkipisteet seuraavasti. Jaetaan kaikki kärjet "melkein samansuuruisiin" ryhmiin (eli otetaan ryhmät kärkien mukaan ja ryhmät kärkien mukaan, jos jäännös on ) ja yhdistetään kaikki eri ryhmien pisteparit reunoilla. Siten saamme -osittaisen graafin. $T_{n}(v)$ $v$ $n-1$ $r$ $m+1$ $n-1-r$ $m$ $v:(n-1)=m$ $r$ $(n-1)$

Merkitään reunojen enimmäismäärällä, jonka graafilla, jolla on pisteet ja joka ei sisällä isomorfista aligraafia, voi olla . $ex(v,n)$ $v$ $K_n$

Lause

Kaikista graafista pisteissä, jotka eivät sisällä aligraafia , graafilla on enimmäismäärä reunoja . Jos , Missä on jaon loppuosa , Tämä maksimi on yhtä suuri $v$ $K_n$ $T_{n}(v)$ $v=m(n-1)+r$ $r$ $v$ $n-1$

ex(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2 }}

Muistiinpanot

Pääkaavalla voidaan kirjoittaa lyhyemmin: $n\leq 8$ $ex(v,n)=\left[v^{2}\cdot {\frac {n-2}{2n-2}}\right]$ .

Todiste

Todistus voidaan tehdä esimerkiksi matemaattisella induktiolla graafin kärkien lukumäärästä . $v$

Otamme käyttöön induktion kokonaisen aligraafin kärkien lukumäärälle. $n$

Pohja . Todistus: Otamme käyttöön induktion kärkien lukumäärälle. $n = 3$
- Pohja . Näissä tapauksissa arvio on ilmeinen. ${\näyttötyyli n=1,2}$
- Vaihe: Anna osoittautui . Todistetaan puolesta . Jos graafissa ei ole reunoja, kaikki on todistettu. Muussa tapauksessa valitse reuna. Huomaa, että enintään yksi reuna menee tähän reunaan graafin jäljellä olevista pisteistä (muuten on kolmio) nämä reunat ovat enintään . Kaavion loppuosaan sovelletaan induktiohypoteesia. Mistä reunojen kokonaismäärä on enintään . Mitä vaadittiin. $k$ $k+2$ $\Nuoli oikealle$ $k$ ${\frac {k^{2}-r^{2}}{4}}+k+1={\frac {(k+2)^{2}-r^{2}}{4 }}$
Pohja on todistettu.

Vaihe. Olkoon totta, me todistamme puolesta . Esittelemme induktion. Pohja . Näissä tapauksissa väite on ilmeinen. Vaihe. Olkoon totta, me todistamme puolesta . Jos graafissa ei ole täydellistä graafia pisteissä, käytämme edellistä vaihetta (ilmeisesti estimaatti on parempi). Muuten valitsemme sen. Jokaisesta muusta kärjestä siihen ei mene enempää kuin reunat, eli enintään . Siksi kaavion reunojen kokonaismäärä ei ylitä $n-1$ $n$ $k=1,2,\ldots ,n-1$ $k$ $k+n-1$ $n-1$ $n-2$ $k\cdot (n-2)$

( n − 2 ) ( k 2 − r 2 ) 2 n − 2 + ( n − yksi ) ( n − 2 ) 2 + k ⋅ ( n − 2 ) + r ⋅ ( r − yksi ) 2 = ( n − 2 ) ( ( k + n − yksi ) 2 − r 2 ) 2 n − 2 + r ⋅ ( r − yksi ) 2 {\displaystyle {\frac {(n-2)(k^{2}-r^{2})}{2n-2))+{\frac {(n-1)(n-2)}{2 }}+k\cpiste (n-2)+{\frac {r\cdot (r-1)}{2}}={\frac {(n-2)((k+n-1)^{2 }-r^{2})}{2n-2}}+{\frac {r\cdot (r-1)}{2}}} ${\frac {(n-2)(k^{2}-r^{2})}{2n-2))+{\frac {(n-1)(n-2)}{2 }}+k\cpiste (n-2)+{\frac {r\cdot (r-1)}{2}}={\frac {(n-2)((k+n-1)^{2 }-r^{2})}{2n-2}}+{\frac {r\cdot (r-1)}{2}}$ Mitä vaadittiin. Induktiovaihe on todistettu.

Muunnelmia ja yleistyksiä

Turánin lauseen todistus saa aikaan hieman vahvemman tuloksen: jokaiselle graafille , joka ei sisällä kopiota täydellisestä graafista, on -osittaisgraafi , jolla on sama pistejoukko kuin kunkin kärjen asteella vähintään y . $\Gamma$ $K_{n+1}$ $n$ $\gamma '$ $\Gamma$ $\Gamma$

Kirjallisuus

"Graafiteoria" O. Ore. 1980
Berge C. Graphs (toinen tarkistettu painos), North-Holland, Amsterdam-New York-Oxford, 1985.
Lovasz L. Kombinatoriset ongelmat ja harjoitukset, Academiqi Kiado, Budapest, 1979.

Ulkoiset linkit

Turanin lause Graafiteorian sanakirjassa