Mi is...a regularitási lemma?

Az Abel-díj 2012-es átadása óta rengeteget (pontosabban: még a korábbinál is többet) hallani Szemerédi Endre regularitási lemmájáról és annak fontosságáról. Mára a regularitási lemmának megszámlálhatatlanul sok verziója létezik, fogalmazhatunk úgy is, hogy egy egész elmélet nőtt ki belőle.

1. ábra. Szemerédi Endre az Abel-díjjal

Magáról a lemmáról beszélve Szemerédi Endre mindig megjegyzi, hogy ugyan az alapokat ő tette le, feltétlenül meg kell említeni azokat a kiváló matematikusokat, akik aztán a munkáját továbbfejlesztették. Ezt alátámasztandó megemlítünk néhány kiemelkedő eredményt (a teljesség igénye nélkül): Timothy Gowers 2007-ben analóg állítást bizonyított hipergráfokra [3], Terence Tao megadta a lemma egy valószínűségelméleti és információelméleti megközelítését [8], Lovász László és Szegedy Balázs pedig a gráfelmélet és az analízis területeit összekapcsolva megteremtette a regularitási lemma különböző analitikus alakjait. [5].

Ennek a cikknek az apropóját Lovász László Abel-díja és az imént említett kapcsolat szolgáltatja. A Szemerédi's Lemma for the Analyst című cikk nem csak Szemerédi Endre szerény állítását segít alátámasztani (értsd: nagy matematikusok vitték tovább, amit ő elkezdett), hanem jól példázza azt a gyakran emlegetett tényt is, hogy Lovász László eredményei a matematika különböző, egymástól távol eső területei között építenek hidat. (A tiszteletére szervezett konferenciák és a Bolyai Társulat gondozásában megjelenő ünnepi kötetek nem véletlenül kapták a „Building Bridges” címet.)

2. ábra. A Building Bridges kötetek borítói I,II

1. Az Erdős–Turán sejtés

Mielőtt a regularitási lemmára térnénk, feltétlenül szót kell ejtenünk az Erdős-Turán sejtésről.

3. ábra. Erdős Pál és Turán Pál

Nem sok olyan fogalom van a matematikában, amiről bizton állíthatjuk, hogy mindenki találkozott vele. Ám az egyik ilyen a számtani sorozat fogalma: egész számok egy $a_1, a_2, \dots, a_k$ sorozatát $k$ hosszúságú számtani sorozatnak nevezzük, ha a szomszédos tagjainak eltérése állandó, azaz ha van olyan $d$ szám, amelyre $a_2=a_1+d, a_3=a_2+d,\dots, a_k=a_{k-1}+d$ . Így például a 13, 20, 27, 34, 41, 48 egy 6 hosszúságú számtani sorozat, amelynek első tagja $a_1=13$ , differenciája pedig $d=7$ . Ahhoz, hogy az Erdős-Turán sejtéshez egy lépéssel közelebb kerüljünk, képzeljük el a következő játékot.

Adnak nekünk egy hatalmas $N$ , és egy kicsi $k$ számot, a példa kedvéért legyen $N=200\,000$ és $k=4$ . A feladatunk az, hogy az 1, 2, 3, ..., $200\,000$ egész számok közül kiválasszuk a lehető legtöbbet úgy, hogy a kiválasztott számhalmaz ne tartalmazzon $4$ hosszúságú számtani sorozatot. Ha például a már kiválasztott számaink között szerepel a $12\,640$ , a $12\,752$ , és a $12\,864$ , akkor nem választhatjuk ki sem a $12\,528$ -at, sem a $12\,976$ -ot, mert ezek bármelyikével létrejönne egy $d=112$ differenciájú $4$ tagú számtani sorozat.

Világos, hogy a feladatunk lépésről lépésre nehezebb lesz, hiszen minél több kiválasztott számunk van, annál több lesz a fentihez hasonló megkötés. Az is világos, hogy bármilyen stratégia szerint is válogatunk, előbb-utóbb meg kell állnunk. (Annál is inkább, mert összesen $200\,000$ számunk van, tehát a játéknak legfeljebb $200\,000$ lépése lehet.) A meglepő az, hogy a valóság ettől a $200\,000$ -től nagyon távol van: bármilyen stratégiát is választunk, a számoknak csak egy kis töredékét tudjuk kiválasztani. Hogy pontosan mennyire kicsi ez a töredék, abba nem megyünk bele, de $N$ méretéhez képest elenyésző.

