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 $\hom({\begin{picture}(1,1)\put(0.5,0.5){\circle*{1mm}} \end{picture}},G)=\vert V(G)\vert$ , $\hom({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},G)=2\vert E(G)\vert$ és $\hom({\begin{picture}(2,2)(0,0.5)\put(0.25,0.45){$\triangle$}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}}\put(1,1.5){\circle*{1mm}} \end{picture}},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({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},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 ? 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({\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.... ...\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}}, G)^4.$

Speciálisan, ha $t({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},G) \geq 1/2$ , akkor $t({\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\line(0... ...0.5,1.5){\circle*{1mm}}\put(1.5,1.5){\circle*{1mm}} \end{picture}},G) \geq 1/16$ . Ennek fényében a probléma újrafogalmazható minimalizálási problémaként: minimalizáljuk $t( {\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\line(... ...mm}}\put(0.5,1.5){\circle*{1mm}}\put(1.5,1.5){\circle*{1mm}} \end{picture}} ,G)$ -t olyan véges $G$ gráfokon, amelyek kielégítik $t({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},G) \geq 1/2$ -et. Némi munkával megmutatható, hogy nincs olyan véges $G$ gráf, amelyre $t({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},G) \geq 1/2$ , és melyre $t( {\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\line(... ...mm}}\put(0.5,1.5){\circle*{1mm}}\put(1.5,1.5){\circle*{1mm}} \end{picture}} ,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({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}} ,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:

$\displaystyle \begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}... ...h} \put(4.5,4.5){\vrule height1.5\unitlength width1.5\unitlength} \end{picture}$

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 -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={\begin{picture}(1,1)\put(0.5,0.5){\circle*{1mm}} \end{picture}}$ , é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({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}} ,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({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},W)$ élsűrűsége

$\displaystyle \int_{[0,1]^2} W(x,y)\,dxdy,$

és a 4 hosszú körök $t({\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\line(0... ...1mm}}\put(0.5,1.5){\circle*{1mm}}\put(1.5,1.5){\circle*{1mm}} \end{picture}},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({\begin{picture}(2,1)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\circle*{1mm}}\put(1.5,0.5){\circle*{1mm}} \end{picture}},W)= 1/2$ , míg $t({\begin{picture}(2,0)(0,0.5)\put(0.5,0.5){\line(1,0){1}}\put(0.5,0.5){\line(0... ...t(0.5,1.5){\circle*{1mm}}\put(1.5,1.5){\circle*{1mm}} \end{picture}} ,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$ ).

2. tétel. (Thm. 9.23, 149. o.) A $(G, \delta_{\square})$ tér kompakt.

Ebből következik, hogy $\left(G, \delta_{\square}\right)$ egy teljes metrikus tér. Ezt a tényt az 1. tétellel kombinálva azt látjuk, hogy a grafonok tere a véges gráfok terének a teljessé tétele a vágásmetrikára! Ez a tétel azt is mutatja, hogy a grafonok hogyan képeznek hidat Szemerédi regularitási lemmájának különböző alakjai között: a 2. tétel levezethető a lemma egy gyenge formájából, míg egy erősebb regularitási lemma a $\mathcal{G}$ kompaktságából következik.

3. tétel. (Lem. 10.23, 167. o.) Minden véges gráfra a $t(H, \cdot)\colon \mathcal{G} \rightarrow [0,1]$ Lipschitz-folytonos.

A 2. és 3. tételek és némi elemi analízis segítségével megmutatható, hogy az extremális gráfelmélet minimalizálási problémái (mint a fentiekben tárgyalt példa) garantáltan megoldhatók a grafonok terében. Ezek a grafonmegoldások az 1. tételen keresztül „sablont” adnak közelítő megoldások konstruálásához a véges gráfok terében.

Daniel Glasscock

Fordította: Tóth László Márton, Rényi Alfréd Matematikai Intézet

Irodalom

: [1] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801-1851. MR 2455626 (2009m:05161)

[2] L. Lovász, Large Networks and Graph Limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035

[3] L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933-957. MR 2274085 (2007m:05132)

Daniel Glasscock az Ohio Állami Egyetem doktorandusz hallgatója volt 2015-ben, amikor a cikk megjelent az AMS-ben. Most Assitant Professor a University of Massachusetts Lowell-en. A fordítást a szerző engedélyével közöljük. (A szerk.)

Információk

Főmenü

Mi is... a grafon?

Irodalom