Mi is… a grafon?

A nagyméretű gráfok mindenütt jelen vannak a matematikában, és a szerkezetük leírása a modern kombinatorika egyik fontos célja. A leghíresebb leírást a Szemerédi-féle regularitási lemma (1978) adja meg, amely azt állítja, hogy bármely kellően nagyméretű gráf csúcsai feloszthatók nagyjából azonos méretű halmazokra úgy, hogy az élek a halmazok többsége között jó közelítéssel véletlenszerűnek tűnnek.

A nagy véges objektumok tanulmányozásának egyik módja az, hogy az egyre nagyobb és nagyobb objektumok sorozatai helyett áttérünk ideális limeszobjektumokra. Ha megfelelően járunk el, a limeszobjektumok tulajdonságai tükrözik az őket közelítő véges objektumok tulajdonságait, és fordítva.

A grafonok a nagy véges gráfok sorozataihoz tartozó limeszobjektumok az úgynevezett vágásmetrikára nézve. Angol nevét (graphon) a gráf (graph) és függvény (function) szavak összevonásával alkották.

A fogalmat Borgs, Chayes, Lovász, T. Sós, Szegedy és Vesztergombi vezette be és dolgozta ki [1,3]. A grafonok természetes módon bukkannak fel olyan területeken, ahol nagy gráfok sorozatai fordulnak elő: extremális gráfelmélet, nagy gráfok tulajdonságtesztelése, kvázi-véletlen gráfok, véletlen hálózatok, statisztikus fizikai rendszerek termodinamikai limeszei, és így tovább.

Kezdjük néhány definícióval és motivációként egy példával. Egy \(G\) gráf alatt csúcsoknak egy \(V(G)\) halmazát és éleknek egy \(E(G)\) halmazát értjük, utóbbinak az elemei különböző csúcsokból alkotott párok. Egy gráfhomomorfizmus \(H\)-ból \(G\)-be egy olyan \(\varphi\) leképezés \(V(H)\)-ból \(V(G)\)-be, amely megőrzi az élek menti szomszédságot. Azaz minden \(\{v,w\}\) élre \(E(H)\)-ból a \(\{\varphi(v), \varphi(w)\}\) egy él \(E(G)\)-ben. Jelöljük \(\hom(H,G)\)-vel a homomorfizmusok számát \(H\)-ból \(G\)-be. Például \(\operatorname{hom}(\,\)\(\,,G)=\vert V(G)\vert\), \(\operatorname{hom}(\,\)\(\,,G)=2\vert E(G)\vert\) és \(\operatorname{hom}(\,\)\(\,,G)\) a \(G\)-ben lévő háromszögek számának 6-szorosa.

A lehetséges leképezések számával normalizálva kapjuk a \(H\) homomorfizmus-sűrűségét \(G\)-ben, \[\displaystyle t(H,G) = \frac{\hom(H,G)}{\vert V(G)\vert^{\vert V(H)\vert}},\] ami annak a valószínűsége, hogy egy véletlenszerűen választott leképezés \(V(H)\)-ból \(V(G)\)-be megőrzi az élek menti szomszédságot. Ez a szám egyben a \(H\) mint részgráf sűrűségét is méri \(G\)-ben, aszimptotikusan, ahogy \(n=\vert V(G)\vert \to \infty\). Például \(t(\,\)\(\,,G)=2\vert E(G)\vert/n^2\), míg a \(G\)-ben lévő élek sűrűsége \(2\vert E(G)\vert/n(n-1)\). Ez a a két kifejezés nagy \(n\)-re közel azonos.

Tekintsük a következő extremális gráfelméleti problémát: Hány 4 hosszú körnek kell lennie egy olyan gráfban, amelynek élsűrűsége legalább \(1/2\)? Könnyű belátni, hogy bármely \(n\) csúcsú gráfban a 4 hosszú körök száma nagyságrendileg legfeljebb \(n^4\). Erdős egyik tétele szerint a lehetséges élek legalább felét tartalmazó gráfokban a 4 hosszú körök száma nagyságrendileg legalább \(n^4\). Pontosabban, bármely \(G\) gráfra

\(\displaystyle t(\) \(\displaystyle , G) \geq t(\) \(\displaystyle , G)^4\)

Speciálisan, ha \(t(\,\)\(\,,G) \geq 1/2\), akkor \(t(\)\(\,,G) \geq 1/16\). Ennek fényében a probléma újrafogalmazható minimalizálási problémaként: minimalizáljuk \(t(\)\(\,,G)\)-t olyan véges \(G\) gráfokon, amelyek kielégítik \(t(\,\)\(\,,G) \geq 1/2\)-et. Némi munkával megmutatható, hogy nincs olyan véges \(G\) gráf, amelyre \(t(\,\)\(\,,G) \geq 1/2\), és melyre \(t(\)\(\,,G)\) eléri az \(1/16\)-ot.