Egy pillanatra gondolkodjunk most el azon, hogy milyen stratégiát követnénk, ha nem csak az 1, 2, 3, ..., $N$ számok közül, hanem az összes pozitív egész számból válogathatnánk. Az az ember érzése, hogy egyre nagyobb és nagyobb számokat kéne választani, egyre nagyobb réseket hagyva köztük. Talán ha nem hagyjuk a számokat „besűrűsödni”, akkor nem üti fel a fejét számtani sorozat, és a végtelenségig játszhatunk.

Most már csak egyetlen fogalom, ez a bizonyos sűrűség választ el minket a sejtés kimondásától. Legyen $A$ a természetes számoknak egy tetszőleges részhalmaza. Az érdekel minket, hogy hogyan alakul az $A$ sűrűsége az $\{1,\dots,n\}$ alakú halmazokban, amikor $n$ -et egyre nagyobbnak és nagyobbnak választjuk. A sűrűséget egy adott $n$ -re a lehető legtermészetesebben mérjük: mekkora hányadát teszi ki az $\{1,\dots,n\}$ halmaznak az $A$ oda eső része $A\cap\{1,\dots,n\}$ , vagyis mennyi a $d_n:=\frac{\vert A\cap\{1,\dots,n\}\vert}{\vert\{1,\dots,n\}\vert}$ hányados értéke. (Az $\vert\cdot\vert$ abszolútérték jel mostantól mindig a halmazok elemszámát jelöli.) Erdős Pál és Turán Pál sejtése azt mondja, hogy ha van olyan pozitív $\alpha$ szám szám, hogy a $d_n$ sűrűségek végtelen sokszor fölé mennek $\alpha$ -nak, akkor $A$ tartalmaz $k$ hosszú számtani sorozatot minden $k$ -ra.

Maga Erdős azt mesélte a sejtésről (bővebben lásd itt), hogy eleinte nem vették észre, hogy ez egy ennyire nehéz probléma. Később aztán 1000 dollárt ajánlott a bizonyításért, amit Szemerédi 1972-ben megcsinált. Az eredmények cikké formálásában Hajnal András segédkezett, az Amerikában tartózkodó Erdős nála érdeklődött, hogy jó-e a bizonyítás. Hajnal a rá jellemző humorral azt válaszolta, hogy azt még nem tudja, de 500 dollárért már megvenné.

4. ábra. Erdős Pál és Szemerédi Endre (További érdekes fotók itt: I,II.)

A bizonyítás jó volt, az Erdős-Turán sejtést pedig ma már inkább Szemerédi tételnek nevezik. A tétel bizonyítása rettenetesen bonyolult (lásd [6]), és ennek a rettenetesen bonyolult bizonyításnak az egyik lépése az a páros gráfokra vonatkozó segédállítás, amelyből aztán a regularitási lemma később kifejlődött [7].

Mielőtt rátérnénk magára a lemmára, teszünk néhány megjegyzést az Erdős-Turán sejtéssel és a Szemerédi tétellel kapcsolatban. A mai napig nyitott a sejtés egy erősebb változata: igaz-e, hogy ha $A$ egy olyan részhalmaza a természetes számoknak, amelyre a $\sum_{a\in A}\frac{1}{a}$ sor divergens, akkor $A$ tartalmaz $k$ hosszúságú számtani sorozatot minden $k$ -ra. Mivel Leonhard Euler már 1737-ben bebizonyította, hogy a prímek reciprokösszege divergens (jelölje a továbbiakban a prímek halmazát $\mathbb{P}$ ), ezért aki ezt az erős Erdős-Turán sejtést igazolja, az automatikusan bebizonyítja a számelmélet egyik legősibb sejtését, hogy van tetszőlegesen hosszú prímszámokból álló sorozat. Egyébként ez utóbbi sejtés 2008 óta már tétel, ugyanis Ben Green és Terence Tao bebizonyította [4] (a bizonyítás egyik fő komponense persze maga a Szemerédi tétel), hogy ha $A$ egy olyan prímszámokból álló halmaz, amelyre a $d_n=\frac{\vert A\cap\{1,\dots,n\}\cap\mathbb{P}\vert}{\vert\{1,\dots,n\}\cap\mathbb{P}\vert}$ relatív sűrűség végtelen sokszor fölé megy egy $\alpha$ pozitív számnak, akkor $A$ tartalmaz $k$ hosszúságú számtani sorozatot minden $k$ -ra. Világos, hogy ha itt $A$ helyére magát $\mathbb{P}$ -t helyettesítjük, akkor $d_n=1$ minden $n$ -re, tehát a prímek halmaza valóban tartalmaz tetszőlegesen hosszú számtani sorozatot. Végül egy érdekesség az Abel-díj kapcsán: a 2020-as díjazott Hillél Fürstenberg számtalan híres eredményének egyike a Szemerédi tételre adott ergodelméleti módszereket használó bizonyítás [2].

