The Lovasz Local Lemma is one of the most useful tools in probabilistic
combinatorics.
It can guarantee the existence of a certain random structure even in
cases when it has
exponentially small probability. This increases the possibility to use
the random method
significantly. Moser and Tardos have given the first efficient algorithm
for the lemma.
The course will show different versions of the lemma and their efficient
proofs.
The same in Hungarian:
A Lovász Lokál Lemma az egyik leghasznosabb eszköz a véletlen módszer
használói számára. 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. Moser és Tardos
tudott először hatékony algoritmust adni ilyen struktúrák megtalálására.
A kurzusban a lemma különböző változatait
és ezek hatékony bizonyításait ismerhetjük meg.
When: 2020 February 3-7, each day from 13.30-15.00.
Where: ELTE Déli Tömb 3-219
Credits: ELTE students can take the course in Neptun to receive credits.