Lovász lokális lemmájáról

Lovász László igen gazdag matematikai munkásságának egyik gyöngyszeme a lokális lemma. Jelentőségét felhasználásainak rendkívül nagy száma adja. Magát a lemmát sokan sok irányban általánosították és nagyon sok kombinatorikai (és néhány azon kívüli) probléma megoldásában játszott kulcsszerepet. Mindezen felül azért is választottam a friss Abel-díjas Lovász gyönyörű eredményei közül pont ezt a jelen cikk témájául, mert bizonyítása egyszerű és csak elemi módszereket használ, így a lemma legegyszerűbb formájának teljes bizonyítását megmutathatom.

Előbb azonban néhány szó a háttérről. Kombinatorikában gyakori jelenség, hogy valamilyen struktúra létezését úgy tudjuk bizonyítani, hogy azt látjuk be, hogy egy véletlen struktúra nagy eséllyel megfelelő lesz, miközben egyetlen konkrét ilyen struktúrát sem tudunk explicit módon megadni. Erre dolgozta ki Erdős Pál az úgynevezett véletlen módszert. Claude Shannon is használt hasonló technikát információelméletben. Módszerük nagyon széles körben bizonyult hatékonynak. Például ezzel látták be olyan nagy kromatikus számú gráfok létezését, amelyeknek a legrövidebb köre is hosszú, szintén így látták be kis fokú ún. expandergráfok létezését, valamint nagy Ramsey-gráfokét, amikre még visszatérünk.

Lássunk egy példát. Tegyük fel, hogy adott egy $n$ elemű $H$ alaphalmaz $k$ elemű részhalmazainak egy $\mathcal{S}$ rendszere. Egy ilyen rendszert $k$ -uniform hipergráfnak is hívnak, $\mathcal{S}$ elemei a hiperélek. Ki szeretnénk színezni $H$ elemeit két színnel úgy, hogy egyetlen hiperél se legyen egyszínű. Ezt a problémát hívják hipergráf kétszínezési problémának. Ahelyett, hogy egy algoritmust adnánk erre, tekintünk egy véletlen színezést (azaz minden elemet a többitől függetlenül egyenlő eséllyel színezünk a két szín egyikére vagy másikára). Vizsgáljuk meg annak a valószínűségét, hogy lesz egy egyszínű hiperél. Egy fix $S\in\mathcal{S}$ hiperélet $2^k$ féleképpen színezhetünk, ezek esélye egyenlő, de csak kettő esetben lesz $S$ egyszínű, így ennek valószínűsége $2/2^k=1/2^{k-1}$ . Annak a valószínűsége, hogy valamelyik hiperél egyszínű, legfeljebb $\vert{\mathcal{S}}\vert/2^{k-1}$ . Ez nem pontos érték, mert bizonyos színezéseknél több hiperél is egyszínű lesz (így ezeket a színezéseket „többször számoljuk”), de felső becslésnek megfelelő. Ha $\vert{\mathcal{S}}\vert<2^{k-1}$ , akkor az előbbi valószínűség 1 alatt van, tehát létezik megfelelő kétszínezés.

