Přednáška Pravděpodobnostní metoda 2 (NTIN095)

Robert Šámal

Rozsah výuky: ZS 2/2 Z, Zk

Organizační poznámky

Cvičení probíhá hlavně formou individuální práce posluchačů (domácí úkoly, třeba řešit průběžně během semestru). První zadání bude po první přednášce.

Textbook

• N. Alon, J. Spencer: The Probabilistic Method, 3rd edition, J. Wiley and Sons 2008

Plánovaná témata

• Korelační nerovnosti
• Martingaly a pokročilé odhady Černovova typu
• Pseudonáhodnost
• Fázové přechody v náhodných grafech
• Diskrepance
• Testování grafových vlastností
• náhodné regulární grafy
• konstrukce objektů několikastupňovou náhodnou volbou (Rödl nibble) -- kupř. v aplikaci na Johanssonův odhad $O(D/\log D)$ na barevnost grafů s max. stupněm D a bez trojúhelníků a čtyřcyklů
• algoritmické lokální lemma

Co bylo na přednášce

1) 8.10.2013 Pstní metoda vs. efektivní algoritmus. Na případu splnitelnosti booleovských formulí ukázány dvě metody: metoda podmíněných středních hodnot a metoda komprese entropie. (Viz též blog Terryho Taa.)

2) 15.10.2013 Dva důkazy frugálního obarvení: pomocí verze lokálního lemmatu a pomocí komprese entropie.

3) 22.10.2013 Algoritmická verze lokálního lemmatu. (Viz též původní článek.)

4) 29.10.2013 Dokončení z minula. Entropie. (z knihy Alon-Spencer kap. 15.7, další info: dvě Shannonovy věty a také Asymptotic equipartition property. Poissonovo rozdělení.

5) 5.11.2013 Poissonovo paradigma: důkaz Jansonovy nerovnosti a aplikace na pravděpodobnost, že náhodný graf neobsahuje trojúhelník.

6) 12.11.2013 Ještě jedna verze Jansonovy nerovnosti. Aplikace na důkaz Bollobásovy věty o barevnosti náhodných grafů. Brunovo síto.

7) 19.11.2013 Aplikace Brunovy nerovnosti na trojúhelníky v $G(n,p)$ a (letmo) na vlastnost EPIT: každý vrchol je obsažen v trojúhelníku. Začátek Talagrandovy nerovnosti.

8) 26.11.2013 Talagrandova nerovnost -- použití na koncentraci délky nejdelší rostoucí podposloupnosti v zadané permutaci. Barvení grafu bez trojúhelníku pomocí $(1-\varepsilon) \Delta$ barev.

9) 3.12.2013 Důkaz Talagrandovy nerovnosti: "geometrická verze". Srovnání s koncentrací míry.

9) 10.12.2013 Důkaz Talagrandovy nerovnosti: dokončení "geometrická verze" a "verze pro certifikovatelné náhodné proměnné". Začátek martingalů: definice, příklady, Azumova nerovnost s částí důkazu.

10) 17.12.2013 Azumova nerovnost -- dokončení důkazu. Doobův martingal a aplikace.