Eseménynaptár

Részletek

A Lovász Lokál Lemma algoritmikus változatai

Bizonyos kombinatorikus struktúrák létezését gyakran úgy egyszerű bizonyítani (sokszor máshogy nem is tudjuk), hogy megmutatjuk, hogy egy véletlen struktúra pozitív valószínűséggel rendelkezik a kívánt tulajdonsággal. Ezt a "véletlen módszert" Erdős Pál fejlesztette ki az 1940-es években és ez főleg akkor volt használható, ha a kívánt tulajdonság nem pusztán pozitív, hanem 1-hez közeli valószínűséggel (azaz szinte mindig) teljesül. Ilyen esetben persze könnyű találni is ilyen struktúrát: egy véletlenül választott struktúra jó eséllyel megfelel.

A Lovász Lokál Lemma egy 1975-ös Erdős-Lovász cikkben jelent meg. Sok olyan esetben is biztosítja, hogy egy véletlen struktúra pozitív eséllyel teljesíti az elvárt tulajdonságokat, amikor ez az esély exponenciálisan kicsi. Ezzel jelentősen megnőtt a véletlen módszer alkalmazhatóságának köre. Amikor a kívánt tulajdonság bekövetkezésének valószínűsége kicsi, akkor nem jó módszer véletlen struktúrákat addig vizsgálni, amíg megfelelőre nem akadunk, hiszen ilyenkor "tűt keresünk szénakazalban", nagyon sokáig kéne próbálkozni, míg véletlenül ráakadnánk egyre. Beck József 1991-es eredményével kezdve többen próbálkoztak minél több esetben hatékony algoritmust adni a Lovász Lokál Lemma szerint létező struktúrák megtalálására. 2010-ben Robin Moserrel sikerült ezt (legalábbis az LLL egyik formájában) teljes általánosságban megtennünk. A megtalált algoritmus meglepően egyszerű és flexibilis, ennek következtében azóta sokan sok irányban általánosították, és még olyan struktúrák megtalálásában is eredményre vezetett, amelyek létezése nem is következik az eredeti lemmából.

Az előadásban a Lovász Lokál Lemma legegyszerűbb formáját ismertetem egy példán keresztül és bemutatom a Robin Moserrel kidolgozott egyszerű algoritmust a lemma szerint létező struktúra megtalálására, valamint megemlítem annak néhány általánosítását.

Az esemény meghívója itt található.