Ezen a ponton érdemes párhuzamot vonnunk egy elemi analízis problémával: minimalizáljuk \((x^3 – 6x)\)-et az \((x \geq 0)\)-t kielégítő racionális számok között. Ennek a polinomnak \([0,\infty)\)-en globális minimuma van  \(x=\sqrt{2}\)-nél, így a legjobb, amit a racionális számok körében tehetünk az, hogy megmutatjuk, hogy a polinom a minimumhoz közelítő értékeket vesz fel racionális számok egy \(\sqrt{2}\)-höz tartó sorozata mentén. Jól tudjuk, hogy ezt a bonyodalmat úgy kell elkerülni, hogy a racionális számokat (mint metrikus teret) teljessé tesszük, kiegészítjük a valós számokkal, és egy ilyen sorozat határértékét \(\sqrt{2}\)-vel realizáljuk.

Van olyan véges gráfokból álló sorozat, amelyben az élsűrűség legalább \(1/2\) és a 4 hosszú körök sűrűsége megközelíti az \(1/16\)-ot. Legyen \(R_n\) egy \(n\) csúcsú véletlen gráf, ahol minden él beválasztása függetlenül, \(1/2\) valószínűséggel dől el. Elhagyva azokat az \(R_n\)-eket amelyekben \(t(\,\)\(\,,R_n) < 1/2\), egy olyan gráfsorozatot kapunk, amiben a 4 hosszú körök sűrűsége 1 valószínűséggel konvergál \(1/16\)-hoz. Követve a \(\sqrt{2}\) analógiáját, érdemes megpróbálnunk realizálni ennek a véges gráfsorozatnak a limeszét, és megérteni, hogyan oldja meg az adott minimalizálási problémát.

Mi lehet ennek az \(R_n\) véletlen gráfsorozatnak a limesze? Egy címkézett gráf szomszédsági mátrixából konstruáljuk meg a gráf pixelképét úgy, hogy az 1-eseket fekete négyzetekké alakítjuk, a 0-ákat pedig fehérekké, és a \([0,1]^2\) egységnégyzetre skálázunk:

A pixelképeken látható, hogy grafikusan „konvergálnak”: az egyre nagyobb és nagyobb \(1/2\) élvalószínűségű véletlen gráfok (bármilyen címkézéssel) egy szürke négyzethez konvergálnak, a konstans \(1/2\) függvényhez \([0,1]^2\)-en.

A konstans 1/2 függvény a \([0,1]^2\)-en egy példa címkézett grafonra. A címkézett grafon egy szimmetrikus, Lebesgue-mérhető függvény \([0,1]^2\)-ből \([0,1]\)-be (a szokásos, nullmértékű eltérés esetén azonosítással). Az ilyen függvényekre tekinthetünk a \([0,1]\) csúcshalmazon vett élsúlyozott gráfokként. A címkézetlen grafon egy átcímkézés erejéig megadott grafon, ahol átcímkézés alatt a \([0,1]\) intervallum egy invertálható és mértéktartó transzformációjának végrehajtását értjük. Vegyük észre, hogy bármely pixelkép egy címkézett grafon, vagyis a (címkézett) gráfok egyben (címkézett) grafonok.

Ennek a konvergenciának egy másik példájaként tekintsük a növekvő egyenletes kapcsolódási gráfok \(G_n\) sorozatát, amelyet induktív módon a következőképpen definiálunk. Legyen \(G_1=\,\), és \(n \geq 2\) esetén konstruáljuk \(G_n\)-t a \(G_{n-1}\)-ből úgy, hogy hozzáadunk egy új csúcsot, majd minden egyes élt, amely még nem szerepel \(E(G_{n-1})\)-ben, egymástól függetlenül \(1/n\) valószínűséggel beveszünk. Kiderül, hogy ez a gráfsorozat 1 valószínűséggel konvergál az \(1-\max(x,y)\) grafonhoz. (Mivel a mátrixok indexelésénél a \((0,0)\) a bal felső sarok, így a grafonoknál is).

A teljes páros gráfok címkézésének két természetes módja is van, és ezek a teljes páros gráfok sorozatának különböző limeszgrafonjaira utalnak. Valójában mindkét címkézett grafonsorozatnak ugyanaz a limesze, amint az ábra is mutatja. Arra biztatjuk az olvasót, hogy térjen vissza ehhez a példához, miután a konvergenciát pontosabban definiáltuk.