2. A regularitási lemma

A regularitási lemma tehát egy gráfelméleti állítás, ami valójában csak nagyon nagy méretű (tehát sok csúccsal és rengeteg éllel rendelkező) gráfokról mond valamit. Mi itt egy kis csalással élve minden fogalmat és állítást kis méretű gráfokon fogunk szemléltetni.

Idézzük fel elsőként, hogy mi a gráf: adottak csúcsok, amelyek közül egyesek össze vannak kötve éllel, mások nincsenek. A csúcsok halmazát $V$ -vel, az élek halmazát $E$ -vel, magát a $V$ csúcshalmaz és $E$ élhalmaz által meghatározott gráfot pedig $G(V,E)$ -vel jelöljük.

Ha $X$ és $Y$ két részhalmaza $V$ -nek, akkor az $X$ és $Y$ között menő élek számát jelölje $e_G(X,Y)$ . (Azokat az éleket, amelyeknek mindkét vége $X\cap Y$ -ban van, kétszer számoljuk.) Számunkra különösen fontosak az úgynevezett páros gráfok: ha a $V$ csúcshalmaz felbontható két részre $U$ -ra és $W$ -re úgy, hogy élek csak a különböző csúcsosztályok között mennek, akkor $G$ -t páros gráfnak nevezzük és $G(\{U,W\},E)$ -vel jelöljük.

Egy $G(\{U,W\},E)$ páros gráfban a $d_G(U,W)=\frac{e_G(U,W)}{\vert U\vert\cdot\vert W\vert}$ hányadosra gondolhatunk úgy, mint $U$ és $V$ közötti élsűrűségre. A fenti gráfra ez a sűrűség $d_G(U,W)=\frac{8}{4\cdot 5}=0.4$ . Ha $U$ és $W$ helyett csak az $X=\{u_2,u_3,u_4\}$ és $Y=\{w_2,w_3,w_4,w_5\}$ csúcshalmazokat vesszük, és felírjuk az $\frac{e_G(X,Y)}{\vert X\vert\cdot\vert Y}\vert=\frac{5}{3\cdot4}\approx 0.416$ hányadost, akkor egy $d_G(U,W)$ -hez közeli számot kapunk.

Arra természetesen nem számíthatunk, hogy ez az $U$ és $W$ összes részhalmazára igaz: például $X'=\{u_1,u_2\}$ és $Y'=\{w_5\}$ választása esetén $\frac{e_G(X',Y')}{\vert X'\vert\cdot\vert Y'\vert}=0$ . Vannak azonban olyan gráfok, amikben ha $X$ -et és $Y$ -t elég kövérnek választjuk, akkor $\frac{e_G(X,Y)}{\vert X\vert\cdot\vert Y\vert}$ hányados közel van $\frac{e_G(U,W)}{\vert U\vert\cdot\vert W\vert}$ -hez. Ezt a tulajdonságot ragadja meg az $\mathbf{\varepsilon}$ -reguláris páros gráf fogalma.

A $G(\{U,W\},E)$ páros gráfot $\varepsilon$ -regulárisnak nevezzük (itt $\varepsilon>0$ egy rögzített pozitív szám, a megengedett hiba), ha minden olyan $X\subseteq U$ és $Y\subseteq W$ részhalmazra, amelyekre $\vert X\vert>\varepsilon\cdot\vert U\vert$ és $\vert Y\vert>\varepsilon\cdot\vert W\vert$ teljesül, a sűrűségek egymáshoz $\varepsilon$ -nál közelebb vannak, azaz

$\displaystyle \left\vert\frac{e_G(U,W)}{\vert U\vert\cdot\vert W\vert}-\frac{e_G(X,Y)}{\vert X\vert\cdot\vert Y\vert}\right\vert<\varepsilon.$

