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

Streda od 10:40 v S4

Cviceni budou po prednasce (od 12:20 v S6) zhruba kazdy druhy tyden.

Zkouseni:

J. Matousek zkousi v terminech 17/I (utery), 19/I(ctvrtek), 26/I (ctvrtek), 7/II (utery), 14/II (utery), vzdy priblizne od 14:10 v pracovne. Chcete-li na takovy termin prijit, prosim poslete mu e-mail aspon 24 hodin predem! R. Samal zkousi dle terminu v SISu - tj. 23/I, 6/II a 13/II (vse pondeli) ve 14 u me v pracovne. Pokud se vam zadny z terminu nehodi, ozvete se.

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

1.přednáška 5.10.2005 Úvodní příklad: důkaz R(k,k) >= 2k/2. 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, nezávislost jevů, subaditivita pravděpodobnosti P(A1 U ... U An) <= P(A1) + ... + P(An).

2.přednáška 12.10.2005 Doporučená literatura. Užitečné odhady faktoriálů a kombinačních čísel. Zkoumání funkce m(k), což jest nejmenší počet hran k-grafu, který není řádně 2-obarvitelný: m(2)=3, m(3)=7, m(k) > 2k-1. Definice náhodné veličiny, střední hodnoty a jejich vlastnosti. Aplikace: existuje turnaj, který obsahuje alespoň 2n-1/n! hamiltonovských cest.

3.přednáška 19.10.2005 Aplikace střední hodnoty: střední hodnota počtu pevných bodů náhodné permutace, každý graf obsahuje bip. podgraf s alespoň polovinou hran (plus zmínka o "derandomizaci"---jak to udělat nenáhodně), balancování vektorů (sčítání plus/minus násobků daných vektorů, aby součet byl co nejmenší/největsí). Erdös-Ko-Radonova věta.

4.přednáška 26.10.2005 Další dvě aplikace volby náhodné permutace: Bollobásova věta a Spernerova věta. Metoda alterace (nápravy) a její aplikace: vylepšení odhadu Ramseyových čísel, slabá forma Turánovy věty a množina bodů bez malých trojúhelníků.

5.prednaska 1.11.2005 [JM] Erdosuv dukaz existence vysoce barevnych grafu bez kratkych cyklu. Rozptyl, kovariance, Cebysevova nerovnost. Dolni odhad prostredniho binomickeho koeficientu.

6.prednaska 8.11.2005 [RS] Dodělávka z 4. přednášky: pravděpodobnost, že tři náhodně zvolené body tvoří trojúhelník s malým obsahem. Množiny s různými součty: odhady na jejich velikost využitím Čebyševovy nerovnosti a také `metody popotahování' (bootstrapping).

7.prednaska 15.11.2005 Aplikace Čebyševovy nerovnosti: prahová funkce pro vlastnost obsahovat trojúhelník.

8.prednaska 22.11.2005 Aplikace Čebyševovy nerovnosti: prahová funkce pro vlastnost obsahovat daný vyvážený graf. Začátek zkoumání "klikovosti" náhodného grafu a návnada na Lovászovo lokální lemma.

9.prednaska 29.11.2005 "Klikovost" náhodného grafu s n vrcholy je skoro jistě menší než 2 log2n a větší než (2-epsilon)log2n (důkaz pomocí Čebyševovy nerovnosti a dlouhého výpočtu). Lovászovo lokální lemma: symetrická i obecná verze, pozorování o nezávislosti na množině jevů, aplikace na barvení hypergrafů.

10.prednaska 7.12.2005 [JM] Priklad: pravdepodobnost, ze konvexni obal n nahodnych bodu na jednotkove kruznici bude obsahovat stred kruznice. Aplikace LLL: existence cyklu delky delitelne k v orientovanych grafech; legracni prosta zobrazeni; barveni R (konecna cast). Strucny uvod do euklidovske Ramseyovy teorie.

11.prednaska 14.12.2005 [JM] Definice topologickeho prostoru, kompaktnost (pouze orientacne), vyuziti pri dukazu existence vhodneho barveni R. Silna koncentrace kolem stredni hodnoty: uvod; Cernovova nerovnost - zakladni verze s dukazem.

12. a 13. prednaska 21.12.2005 [JM] Pojem diskrepance mnozinoveho systemu. Horni odhad diskrepance m mnozin na n bodech pomoci Cernovovy nerovnosti. Obecnejsi verze Cernovovy nerovnosti; intuice pomoci centralni limitni vety. Technika pravdepodobnostniho zaokrouhlovani na prikladu maximalniho k-pakovani. Dolni odhad (Cernovova nerovnost je temer optimalni) - bez dukazu. Dolni odhad pro diskrepanci m mnozin na n bodech. Jiny dolni odhad diskrepance pres Hadamardovy matice.

14. prednaska 11.1.2006 [JM] Pojem soucinoveho pravdepodobnostniho prostoru, funkce f na nem, vliv i-te promenne na ni, veta o koncentraci funkci. Priklady: pocet zivych zajicu, barevnost nahodneho grafu (tam se "prirozeny" soucinovy prostor musi chytre "uzavorkovat"). Veta o ctyrhodnotove koncentraci barevnosti pro dostatecne male p.