Sažetak Svrha ovoga članka je predstaviti jedan of fundamentalnih rezultata iz teorije grafova poznat pod nazivom Turánov teorem te prezentirati pet dokaza koristeći pritom alate iz različitih grana matematike. Prva tri dokaza se uglavnom oslanjaju na teoriju grafova i metode prebrojavanja, a preostala dva na matematičku analizu, algebru i vjerojatnost.


Ključne riječi multipartitan graf, klika, Turánov graf, Turánov teorem



Abstract The purpose of this article is to present one of the fundamental results in graph theory known as Turán's theorem and present five proofs by using tools from various branches of mathematics. First three rely almost exclusively on graph theory and counting methods, while the other two rely on mathematical analysis, algebra, and probability.


Keywords multipartite graph, clique, Turán graph, Turán's theorem




Pál Turán je bio vrsni mađarski matematičar čije su ideje i rezultati znatno utjecali na razvoj teorije grafova, ali i raznih drugih grana matematike. Tome je pridonijela i plodna suradnja s velikim matematičarom Paulom Erdösom: trajala je 46 godina i rezultirala s 28 zajedničkih znanstvenih radova!
Pál Turán je rođen 18. kolovoza 1910. u Budimpešti. Učiteljsku diplomu iz matematike i znanosti dobio je na Sveučilištu u Budimpešti 1933., a doktorirao je pod vodstvom Leopolda Fejéra 1935. godine na Eötvös Loránd Sveučilištu. Skoro trideset godina je radio zajedno s Fejérom, što je vidljivo iz brojnih zajedničkih radova iz matematičke analize, no najviše je bio privučen teoriji brojeva i u tom području je ostvario rezultat međunarodnog značaja. Brojni matematičari iz cijeloga svijeta dolazili su kod Turána pisati disertacije pod njegovim vodstvom. S prijateljima je volio raspravljati o matematici i matematičkim istraživanjima. Govorio je kako napredak u matematici dolazi kroz rješavanje otvorenih problema: ispočetka dokaz može biti vrlo kompliciran, no prije ili kasnije bit će pronađene lakše metode. Metoda i elegancija dokaza su sekundarni.
Ovaj rad je usredotočen na Turánov doprinos teoriji grafova, konkretno na iznimno važan teorem koji danas nosi njegovo ime: Turánov teorem. Radi se o jednom od fundamentalnih rezultata koji služi kao početna točka u istraživanju raznih drugih problema. Navest ćemo dokaze koji su otkriveni i ponovno otkriveni, od kojih se neki ne oslanjaju samo na teoriju grafova, nego i na druge grane matematike poput algebre i vjerojatnosti.





Broj elemenata danog skupa A označit ćemo s |A| i zvati ga kardinalitetom skupa A. Zatim ćemo s \binom{n}{k} označiti broj svih k-članih podskupova skupa od n elemenata.


U ovome radu ćemo pod pojmom grafa podrazumijevati jednostavan neusmjereni graf. Neka je G graf sa skupom vrhova V = \lbrace 1,2,\dots,n\rbrace. Za neka dva vrha kažemo da su susjedni ako su krajevi istog brida. U nastavku ćemo s ij ili ji označavati brid kojemu su i i j krajevi.
Za graf G kojemu su svaka dva vrha spojena bridom kažemo da je potpun i označavamo ga s K_{n}, gdje je n broj vrhova. Graf K_{3} se još zove i trokut.
Za graf G'=(V',E') kažemo da je podgraf grafa G ako vrijedi V' \subseteq V i E' \subseteq E, pri čemu krajevi svih bridova u E' moraju biti sadržani u skupu V'. K-klika u G je potpun podgraf od G s k vrhova i označavamo ga s K_{(k)}.
Stupanj d(v) vrha v u grafu G je broj bridova kojima je v jedan od krajeva. Prema definiciji grafa, stupanj vrha jednak je broju njegovih susjeda. Izolirani vrh je vrh stupnja nula. Graf G je {k-regularan} ako su mu svi vrhovi stupnja k. Ukoliko nije potrebno istaknuti koliki je stupanj vrha u takvom grafu, koristit ćemo naziv regularan graf.
Neka je k prirodan broj i neka k \geq 2. Graf G je {k-partitan} ako mu se skup vrhova V mo\v{z}e particionirati u k podskupova tako da nijedan brid nema oba kraja u istom podskupu. Za k=2 takve grafove još zovemo i bipartitnim grafovima. Potpunk-partitan graf} je jednostavan k-partitan graf u kojemu je svaki par vrhova iz različitih skupova k-particije spojen bridom. Ako su V_{1},\ldots,V_{k} skupovi k-particije od V i |V_{i}|=n_{i}, i=1,\ldots,k, tada potpun k-partitan graf označavamo s K_{n_{1},n_{2},\ldots,n_{k}}. Za graf kažemo da je potpun multipartitan ako je potpun k-partitan za neko k\geq 2.
Slijedi tvrdnja koja će nekoliko puta biti korištena u ovom članku.