Lássuk ennek az egyszerű eredménynek egy alkalmazását is. Egy gráfban csúcsok egy halmaza klikket alkot, ha közöttük minden él be van húzva, míg függetlennek nevezzük csúcsok egy halmazát, ha egyetlen él sincs köztük. Ramsey híres tétele alapján minden $n$ csúcsú gráfban vagy van egy körülbelül $\log n/2$ elemű klikk, vagy egy ekkora független halmaz. (A cikkben $\log$ mindig a kettes alapú logaritmust jelöli.) De vajon éles-e ez az eredmény? Nem ismert konstrukció olyan $n$ csúcsú gráfra, amiben minden klikk és független halmaz mérete polinomiális lenne $\log n$ -ben. Ennek ellenére tudjuk, hogy a Ramsey-tételben szereplő $\log n/2$ körüli korlát majdnem éles, mert majdnem minden $n$ -csúcsú gráfra igaz, hogy nincs benne sem $2\log n$ csúcsú klikk, sem ekkora független halmaz. Ennek belátásához elég észrevennünk, hogy egy $n$ csúcsú gráfot tekinthetünk a csúcspárok kétszínezésének: ha van él a két csúcs között, az jelenti az egyik színt, ha nincs él, az a másikat. Ebben a megfogalmazásban egy $U$ csúcshalmaz klikk vagy független halmaz, ha az $U$ -beli párok alkotta $\vert U\vert\choose2$ méretű halmaz egyszínű. Annak eldöntése tehát, hogy van-e $n$ csúcsú gráf $m$ méretű klikk vagy független halmaz nélkül, épp egy hipergráf kétszínezési probléma. Ez egy $m\choose2$ -uniform hipergráf, amiben $n\choose m$ hiperél van, ezek az $m$ méretű csúcshalmazoknak felelnek meg. A fent bizonyított eredmény szerint tehát van $n$ csúcsú gráf, amiben nincs $m$ elemű klikk vagy független halmaz, ha ${n\choose m}<2^{{m\choose2}-1}$ . Egyszerű számítás mutatja, hogy $m=\lceil2\log n\rceil$ választás mellett ( $n>2$ esetén) teljesül a feltétel, tehát a Ramsey tételében szereplő korlát nagyságrendileg éles. (Sőt, azt sem nehéz megmutatni, hogy ahogy $n$ nő, az ilyen, úgynevezett Ramsey-gráfok aránya az összes $n$ csúcsú gráf között 1-hez tart.) Ezt az alsó becslést Erdős Pál látta be 1947-ben, [1], de az alsó és felső becslés közötti négyes faktort azóta sem sikerült lejjebb szorítani.

Lovász lokális lemmája Erdős és Lovász egy 1975-ös cikkében jelent meg, [2]. Ők is a hipergráf kétszínezési problémát vizsgálták. Azt bizonyították, hogy egy $k$ -uniform hipergráf kétszínezhető, ha $k\ge2$ és tetszőleges $S$ hiperélet maximum $2^{k-3}$ másik hiperél metsz. A fenti egyszerű gondolatmenet akkor adta a kétszínezhetőséget, ha a hiperélek teljes száma kevesebb, mint $2^{k-1}$ , tehát egy globális korlátot adott a hipergráf méretére. Az Erdős-Lovász eredmény numerikus korlátja icipicit gyengébb, de az egy lokális korlát. A teljes hipergráf mérete tetszőleges (akár végtlelen is) lehet, csak az a lényeg, hogy egyetlen hiperél hány másikat metsz. Ez lehetővé tette a véletlen módszer alkalmazását a korábbinál sokkal több esetben. Míg korábban a véletlen módszert főleg olyankor lehetett alkalmazni, ha egy véletlenül választott struktúra (gráf, színezés, stb.) nagy eséllyel teljesítette a kivánalmakat, az új módszer, amely a Lovász-féle lokális lemma alkalmazásán alapul, sok olyan esetben is működik, amikor „tűt keresünk a szénakazalban”, azaz annak a valószínűsége, hogy egy véletlen struktúra megfelel, akár exponenciálisan kicsi is lehet. Ilyen a hipergráf kétszínezés is: ahogy a hipergráf mérete nő, a véletlen színezés egyre nagyobb valószínűséggel teszi egyszínűvé valamelyik élet.

A fenti hipergráf kétszínezési eredmény egyszerűen következik a lokális lemma alábbi, egyik legegyszerűbb formájából. A továbbiakban $e$ a természetes alapú logaritmus alapja, $e=2.71\dots$