Legyen most $G(V,E)$ egy tetszőleges gráf (nem feltétlenül páros, mint eddig). Vegyük a $V$ -nek két olyan $S$ -sel és $T$ -vel jelölt részhalmazát, amelyeknek nincs közös eleme (az alábbi gráfon ezek $S=\{s_1,s_2,s_3\}$ és $T=\{t_1,t_2,t_3,t_4\}$ ). Tartsuk meg azokat és csak azokat az éleket, amelyeknek egyik végpontja $S$ -ben, a másik $T$ -ben van (az ábrán ez a zöld élhalmaz). Így $G(V,E)$ -nek egy olyan részgráfját kapjuk, ami páros. Jelölje ezt $G[S,T]$ .

Nagyon pongyolán fogalmazva a regularitási lemma azt mondja, hogy ha a gráfnak elég sok csúcsa van, akkor a csúcsokat fel tudjuk bontani kevés darab lényegében egyforma méretű $V_1,\dots,V_k$ halmazra úgy, hogy ha ezekből készítjük el a $G[V_i,V_j]$ páros gráfokat a fenti módon, akkor azok nagy része $\varepsilon$ -reguláris lesz. Tehát a gráfot fel lehet darabolni nem túl sok „szép darabra”, persze némi hibától eltekintve.

A rend kedvéért precízen is kimondjuk a lemma klasszikus alakját, továbbá egy gyenge alakját is, mert később ezek majd jól fognak jönni. Ehhez szükségünk lesz a partíció fogalmára. A $V$ csúcshalmaz egy $V_1,\dots,V_k$ átfedés nélküli halmazokra való feldarabolását partíciónak nevezzük.

Ha a partícióban szereplő darabok lényegében egyforma méretűek, azaz $\vert V_i\vert\approx\frac{n}{k}$ minden $1\leq i\leq k$ -ra (másképp: $\big\vert\vert V_i\vert-\vert V_j\vert\big\vert\leq1$ ), akkor a partíciót ekvipartíciónak nevezzük.

1. Lemma. (Regularitási lemma, hagyományos alak.) Tetszőleges $\varepsilon>0$ és számokhoz léteznek olyan $\varepsilon$ -tól és -től függő $M(\varepsilon,m)$ és $N(\varepsilon,m)$ konstansok, amelyekre az alábbi állítás teljesül. Minden legalább $N(\varepsilon,m)$ csúcsú gráf csúcshalmazának van olyan $\{V_1,\dots,V_k\}$ ekvipartíciója ( $m\leq k \leq M(\varepsilon,m)$ ), amelyben legfeljebb $\varepsilon\cdot k^2$ darab $1\leq i<j\leq k$ indexpár kivételével mindegyik páros gráf $\varepsilon$ -reguláris.

Most rátérünk a regularitási lemma egy gyenge alakjára, ami Alan Frieze-től és Ravi Kannantól származik [1]. Hasonlóan a korábbi $d_G(U,W)$ mennyiséghez, vezessük be a partícióhoz tartozó élsűrűségeket. Egy adott $\mathcal{P}=\{V_1,\dots,V_k\}$ partíció esetén jelölje $d_{ij}$ a $V_i$ és $V_j$ csúcshalmazok közti élsűrűséget:

$\displaystyle d_{ij}:=\frac{e_G(V_i,V_j)}{\vert V_i\vert\cdot\vert V_j\vert}.$

Legyen $S$ és $T$ a $V$ -nek két részhalmaza. Emlékezzünk, hogy $e_G(S,T)$ -vel jelöltük azon élek számát, amelyeknek egyik végpontja $S$ -ben, a másik $T$ -ben van. Ezt az mennyiséget megbecsülhetjük a $\mathcal{P}$ partíció és a $d_{ij}$ sűrűségek (vagy ha úgy tetszik átlagok) segítségével:

$\displaystyle e_{\mathcal{P}}(S,T):=\sum_{i=1}^k\sum_{j=1}^k d_{ij}\vert V_i\cap S\vert\cdot\vert V_j\cap T\vert.$