Proučavajući grafove, Turán je tražio odgovor na sljedeće pitanje: koliko najviše bridova može imati graf s n\geq 2 vrhova koji ne sadrži kliku K_{(k)}? Označimo traženi broj s t(n,k). Vrijedi t(n,2) = 0 i t(n,k) je rastuća funkcija po k. Primjer grafa s n vrhova koji sadrži t(n,k) bridova je potpun (k-1)-partitan graf K_{n_{1}, \ldots, n_{k-1}}, n=n_{1}+\cdots+n_{k-1}, pa će formula za t(n,k) biti glavni rezultat kojim ćemo se intenzivno baviti u ovome radu. Na slici 1 prikazan je K_{2,2,3}. Graf K_{n_{1}, \ldots, n_{k-1}} sadrži \displaystyle{ \sum_{i \lt j} n_{i} n_{j}} bridova. Članovi ove sume mogu se dobiti iz jednakosti odnosno vrijedi Problem maksimizacije sume na lijevoj strani jednakosti (3.1) ekvivalentan je problemu minimizacije sume na desnoj strani iste jednakosti uz uvjet \displaystyle{\sum_{i=1}^{k-1} n_{i}=n}. Prema Cauchyjevoj nejednakosti primjenjenoj na brojeve n_{1},\ldots,n_{k-1} i k-1 jedinica 1,\ldots,1 dobivamo iz čega proizlazi Jednakost vrijedi ako i samo ako n_{i}=\frac{n}{k-1}, i=1,\ldots,k-1. Zaključujemo da graf K_{n_{1}, \ldots, n_{k-1}} sadrži najveći mogući broj bridova ako i samo ako su mu svi skupovi particije jednakobrojni, odnosno n_{1}=n_{2}=\cdots=n_{k-1}=\frac{n}{k-1}. No, Turánovo pitanje podrazumijeva proizvoljno zadane brojeve n i k pa je jednakobrojnost skupova particije moguća ako i samo ako je n djeljiv s k-1. U suprotnom je dovoljno zahtijevati da kardinaliteti skupova particije budu približno jednaki, odnosno | n_{i} - n_{j} | \leq 1, \forall i,j=1,\ldots,{k-1}, i\neq j.
Vratimo se na slučaj kada k-1 dijeli n. Iz (3.1) tada dobivamo pa je ovo najveći mogući broj bridova proizvoljnog jednostavnog grafa s n vrhova koji ne sadr\v{z}i kliku K_{(k)}.
Općenito, grafovi K_{n_{1}, \ldots, n_{k-1}} za koje vrijedi | n_{i} - n_{j} | \leq 1, \forall i,j=1,\ldots,{k-1}, i\neq j, zovu se Turánovi grafovi i označeni su s T(n,k). Sada smo u mogućnosti iskazati Turánov teorem i navesti nekoliko različitih dokaza.





Preciznija varijanta ovog teorema sadrži i tvrdnju da je graf K_{n_{1}, \ldots, n_{k-1}} za koji vrijedi | n_{i} - n_{j} | \leq 1, \forall i,j=1,\ldots,{k-1}, i\neq j, jedinstven graf bez klike K_{(k)} s najvećim brojem bridova t(n,k). Otuda i naziv za takav graf: Turánov graf. Mi ćemo se usredotočiti na dokazivanje nejednakosti (4.1), ali ćemo u nekim dokazima pokazati da jednakost u (4.1) vrijedi ako i samo ako G=T(n,k) za proizvoljan k.