Lovász lokális lemma (szimmetrikus változat). Legyen $\mathcal{A}$ események egy véges családja egy valószínűségi térben, ezeket hívjuk rossz eseményeknek. Tegyük fel továbbá, hogy adott egy gráf (a függőségi gráf), amelynek csúcsai a rossz események, és teljesül, hogy tetszőleges rossz esemény független a vele nem szomszédos rossz események halmazától. Legyen a gráf maximális foka. Ha egyetlen rossz esemény valószínűsége sem több, mint , akkor pozitív annak a valószínűsége, hogy egyik rossz esemény sem következik be.

A lemmában egyetlen bonyolult fogalom szerepel, ez a függetlenség. Az $A$ és a $B$ eseményt függetlennek mondjuk, ha $P\left[A\wedge B\right]=P[A]P[B]$ . Itt $A\wedge B$ az $A$ és $B$ események metszetét jelöli, tehát azt, hogy mindkettő bekövetkezik. Például két diszjunkt halmaz egyszínűsége egy uniform véletlen színezésben független. A lemmában azonban nem páronkénti függetlenség szerepel, hanem ennél valamivel több. Azt mondjuk, hogy az $A$ esemény független események egy $\mathcal{B}$ halmazától, ha $A$ minden olyan $C$ eseménytől független, ami a $\mathcal{B}$ -beli események kombinációjaként leírható, tehát ahol $C$ megadható azzal, hogy kikötjük néhány $\mathcal{B}$ -beli eseményről, hogy teljesüljön, míg más $\mathcal{B}$ -beliekről, hogy ne teljesüljenek. (Nem nehéz belátni, hogy ekvivalens definíciót kapunk, ha csak az egyik típusú kikötést engedjük meg. A lemma bizonyításában is csak azt fogjuk használni, hogy a megfelelő $A$ esemény független az olyan $C$ eseményektől, amik bizonyos $\mathcal{B}$ -beliek nem-teljesülésével adhatók meg.)

Nézzük meg hogyan következik a fent említett eredmény $k$ -uniform hipergráfok kétszínezéséről a lokális lemmából. Az alaphalmaz uniform véletlen kétszínezését vizsgáljuk. A rossz események a hiperélekhez tartoznak: azt tekintjük rossznak, ha a hiperél egyszínű. Mindegyik rossz esemény valószínűsége $p=1/2^{k-1}$ . A $G$ függetlenségi gráfban két rossz eseményt összekötünk, ha a hozzájuk tartozó hiperélek metszik egymást. A lemma függetlenségi feltétele teljesül, hiszen ha az $A$ rossz esemény egy $S$ hiperél egyszínűsége, akkor $A$ csak az $S$ -ben szereplő pontok színétől függ, míg az $A$ -val nem szomszédos rossz események (és így azok kombinációi is) csak az $S$ -en kívüli elemek színétől függenek, így függetlenek $A$ -tól. Ha most a $G$ gráf $d$ maximális fokszámára $d\le2^{k-3}$ , és $k\ge5$ , akkor teljesül $p\le1/((d+1)e)$ , tehát a lemma szerint pozitív eséllyel az összes rossz esemény elkerülhető, ami épp a hipergráf kétszínezhetőségét jelenti. (A $2\le k\le4$ eset nagyon egyszerűen adódik direkt meggondolásból, de a lokális lemma egy másik formáját is használhatjuk.) Ez a gondolatmenet csak véges hipergráfokra alkalmazható, a végtelen eset ebből kompaktsági meggondolásokkal következik.

Sokkal egyszerűbb lenne a lokális lemma kimondása, ha csak páronkénti függetlenséget használnánk benne. A függőségi gráfot ekkor egyszerűen úgy definiálhatnánk, hogy két rossz esemény között akkor van él, ha nem függetlenek. Sajnos a lokális lemma így kapott erősebb változata nem igaz. Ezt könnyen láthatjuk pont a hipergráf kétszínezési feladatból. Két hiperél egyszínűsége nem csak akkor független, ha hiperélek diszjunktak, hanem akkor is, ha egyetlen elemben metszik egymást. Így ha a hipergráfunk egyszerű, azaz bármely két hiperél legfeljebb egy pontban metszi egymást, akkor a függőségi gráf üres lenne, maximális fokszáma pedig $d=0$ . Ismert azonban, hogy tetszőleges $k$ -ra létezik nem kétszínezhető $k$ -uniform egyszerű hipergráf. Egy ilyen 3-uniform hipergráfot adnak például a Fano-sík egyenesei, és már ez is mutatja, hogy a lokális lemmának ez az erősebb verziója nem lehet igaz.