A homomorfizmus-sűrűségek természetes módon kiterjednek grafonokra is. Egy véges \(G\) gráf esetén a \(t(\,\)\(\,,G)\) sűrűség kiszámítható úgy, hogy a \(G\) minden egyes csúcsának adunk \(1/n\) tömeget, és a csúcspárokon integráljuk az élek indikátorfüggvényét. Pontosan ugyanígy, egy \(W\) címkézett grafon \(t(\,\)\(\,,W)\) élsűrűsége \[\displaystyle \int_{[0,1]^2} W(x,y)\,dxdy,\] és a 4 hosszú körök \(t(\)\(\,,W)\) sűrűsége \[\displaystyle \int_{[0,1]^4} W(x_1,x_2)W(x_2,x_3)W(x_3,x_4)W(x_4,x_1)\, dx_1 dx_2 dx_3 dx_4.\]

Innen már egyszerű egy \(H\) véges gráfnak a \(W\) grafonban vett \(t(H,W)\) homomorfizmus-sűrűségére felírni a megfelelő kifejezést. A felírt formulák alapján látjuk, hogy a \(W \equiv 1/2\) konstans grafon megoldja a minimalizálási problémát: \(t(\,\)\(\,,W)= 1/2\), míg \(t(\)\(\, ,W) = 1/16\).

Azért, hogy a véges gráfok terének teljessé tételével megkapjuk a grafonok terét, és hogy a grafonok konvergenciáját precízen definiálhassuk, bevezetjük a \(W\) és \(U\) címkézett grafonok \(\delta_{\square}(W,U)\) vágástávolságát: \[\displaystyle \inf_{\varphi, \psi} \sup_{S,T} \left\vert \int_{S \times T} W\big(\varphi(x), \varphi(y) \big) – U\big(\psi(x), \psi(y)\big)\,dxdy \right\vert,\] ahol az infimumot a \(W\) és \(U\) összes \(\varphi\) és \(\psi\) átcímkézése felett vesszük, a szuprémumot pedig a \([0,1]\) összes mérhető \(S\) és \(T\) részhalmazán. A vágástávolság először a maximális eltérést méri két felcímkézett grafon integráljai között \([0,1]^2\) mérhető szorzathalmazain (innen a \(\square\) jelölés), majd minimalizálja ezt a maximális eltérést az összes lehetséges átcímkézés felett. (Két véges gráf vágástávolságát kombinatorikusan is definiálhatjuk, bárminemű analízis nélkül, de a definíció meglehetősen komplikált.)

A vágástávolságot a definícióban szereplő infimum jól definiálttá teszi a címkézetlen grafonok terén, de még nem válik metrikává. Az olyan \(W\) és \(U\) grafonokat, amelyekre \(t(H,W) = t(H,U)\) minden véges \(H\) gráfra, gyengén izomorfnak nevezzük. Kiderül, hogy \(W\) és \(U\) akkor és csak akkor gyengén izomorf, ha \(\delta_{\square}(W,U) =0\). A vágástávolság ténylegesen metrikává válik a címkézetlen grafonok \(\mathcal{G}\) terén, ha azokat gyenge izomorfizmus erejéig tekintjük. A pixelképek konvergenciájának imént bemutatott példáit tekinthetjük konvergens sorozatoknak és azok határértékeinek \(\mathcal{G}\)-ben (gyenge izomorfizmus erejéig).

Végezetül kiemelünk néhány alapvető eredményt a grafonokkal kapcsolatban. Az oldalhivatkozások Lovász könyvéből [2] származnak, amit bátran ajánlunk a további részletek után érdeklődő olvasó figyelmébe.

1. tétel. (Prop. 11.32, 185. oldal) Minden grafon véges gráfok egy sorozatának \(\delta_{\square}\)-limesze.

Egy \(W\) címkézett grafon egy véges címkézett gráffal való közelítéséhez legyen \(S\) egy \([0,1]\)-ből véletlenszerűen kiválasztott, \(n\) pontból álló halmaz, majd konstruáljunk egy olyan gráfot \(S\)-en, amelyben a \(\left\{s_{i}, s_{j}\right\}\) él \(W\left(s_{i}, s_{j}\right)\) valószínűséggel szerepel. Ez a címkézett gráf vágástávolságban nagy valószínűséggel jól közelíti \(W\)-t  (ahogy \(\vert S\vert \rightarrow \infty\)).