Godine 1907. nizozemski matematičar Willem Mantel dokazao je tvrdnju da graf bez trokuta sadrži najviše n^{2}/4 bridova, a graf za koji se postiže gornja granica je K_{n/2,n/2} za n paran, odnosno K_{(n-1)/2,(n+1)/2} za n neparan [9]. Danas je ta tvrdnja u literaturi poznata kao Mantelov teorem. Time je dokaz Turánova teorema za slučaj k=3 bio poznat prije nego se Turán počeo baviti grafovima s proizvoljno zadanim k. Mantelov teorem ovdje nećemo dokazati. Navedimo još neke pojmove i tvrdnje koje će nam trebati u nastavku članka. Ukoliko s d_{i} označimo stupanj vrha i u grafu s n vrhova, vrijedi Skup A \subseteq V vrhova u grafu zovemo nezavisnim ako ne sadrži susjedne vrhove. Primjerice, skup V_{i} particije skupa vrhova u grafu K_{n_{1}, \cdots, n_{k-1}} je nezavisan za svaki i=1,\ldots,k-1. Broj \alpha (G) = \max \lbrace |U|: U \subseteq V,\, \, U nezavisan \rbrace naziva se broj nezavisnosti grafa G.

U nastavku ćemo navesti pet različitih dokaza Turánovog teorema za proizvoljan k.


Koristimo jaku indukciju po broju n. Ona se od obične indukcije razlikuje jedino u pretpostavci, tj. ako smo u bazi jake indukcije dokazali da tvrdnja vrijedi za k=1, onda pretpostavka jake indukcije glasi da tvrdnja vrijedi za sve k\lt n pa u koraku jake indukcije treba dokazati da tvrdnja vrijedi za k=n.

Nejednakost (4.1) trivijalno vrijedi za sve prirodne brojeve manje od n. Neka je G graf sa skupom vrhova V=\lbrace 1, \ldots, n\rbrace koji ne sadrži k-klike, a ima najveći mogući broj bridova. Tada G sadrži (k-1)-klike jer bismo u suprotnom mogli dodati bridove u G. Neka je A skup vrhova (k-1)-klike i B=V \backslash A, \,|B|=n-k+1 (slika 3). Znamo da (k-1)-klika sadrži \binom{k-1}{2} bridova. Slijede gornje granice za broj bridova e_{B} koji spajaju vrhove u B i broj bridova e_{A,B} između A i B. Prema pretpostavci indukcije znamo da vrijedi S obzirom da G ne sadrži k-klike, svaki j \in B je susjed s najviše k-2 vrhova u A pa dobivamo e_{A,B} \leq (k-2)(n-k+1). Slijedi

Ovaj dokaz koristi strukturu Turánovih grafova. Neka je m \in V vrh najvećeg stupnja u grafu G, odnosno \displaystyle{d_{m} = \max_{1 \leq j \leq n} d_{j}}. Označimo sa S susjede of m, |S|=d_{m} i stavimo T=V/S. Kako G ne sadrži k-klike i svi vrhovi iz S su susjedi vrhu m, to S ne sadrži (k-1)-klike. Konstruirajmo graf H na skupu V (slika 4). Graf H odgovara grafu G na S i sadrži sve bridove između S i T (dakle, u H je svaki vrh iz S spojen bridom sa svakim vrhom iz T), ali ne i bridove među vrhovima iz T. Skup T je nezavisan u H te H ne sadrži k-klike. Neka je d'_{j} stupanj vrha j u H. Ako je j \in S, tada iz konstrukcije grafa H vrijedi d_{j}' \geq d_{j}. Ako je j \in T, tada imamo d_{j}' = |S| = d_{m} \geq d_{j} prema izboru vrha m. Vidimo da je |E(H)| \geq |E| i zaključujemo da od svih grafova s najvećim brojem bridova, jedan mora biti oblika kakvog je H. Koristeći indukciju na skupu S, zaključujemo da se među grafovima s najvećim brojem bridova nalazi graf K_{n_{1},\ldots,n_{k-1}}. Preciznije, graf H na S ima najviše bridova koliko i Turánov graf K_{n_{1},\ldots,n_{k-2}} na S. Slijedi |E|\leq K_{n_{1},\ldots,n_{k-1}}, pri čemu n_{k-1}=|T|, odnosno \displaystyle{|E|\leq \sum_{i \lt j}n_{i} n_{j}}, što implicira (4.1). 
Navedeni dokaz se odnosi na precizniju varijantu teorema 3, odnosno uključuje i dokaz da jednakost u (4.1) vrijedi ako i samo ako G=T(n,k).