A lokális lemmának azonban sok más erősebb formája ismert. Shearer, [3] pontosan meghatározta, hogy adott $G$ függőségi gráf és a rossz események adott valószínűsége mellett mikor következtethetünk arra, hogy az összes rossz eseményt pozitív valószínűséggel elkerüljük. Itt most csak egy ennél kevésbé általános, de egyszerűbb verziót idézünk, ami azonban még így is jóval általánosabb a fenti szimmetrikus változatnál. Vegyük észre, hogy ez a változat mindig alkalmazható, amikor a szimmetrikus változat, de néha olyankor is, amikor az nem.

Lovász lokális lemma (egy aszimmetrikus változat) Legyen $\mathcal{A}$ „rossz” események egy véges családja, legyen egy gráf ezeken az eseményeken, mint csúcsokon, és tegyük fel, hogy minden rossz esemény független a vele nem szomszédos rossz események halmazától. Ha minden $A\in\mathcal{A}$ rossz eseményre teljesül, hogy $P[A]+\sum_{B\sim A}P[B]<1/e$ , ahol szomszédaira összegzünk, akkor pozitív annak a valószínűsége, hogy egyik rossz esemény sem következik be.

A lokális lemma bizonyítása

A cikket a lokális lemma szimmetrikus változatának bizonyításával zárom. Néha átütő erejű eredményeknek is nagyon egyszerű a bizonyítása, csak éppen megtalálni nehéz ezt az (utólag) egyszerű bizonyítást. Ez is egy ilyen eset. A bizonyítás megtalálásának körülményeiről is mesél Lovász egy nemrégi Telex-interjúban.

Bevezetünk néhány egyszerű jelölést: $\overline A$ az $A$ esemény komplementerét jelöli, azaz $\overline A$ akkor teljesül, ha $A$ nem. Két esemény metszetéhez hasonlóan, a $\wedge$ jelet használjuk akárhány esemény metszetére: $\bigwedge_{i=1}^mA_i$ tehát akkor teljesül, ha valamennyi $A_i$ teljesül. Előfordul, hogy nulla esemény metszetéről fogunk beszélni, ez a teljes esemény, ami mindig teljesül. A bizonyítás kulcsfogalma a feltételes valószínűség. Ha $A$ és $B$ események, $P[B]>0$ , akkor valószínűsége, feltéve definíciója: $P\left[A\vert B\right]=P\left[A\wedge B\right]/P[B]$ . Használni fogjuk a feltételes valószínűség néhány egyszerű tulajdonságát, mint $P\left[\overline A\vert B\right]=1-P\left[A\vert B\right]$ , vagy a láncszabály: $P\left[A\wedge B\vert C\right]=P\left[B\vert C\right]P\left[A\vert B\wedge C\right]$ . Ezek egyszerűen levezethetőek a definíció behelyettesítésével.

A kulcs a következő lemma igazolása. Észrevehetjük, hogy a lokális lemmában szereplő $1/((d+1)e)$ korlát helyett a valamivel nagyobb $d^d/(d+1)^{d+1}$ korlát is elegendő lenne a bizonyításhoz.

Lemma A szimmetrikus lokális lemma feltételei mellett minden és tőle különböző $B_1,\dots,B_m$ rossz eseményre teljesül, hogy $P\left[A\vert\bigwedge_{i=1}^m\overline B_i\right]<1/(d+1)$ .