Mivel átlagokkal számoltunk, természetesen nem várhatjuk, hogy tetszőleges $S$ -re és $T$ -re $e_G(S,T)$ megegyezzen $e_{\mathcal{P}}(S,T)$ -vel. Az eltérés nagyságra, tehát a $\max_{S,T\subseteq V}\vert e_G(S,T)-e_{\mathcal{P}}(S,T)\vert$ számra tekinthetünk úgy, mint egy mérőszámra, ami a $\mathcal{P}$ partíció irregularitását méri. Most már minden adott, hogy kimondjuk a regularitási lemma gyenge alakját. (Ennek a gyenge alaknak a következő fejezetben komoly szerepe lesz.)

2. Lemma. (Gyenge regularitási lemma.) Tetszőleges $\varepsilon>0$ számhoz és tetszőleges gráfhoz van olyan $\mathcal{P}=\{V_1,\dots,V_k\}$ ( $k\leq 2^{2/\varepsilon^2}$ ) partíciója -nek, hogy minden $S,T\subseteq V$ -re

$\displaystyle \vert e_G(S,T)-e_{\mathcal{P}}(S,T)\vert\leq\varepsilon\vert V\vert^2.$

3. Regularitási lemma az analízisben

Már említettük Lovász László és Szegedy Balázs Szemerédi's Lemma for the Analyst című cikkét, amelyben a regularitási lemmának három különböző analízisbeli interpretációját is megadták. Különösen érdekes ez az eredmény, mert a gráfelmélet és az analízis között (vagy ha úgy tetszik a folytonos és diszkrét matematika között) hatalmas szakadékot kell tudni áthidalni. Az ilyen távoli területek összekapcsolása mindig nagyon szép, és persze roppant bonyolult. Arra nincs lehetőség, hogy a szükséges fogalmakat mind bevezessük, és a cikk eredményeit itt bemutassuk, de talán sikerül legalább a felszínt megkapargatni.

Először arról lesz szó, hogy hogyan lehet gráfokat speciális függvényekkel azonosítani. A példa kedvéért vegyük az alábbi ötcsúcsú $G(V,E)$ gráfot, és mellé egy $5\times5$ egybevágó négyzetre felbontott egységnégyzetet. Számozzuk meg a csúcsokat, és feketítsük be az $i$ -edik oszlop és $j$ -edik sor kereszteződésében lévő négyzetet, ha az $i$ és $j$ csúcsok szomszédosak. (Azon se most, se később ne akadjunk fenn, hogy a szomszédos kis négyzetek közös oldala milyen színű, ha az egyik négyzet fekete, a másik pedig fehér.)

Ezzel az eljárással egy felcímkézett gráfot megfeleltettünk egy „pixeles képnek”. A pixeles képet pedig meg tudjuk feleltetni egy $W:[0,1]\times[0,1]\to[0,1]$ függvénynek: legyen $W(x,y)=0$ , ha az $(x,y)$ pont a pixeles képen fehér, és legyen $W(x,y)=1$ , ha az $(x,y)$ pont a pixeles képen fekete színű.

Mivel a szomszédosság egy szimmetrikus reláció (ha az $u$ csúcs össze van kötve $v$ -vel, akkor $v$ is össze van kötve $u$ -val), ezért a fenti eljárással definiált függvények szimmetrikusak, azaz minden $0\leq x,y\leq1$ -re $W(x,y)=W(y,x)$ . Most áttérünk egy jóval általánosabb függvényosztályra, ami ezeket a pixeles képekből származó függvényeket mind tartalmazza.

Jelöljük $\mathcal{W}$ -vel a $W:[0,1]\times[0,1]\to\mathbb{R}$ korlátos és mérhető szimmetrikus függvények vektorterét. Egy $W$ függvény korlátossága alatt azt értjük, hogy van olyan $K$ szám, amire $-K\leq W(x,y)\leq K$ teljesül minden $(x,y)$ pontra. A mérhetőség pedig egy nagyon természetes (és szükséges) technikai feltevés, amennyiben az ember integrálni szeretne. Márpedig hamarosan látni fogjuk, hogy az integrál fogalma mindig ott lesz a háttérben. A részletekbe terjedelmi okokból nem megyünk bele, elégedjünk meg annyival, hogy ezzel a mérhetőségi feltevéssel csak olyan (vadul viselkedő) függvényeket zárunk ki, amelyek úgy képezik a $[0,1]\times[0,1]$ -et $\mathbb{R}$ -be, hogy a rajtuk lévő természetes halmazstruktúrák a függvény mentén nem passzolnak össze.