Ovaj dokaz generalizira ideju prvog dokaza za slučaj k=3 i daje procjenu broja h-klika. Neka je G proizvoljan graf sa skupom vrhova V=\lbrace 1,\dots,n\rbrace i označimo s \mathscr{C}_{h} skup h-klika u G, pri čemu |\mathscr{C}_{h}|=C_{h}. Primjerice, imamo C_{1}=n, C_{2}=|E|, a C_{3} je broj trokuta u G. Za A \in \mathscr{C}_{h} označimo s d(A) broj (h+1)-klika koje sadrže A. Brojeći na dva načina, dobivamo i ovo je poopćenje jednakosti (4.2). Neka je h\geq 2. Za A \in \mathscr{C}_{h} označimo s A^{(1)}, \dots, A^{(h)}(h-1)-klike sadržane u A (takvih klika je ukupno h jer je broj (h-1)-klika u h-kliki jednak broju načina da od ukupno h vrhova odaberemo njih h-1).


Uzmimo A \in \mathscr{C}_{h}, B=V \backslash A, |B|=n-h. Među vrhovima skupa B postoji točno d(A) vrhova koji su susjedni svim vrhovima u A. Svaki od preostalih vrhova u B je susjed najviše jednoj (h-1)-kliki A^{(i)}, tvoreći h-kliku (slika 5). Dobivamo (primijetimo da se pojavljuje - 1 zbog A^{(i)} \subseteq A) odnosno Sumiranjem po svim A \in \mathscr{C}_{h} dobivamo S obzirom da u proizvoljnom grafu G vrijedi zaključujemo te prema (4.3) imamo Uvrštavanjem (4.6) i (4.7) u (4.5) dobivamo Primjenom Cauchyjeve nejednakosti (2.1) na sve brojeve d(B) iz skupa \mathscr{C}_{h-1} te na C_{h-1} jedinica, dobivamo što je ekvivalentno (4.4).
Da bismo dokazali (4.1), moramo naći vezu između nejednakosti (4.4) i broja bridova |E|. Stavimo S obzirom da desna strana od (4.9) raste po \vartheta, moramo dokazati da vrijedi \vartheta \leq k-1 za grafove bez k-klika (jer se desna strana nejednakosti (4.1) može zapisati ovako: \left(1-\frac{1}{k-1}\right)\frac{n^{2}}{2}).


Za h=1 imamo C_{1} = n i C_{2} = |E| pa vrijedi (4.10) pri čemu jednakost vrijedi iz definicije \vartheta. Koristeći (4.4) i indukciju po h, zaključujemo što je i trebalo dokazati. Ako G ne sadrži k-klike, onda vrijedi C_{k} = 0 i zaključujemo \vartheta \leq k-1 iz (4.10) za h+1=k. 


Do sada su se dokazi Turánova teorema oslanjali na razne metode prebrojavanja. Sljedeća dva dokaza koriste potpuno drugačije tehnike.


Neka je G proizvoljan graf sa skupom vrhova V = \lbrace 1, \ldots, n \rbrace. S \omega = \omega (G) označimo broj vrhova u najvećoj kliki od G. Nadalje, svakom vrhu i \in V pridružimo realnu varijablu x_{i} i promatramo funkciju f(x_{1}, \dots, x_{n}) =\displaystyle{ 2 \sum_{ij \in E} x_{i} x_{j}}.


