Informace k prednasce "Pravdepodobnostni metoda" 
(Jiri Matousek, KAM), zimni semestr 2007/2008

Zkouska

V SIS jsem vypsal termin 6.2. (od 9:30), kdybyste potrebovali prijit jindy, ozvete se.

Streda 17:20 v S6

Rozsah vyuky: ZS 2/2 Z, Zk

Anotace

Pravdepodobnostni metoda je zpusob dukazu existence kombinatorickych objektu ``pocitanim''. Pro mnoho dulezitych objektu je to jediny znamy dukaz. Pravdepodobnostni metoda se stale casteji objevuje i v navrhu a analyze algoritmu a v dalsich odvetvich informatiky a patri k nejdulezitejsim nastrojum diskretni matematiky. O naplni prednasky si muzete udelat lepsi predstavu podle latky probrane v predlonske prednasce.

Organizacni poznamky

Cviceni zcasti formou individualni prace posluchacu (domaci ukoly, treba resit prubezne behem semestru). Cviceni povede Jana Maxova.

Prednaska se vzajemne doplnuje s prednaskou L. Kucery nebo J. Sgalla "Pravdepodobnostni algoritmy".

Ucebni text

Skripta J. Matousek, J. Vondrak: The probabilistic method vysla v ITI Seriich (preprintova rada Institutu teoreticke informatiky MFF UK) pod cislem 2002-087 a je k dispozici v informaticke knihovne MFF UK. Elektronicka verze v postscriptu zkomprimovanem programem "gzip" (2 male stranky na jednu stranu A4, celkem asi 90 malych stran) zde.

Osnova

Zakladni pravdepodobnostni metoda, linearita stredni hodnoty, metoda modifikace, pouziti variance. Lovaszovo lokalni lemma. Pseudonahodnost a explicitni konstrukce. Odhady Cernovova typu (a pripadne martingaly). Ilustrace metod na prikladech z ruznych oblasti diskretni matematiky a informatiky.

Dalsi literatura

Probrana latka

3. rijna 2007. Důkaz R(k,k) >= 2k/2-1, kde R(k,l) je nejmenší počet vrcholů grafu, který zaručí, že graf obsahuje nezávislou množinu velikosti k nebo úplný podgraf s l vrcholy. Opakování pojmů z teorie pravděpodobnosti: pravděpodobnostní prostor, G(n,p) (nahodny graf) jako pravdep. prostor, nezávislost jevů, nahodna promenna. Odhady pro n! a pro n nad k. Zakladni nerovnost 1+x <= exp(x), pouziti hlavne pro odhady mocnin vyrazu 1-p pro male p.

10. rijna 2007. Zkoumání funkce m(k), coz je nejmenší počet hran k-uniformniho hypergrafu, který není 2-obarvitelný: m(2)=3, m(3)=7 [Fanova rovina!], m(k) >= 2k-1. Definice nezavislych nahodnych velicin. Střední hodnota a jeji vlastnosti. Indikator jevu. Pouziti: stredni hodnota poctu pevnych bodu nahodne permutace. Existuje turnaj, který obsahuje alespoň 2n-1/n! hamiltonovských cest.

17. rijna 2007. Poznamka o problemu maximalniho rezu (MAXCUT). Veta: kazdy graf s m hranami obsahuje bipartitni podgraf s aspon m/2 hranami. Veta Erdos-Ko-Rado. Bollobasova veta o systemu dvojic mnozin, tez dukaz Spernerovy vety o nezavislem systemu mnozin. Pravdepodobnost, ze konvexni obal n nezavislych nahodnych bodu na kruznici obsahuje jeji stred (neni ve skriptech).

24. rijna 2007. Veta o "vyvazovani" vektoru: pro kazdych n jednotkovych vektoru v nejakem R^d existuji znamenka epsilon_1,...,epsilon_n takova, ze vektor epsilon_1 v_1 + epsilon_2 v_2 +...+ epsilon_n v_n ma (euklidovskou) delku nejvys odmocnina z n. [Na rozmysleni pro vsechny: muzu pro libovolny pocet vektoru, ale v rovine, vynutit vic nez odmocnina ze 2 pro vsechny volby znamenek?] Dalsi dulezity trik v pravdepodobnostni metode: metoda modifikace (= vylepseni nahodneho objektu). "Slaba Turanova veta": Libovolny graf s n vrcholy a m hranami ma nezavislou mnozinu s aspon n/2d vrcholy, kde d=2m/n je prumerny stupen. Veta: Pro kazde k a r existuje graf barevnosti aspon k, v nemz ma kazda kruznice delku vetsi nez r.

31. rijna 2007. Markovova nerovnost. Cebysevova nerovnost. Vypocet rozptylu pro soucet nahodnych velicin. Dolni odhad 2m nad m. Definice prahove funkce pro monotonni vlastnost grafu. Prahova funkce pro "obsahovat trojuhelnik" (prvni cast).

7. listopadu 2007. Prahova funkce pro "obsahovat trojuhelnik" (dokonceni). Vyvazene grafy, prahova funkce pro obsahovani daneho vyvazeneho grafu. Proc je vyvazenost skutecne potreba - priklad K_4 s ocaskem. Horni odhad na maximalni velikost mnoziny s ruznymi soucty pomoci Cebysevovy nerovnosti.

14. listopadu 2007. Lovászovo lokální lemma: symetrická i obecná verze (obecna verze bez dukazu, symetricka odvozena z obecne). Aplikace na barvení hypergrafů. Poznamka o algoritmickych verzich LLL (zhruba postup algoritmu pro problem barveni hypergrafu). Aplikace LLL: existence cyklu delky delitelne k v orientovanych grafech.

21. listopadu 2007. Aplikace LLL: legracni prosta zobrazeni. Strucny uvod do euklidovske Ramseyovy teorie. Barveni R (konecna cast) pomoci LLL. Topologicke prostory, kompaktnost, vyuziti pri dukazu existence vhodneho barveni R. Koncentrace kolem stredni hodnoty: uvod.

28. listopadu 2007. Zakladni verze Cernovovy nerovnosti s dukazem. Definice kombinatoricke diskrepance. Veta o hornim odhadu diskrepance. Hadamardova matice. Dolni odhad diskrepance pro n mnozin na n bodech. Poznamka o centralni limitni vete.

12. prosince 2007. Obecnejsi verze Cernovovy nerovnosti bez dukazu. Algoritmicky problem k-pakovani, formulace jako celociselny program, relaxace na linearni program, pravdepodobnostni zaokrouhleni ziskaneho necelociselneho reseni.

19. prosince 2007. Funkce na soucinovem pravdepodobnostnim prostoru, vliv i-te souradnice. Veta o koncentraci takove funkce (v zavislosti na vlivech souradnic) - bez dukazu. Pouziti: koncentrace velikosti obrazu nahodneho zobrazeni, Shamirova-Spencerova veta o koncentraci barevnosti G(n,p), veta o 4-hodnotove koncentraci barevnosti. Talagrandova nerovnost (specialni tvar s "certifikaty"), jeji pouziti na delku nejdelsi rostouci podposloupnosti v nahodne posloupnosti n cisel z intervalu [0,1].

9.ledna 2008 (Jana Maxova). Velke nezavisle mnoziny v grafech bez trojuhelniku. Prusecikove cislo grafu, dolni odhad na zaklade poctu hran, aplikace na pocet incidenci bodu a primek. Nahodne prochazky ve vrcholove tranzitivnim grafu (pravdepodobnost navratu je aspon tak velka, jako pravdepodobnost prichodu kamkoliv jinam).