A $\mathcal{W}$ vektorteret felruházhatjuk egy speciális függvénnyel, a vágás norma nevű mennyiséggel. Minden $W$ függvényhez rendeljünk hozzá egy $\Vert W\Vert$ -val jelölt számot, az ő normáját a következő formulával

$\displaystyle \Vert W\Vert:=\sup_{S,T\subseteq[0,1]}\left\vert\int\limits_{S\times T}W(x,y)~dxdy\right\vert.$

A normára gondolhatunk úgy, mint a hosszúság fogalmának egy nagyon fontos és hasznos általánosítására. Ha rendelkezésünkre áll egy norma, akkor olyan absztrakt fogalmakat is megfoghatunk számok segítségével, mint például a „közelség”. Azt mondhatjuk, hogy $W_1$ és $W_2$ közel vannak egymáshoz, vagy kevéssel térnek el egymástól, ha a különbségüknek kicsi a hossza, azaz ha a $\Vert W_1-W_2\Vert$ szám kicsi.

Észrevehettük, hogy a gráfokhoz tartozó függvények elég speciális szerkezetűek. Valóban, ezek a függvények az úgynevezett lépcsős függvények osztályához tartoznak. Egy $W\in\mathcal{W}$ függvényt lépcsős függvénynek nevezünk legfeljebb $m$ lépcsővel, ha van a $[0,1]$ intervallumnak olyan $\mathcal{P}=\{S_1,\dots,S_m\}$ felosztása, hogy a $W$ függvény konstans az összes $S_i\times S_j$ téglán.

Azt láttuk, hogy egy $n$ csúcsú gráfot olyan szimmetrikus lépcsős függvénnyel tudtunk azonosítani, amelyben a $\mathcal{P}=\{S_1,\dots,S_m\}$ partíció tagjai az $1/m$ hosszú intervallumok az $S_i\times S_j$ négyzeteken pedig a függvényérték vagy 0 vagy 1.

Egy másik fontos függvényosztály a $\mathcal{W}$ azon elemeiből áll, amelyekre $0\leq W(x,y)\leq 1$ teljesül minden $(x,y)\in[0,1]\times[0,1]$ esetén. Ezeket a függvényeket grafonoknak nevezzük, a grafonok halmazát pedig $\mathcal{W}_0$ -lal jelöljük. A regularitási lemma gyenge alakjának (lásd 2. Lemma) analitikus változata azt mondja, hogy bármilyen $W$ grafont is veszünk, és bármilyen kicsi $\varepsilon>0$ hibát engedünk meg, találunk majd olyan $\mathcal{W}_0$ -beli lépcsős grafont, amely a $W$ -t $\varepsilon$ -nál jobban megközelíti, és nincs túl sok lépcsője.

3. Lemma. (Gyenge regularitási lemma, analitikus változat.) Minden $W\in\mathcal{W}_0$ grafonhoz és $\varepsilon>0$ -hoz létezik olyan $W'\in\mathcal{W}_0$ lépcsős függvény legfeljebb $\lceil2^{2/\varepsilon^2}\rceil$ lépcsővel, amelyre $\Vert W-W'\Vert\leq\varepsilon$ .

Végezetül megemlítjük, hogy a regularitási lemma megfogalmazható mint kompaktsági tétel. Ezt a mély állítást a többinél kicsit tömörebben, az analízisben sztendernek számító fogalmak felidézése nélkül tárgyaljuk. Tudjuk, hogy egy topologikus tér metrizálhatósága mennyire fontos és hasznos tulajdonság, különösen ha a metrizálással nyert metrikus tér kompakt. A kérdés, hogy hogyan metrizáljuk a grafonok terét, és hogy a metrizálással kapott tér kompakt-e.

Először is egy megjegyzés: az az eljárás, ahogy gráfokból függvényeket csináltunk, függött attól, hogy hogyan címkéztük fel a csúcsokat. A következő példa azt mutatja, hogy ugyanannak az ötcsúcsú (címkézetlen) gráfnak két különböző önkényes felcímkézése különböző pixeles képekhez, és így különböző függvényekhez vezet.

A csúcsok átszámozásának megfelelője a grafonok nyelvén egy $\varphi:[0,1]\to[0,1]$ invertálható mértéktartó leképzéssel való komponálás, nevezetesen $W^{\varphi}(x,y):=W(\varphi(x),\varphi(y))$ . Vezessük be az alábbi $\delta$ függvényt a vágás norma segítségével $\delta(U,V):=\inf\limits_{\varphi}\Vert U^{\varphi}-W\Vert$ .