S obzirom da je f neprekidna funkcija na kompaktnom skupu K=\lbrace (x_{1},\ldots,x_{n})\in\mathbb{R}^{n}\,:\, \sum_{i=1}^{n} x_{i} = 1, x_{i} \geq 0, i=1,\ldots,n\rbrace (K je tetraedar u \mathbb{R}^{n} omeđen hiperravninom x_{1}+\cdots +x_{n}=1 i koordinatnim osima x_{i}, i=1,\ldots,n), to postoji vektor x=(x_{1},\ldots,x_{n}) u kome f ima najveću vrijednost (vidi [15]). Među takvim vektorima x odaberemo onoga koji ima najviše nul komponenti. (Primijetimo da ako f postiže najveću vrijednost na rubu od K, tada je barem jedna komponenta x_{i} jednaka nuli.) Neka je C= \lbrace i \in V: x_{i} \gt 0 \rbrace. Pokažimo najprije da je C skup vrhova klike. Pretpostavimo suprotno, tj. bez smanjenja općenitosti, uzmimo 1,2 \in C, ali 12 \notin E. Za svaki t \in \mathbb{R} za koji vrijedi -x_{1} \leq t \leq x_{2} vektor x_{t} = (x_{1} + t, x_{2} - t, x_{3}, \dots, x_{n}) zadovoljava uvjete u (4.11) i dodatno je f(x_{t}) linearna funkcija u varijabli t jer se produkt (x_{1} + t)(x_{2} - t) ne pojavljuje u f(x_{t}) zbog 12 \notin E. Zbog odabira x, f(x_{t}) postiže maksimum u t=0. Slijedi da je f(x_{t}) konstanta za svaki t. Za t=x_{2}, \bar{x} = (x_{1} + x_{2}, 0, x_{3}, \dots, x_{n}) dobivamo f(\bar{x}) = f(x), što je u kontradikciji s izborom vektora x. Možemo pretpostaviti da f(x) ima najveću vrijednost za vektor x za koji je C = \lbrace i\in V: \: x_{i} \gt 0 \rbrace skup vrhova klike.
Budući da je zaključujemo da je f(x) najveći ako i samo ako je \displaystyle{\sum_{i \in C} x_{i}^{2}} najmanji, a to je uz pretpostavku \displaystyle{ \sum_{i \in C} x_{i} = 1} onda kada je x_{i} = 1/|C| te dobivamo pri čemu vrijedi jednakost za |C| = \omega, što smo i htjeli dokazati. Nejednakost (4.1) odmah slijedi. Postavljanjem x_{i} = 1/n imamo f(x) = 2|E|/n^{2} i zbog toga dobivamo jer G ne sadrži K_{(k)}. 


Zadnji dokaz koristi alate iz područja teorije vjerojatnosti. Neka je G proizvoljan graf sa skupom vrhova V= \lbrace 1, \ldots, n\rbrace.


S jednakom vjerojatnošću 1 / n! biramo permutaciju (\pi_{1}, \dots, \pi_{n}) skupa V i konstruiramo skup C na sljedeći način: stavimo \pi_{i} u C ako i samo ako je \pi_{i} susjedan svim \pi_{j}, \, j\lt i. Prema definiciji C je klika u G. Neka je X=|C| odgovarajuća slučajna varijabla. Imamo X =\displaystyle{ \sum_{i=1}^{n} X_{i} }, gdje je X_{i}=1 ako i \in C, a X_{i}=0 ako i\notin C. Sada zaključujemo da je i \in C s obzirom na permutaciju (\pi_{1}, \dots, \pi_{n}) ako i samo ako se i pojavljuje prije svih n-1-d_{i} ne-susjeda od i, odnosno ako je i prvi među i i njegovim ne-susjedima. Zaključujemo da je očekivanje slučajne varijable X_{i} dano s EX_{i} = 1 / n-d_{i} i nadalje vrijedi zbog linearnosti očekivanja. Posljedično, mora postojati klika C s najmanje E(|C|) vrhova, što je tvrdnja (4.12). Da bismo iz (4.12) došli do tvrdnje Turánovog teorema, koristimo Cauchyjevu nejednakost oblika pri čemu x_{i} = n-d_{i}. Uistinu, (4.12) i (4.2) impliciraju Ako G ne sadrži K_{(k)}, onda \omega (G) \leq k-1 i (4.13) se svodi na (4.1).