[an error occurred while processing this directive]

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

Pondeli od 9:00 v S8, zaciname 6. rijna.

Cviceni bylo umluveno na ctvrtek od 8:10 v S11. Cviceni zacnou az po nekolika tydnech (az bude uzavrena prvni serie prikladu!).
Zadani prvni serie prikladu uz je k mani na webu Roberta Samala.

Seznam probrane latky najdete na konci teto stranky.

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 lonske prednasce.

Organizacni poznamky

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

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

6. rijna. Argument o dobrych a spatnych objektech. 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. 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. Kdo nema jistotu v zakladnich pojmech teorie pravdepodobnosti (pravdepodobnostni prostor - staci konecny pripad -, nezavisle jevy atd., prectete si prosim prislusne 4 stranky ve skriptech.

13. rijna. 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. Střední hodnota a jeji linearita. Indikator jevu I_A, E[I_A]=P[A]. Pouziti: stredni hodnota poctu pevnych bodu nahodne permutace, stredni hodnota poctu levych maxim. Existuje turnaj, který obsahuje alespoň n!/2n-1 hamiltonovských cest. Kazdy graf G=(V,E) obsahuje bipartitni podgraf s aspon |E|/2 hranami. Veta (Erdos-Ko-Rado): System k-tic na n-prvkove mnozine, v nemz se kazde dve k-tice protinaji, ma nejvys n-1 nad k-1 k-tic (pro n aspon 2k).

20. rijna. Balancování vektorů pomocí linearity střední hodnoty a poznámka o "derandomizaci pomocí kosinové věty". Dva důkazy pomocí náhodného uspořádání (Bollobásova věta a Spernerova věta). Markovova nerovnost (znění a důkaz).

27. rijna. Horni odhad funkce m(k) pomoci nahodneho systemu k-tic. Metoda modifikace: slaba verze Turanovy vety; existence grafu s barevnosti vetsi nez k a obvodem vetsim nez l.

3. listopadu. Rozptyl. Cebysevova nerovnost. Vypocet rozptylu pro soucet nahodnych velicin, kovariance. Dolni odhad 2m nad m. Mnoziny s ruznymi soucty, horni odhad pro maximalni velikost takove mnoziny obsazene v {1,2,...,n}. Definice prahove funkce pro monotonni vlastnost grafu.

10. listopadu. Prahova funkce pro "obsahovat trojuhelnik". Vyvazene grafy, prahova funkce pro obsahovani daneho vyvazeneho grafu. Proc je vyvazenost skutecne potreba - priklad K4 s ocaskem. Graf zavislosti. Lovászovo lokální lemma: symetrická verze.

24. listopadu. Obecna verze LLL (jen zneni), jak se z ni odvodi symetricka verze. 2-obarvitelnost k-uniformnich hypergrafu, kde kazda hrana protina nejvys d jinych hran. Poznamka: LLL je nekonstruktivni, ale existuji tez algoritmicke verze. Veta o existenci orientovaneho cyklu delky delitelne k v orientovanych grafech. Strucny uvod do euklidovske Ramseyovy teorie.

1. prosince. Použití LLL na nalezení speciálního obarvení reálných čísel: takového, že každý posun jisté množiny S obsahuje všechny barvy. LLL funguje pokud barvíme jenom konečně mnoho reálných čísel, pak je ještě třeba použít princip kompaktnosti. Za dva týdny si řekneme dukaz základní verze LLL, zkuste o něm trochu podumat, abyste ho lépe vychutnali.

8. prosince. Černovova nerovnost -- důkaz, použití.

15. prosince. Další užití Černovovy nerovnosti (randomizované zaokrouhlování pro hledání hypergrafového párovaní). Její "obrácená verze".

5. ledna. Úvod do martingalů. Martingal odhalování vrcholů, hran. Azumova nerovnost (bez dk).

12. ledna. Martingaly lépe: zobrazení A do B coby pravděpodobnostní prostor. Využití: barevnost náh. grafu je koncentrována v pásu velikosti řádově odmocnina z n. Počet bodů, které mine náhodné zobrazení je koncentrováno. "Izoperimetrická nerovnost" pro podmnožiny {0,1}^n. [an error occurred while processing this directive]