Ez a $\delta$ már majdnem egy metrika, ráadásul úgy méri a grafonok távolságát, hogy az az „átcímkézésre” érzéketlen. Meg lehet mutatni, hogy $\delta(U,V)=\delta(V,U)$ , és hogy $\delta$ teljesíti a háromszögegyenlőtlenséget $\delta(U,V)\leq\delta(U,W)+\delta(W,V)$ . Azonban a $\delta$ definíciójából adódóan itt most azzal a problémával szembesülünk, hogy vannak olyan $U$ és $V$ grafonok, amik nem azonosak, a $\delta$ -távolságuk mégis nulla. Márpedig azt meg akarjuk követelni, hogy a metrizálandó objektumaink csak önmaguktól legyenek nulla távolságra. Mivel az $U\sim V\,\Leftrightarrow\,\delta(U,V)=0$ reláció nyilvánvalóan egy ekvivalencia reláció, ezért ezeket az egymástól nulla távolságra lévő elemeket azonosíthatjuk. Jelöljük az így kapott teret $\mathcal{X}$ -szel. Erre az $\mathcal{X}$ -re a $\delta$ -t ráhúzva már egy valódi metrikus teret kapunk.

Térjünk rá a kompaktságra: metrikus terekben a kompaktság ekvivalens a sorozatkompaktsággal, azaz azzal, hogy minden sorozatnak van konvergens részsorozata. Ha tehát adott grafonoknak egy $(W_n)_{n\in\mathbb{N}}$ sorozata, akkor konstruálni kell egy olyan $U$ grafont, és $(W_{n_k})_{k\in\mathbb{N}}$ részsorozatot, amelyre $\delta(W_{n_k},U)\to0$ . Lovász és Szegedy a gyenge regularitási lemma analitikus változatának segítségével ezt megtették, ezzel bebizonyították, hogy az $(\mathcal{X},\delta)$ metrikus tér kompakt. Ilyen értelemben a grafonok terének kompaktsága tekinthető úgy, mint a regularitási lemma egy topologikus interpretációja. További részletek, és a regularitási lemma további nagyon érdekes alakjai megtalálhatók a [5] cikkben.

5. ábra. Lovász László és Szegedy Balázs Oberwolfachban

Ahogy arra néhány példát is láthattunk, a Szemerédi regularitási lemmát és a Szemerédi tételt sokan általánosították, újrabizonyították, vagy épp más struktúrákban találtak hasonló eredményeket. Ha az ember kutakodni kezd a regularitási lemma után, azt tapasztalja hogy ahány helyre benéz, annyi variációval találkozik. Ez persze nem olyan meglepő, ugyanis a regularitási lemma sokkal több, mint egy egyszerű merev állítás, a regularitási lemma egy nagyon általános jelenség lényegét ragadja meg. Hogy mi is ez a jelenség? Szemerédi Endre Abel-előadásának címe „In every chaos there is an order” volt, Kepes András róla szóló fantasztikus portréfilmjének címe pedig „Rend a káoszban”, tehát nem lehet kapufát lőni azzal a kompakt megfogalmazással, hogy minden káoszban van valami rendszer.

Irodalomjegyzék

: [1] A. Frieze, R. Kannan, Quick Approximation to Matrices and Applications, Combinatorica 19 (1999), 175–220.

[2] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Anal. Math. 31 (1977), 204–256.

[3] T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. 166 (3), 897–946.

[4] B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. 167 (2008), 481–547.

[5] L. Lovász, B. Szegedy, Szemerédi’s Lemma for the Analyst, Geom. Funct. Anal. 17 (2007), 252–270.

[6] E. Szemerédi, On sets of integers containing no elements in arithmetic progression, Collection of articles in memory of Jurii Vladimirovic Linnik, Acta Arith. 27 (1975), 199–245.

[7] E. Szemerédi, Regular partitions of graphs, Problémes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, 1978, 399–401.

[8] T. Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), 8–28.

A cikk az ITM és az NKFIH ÚNKP-20-5-BGE-1 és PD128374 kódszámú projektjeinek, valamint az MTA Bolyai János Kutatási Ösztöndíjának támogatásával készült.

Titkos Tamás

Rényi Alfréd Matematikai Kutatóintézet