Bizonyítás. Az állítást $m$ -re vonatkozó indukcióval bizonyítjuk. Az $m=0$ alapeset egyszerűen kezelhető, de tekinthető az általános induktív lépés speciális esetének is. Tegyük tehát fel, hogy az állítás teljesül $m$ kisebb értékeire, és igazoljuk a lemmában szereplő egyenlőtlenséget. Feltehetjük, hogy a $B_i$ események között előbb szerepelnek azok, amelyek a függőségi gráfban $A$ szomszédai, mint azok, amelyek nem. Tehát $B_1,\dots,B_k$ szomszédja $A$ -nak, $B_{k+1},\dots,B_m$ nem. A láncszabály ismételt alkalmazásával ezt kapjuk:

$\displaystyle P\left[A\wedge\bigwedge_{i=1}^k\overline B_i\,\Big\vert\bigwedge_... ...{i=1}^kP\left[\overline B_i\,\Big\vert\bigwedge_{j=i+1}^m\overline B_j\right].$

A képlet jobb oldalán megjelenik a becsülendő mennyiség, a képletben megjelenő többi feltételes valószínűséget meg egyenként megbecsüljük. Az induktív feltevésünk miatt teljesül, hogy

$\displaystyle P\left[\overline B_i\,\Big\vert\bigwedge_{j=i+1}^m\overline B_j\r... ...\Big\vert\bigwedge_{j=i+1}^m\overline B_j\right]\ge1-\frac1{d+1}=\frac d{d+1},$

hiszen a feltétel itt már $m$ -nél kevesebb $\overline B_j$ metszete. Tudjuk, hogy $A$ független a $B_{k+1},\dots,B_m$ eseményektől, valamint hogy $P\left[A\vert C\right]=P[A]$ teljesül, ha $A$ és $C$ független, így:

$\displaystyle P\left[A\wedge\bigwedge_{i=1}^k\overline B_i\,\Big\vert\bigwedge_... ...B_j\right]\le P\left[A\,\Big\vert\bigwedge_{j=k+1}^n\overline B_j\right]=P[A].$

A fenti három képletet összerakva:

$\displaystyle P\left[A\,\Big\vert\bigwedge_{j=1}^m\overline B_j\right]=\frac{P\... ...e B_i\vert\bigwedge_{j=i+1}^m\overline B_j\right]}\le\frac{P[A]}{(d/(d+1))^k}.$

Ezzel lényegében meg is vagyunk, hiszen $k$ legfeljebb $A$ fokszáma a függőségi gráfban, tehát legfeljebb $d$ , $P[A]$ pedig becsülhető $1/((d+1)e)$ -vel. Végezetül felhasználjuk a közismert $(1+1/d)^d<e$ egyenlőtlenséget, és ezzel a lemma bizonyítást nyert:

$\displaystyle P\left[A\,\Big\vert\bigwedge_{j=1}^m\overline B_j\right]\le\frac{... ...+1)e)}{(d/(d+1))^d}=\frac1{d+1}\cdot\frac{(1+1/d)^d}e<\frac1{d+1}.\quad\square$

A fenti lemmából gyorsan levezethető a lokális lemma állítása. Legyen $A_1,\ldots,A_n$ az összes rossz esemény felsorolása. Megint a láncszabályt alkalmazzuk ismételten:

$\displaystyle P\left[\bigwedge_{i=1}^n\overline A_i\right]=\prod_{i=1}^nP\left[... ...bigwedge_{j=i+1}^n\overline A_j\right]\right)>\left(\frac d{d+1}\right)^n\ge0.$

Köszönet

Hálás vagyok Simonyi Gábornak a cikk megírásában nyújtott segítségért.

Irodalomjegyzék

: [1] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc.53 (4) (1947), 292–294.

[2] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets II (A. Hajnal, R. Rado, V. T. Sós, eds.) North-Holland (1975), pp. 609–627.

[3] J. B. Shearer, On a problem of Spencer, Combinatorica 5 (3) (1985), 241–245.

Tardos Gábor

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