Robert Šámal

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

Přednáška se koná ve středu 15:40 v S4. K přednášce jsou také cvičení (tamtéž po přednášce, cca jednou za dva týdny). Cvičení je založeno na samostatném řešení příkladů, jejich zadání můžete najít na stránce cvičícího -- Pavla Patáka (nápověda: musíte vybrat "záložku" Příklady).

Seznam probrané látky najdete na konci teto stranky.

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

Zkoušky

Z probrané látky -- teorie i její aplikace na jednodušší příklady. Zkoušku je též možné získat za hvězdnou účast na cvičení (velký počet vyřešených domácích úkolů).

Anotace

Pravděpodobnostní metoda je způsob důkazu existence kombinatorických objektů "počítáním". Pro mnoho důležitých objektů je to jediný známý důkaz. Pravděpodobnostní metoda se stále častěji objevuje i v návrhu a analýze algoritmu a v dalších odvětvích informatiky a patří k nejdůležitějším nástrojům diskrétní matematiky.
O náplní přednášky si můžete udělat lepší představu podle látky probrané minule.

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).

Učební text

Skripta J. Matoušek, J. Vondrák: The probabilistic method vyšla v ITI Sériích (preprintova řada Institutu teoretické informatiky MFF UK) pod číslem 2002-087 a je k dispozici v informatické knihovně MFF UK.
Elektronická verze v postscriptu zkomprimovaném programem "gzip" (2 malé stránky na jednu stranu A4, celkem asi 90 malých stran) zde.

Osnova

Základní pravděpodobnostní metoda, linearita střední hodnoty, metoda modifikace, použití variance. Lovászovo lokální lemma. Pseudonahodnost a explicitní konstrukce. Odhady Černovova typu. Ilustrace metod na příkladech z různých oblasti diskrétní matematiky a informatiky.

Další literatura

N. Alon, J. Spencer: The Probabilistic Method, J. Wiley and Sons 1993
J. Spencer: Ten lectures on the probabilistic method, SIAM, 1987
kapitola ze skript J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky (pokrývá jen úvodní část přednášky)

Probraná látka

3. října Jak dokazovat existenci házením kostkou. Důkaz R(k,k) > 2^k/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. (Důkaz funguje pro k ≥ 3, ale my jsme jenom shledali, že funguje pro dostatečně velká k.) Opakování základních pojmů teorie pravděpodobnosti (pravděpodobnostní prostor - hlavně konečný případ). Turnaje (orientovace úplných grafů) s vlastností S_k: každých k vrcholů má společného vstupního souseda.

10. října Zkoumání funkce m(k), což je nejmenší počet hran k-uniformního hypergrafu, který není 2-obarvitelný: m(2)=3, m(k) ≥ 2^k-1, m(3)=7 (Fanova rovina + pstní metoda + indukce). Další opakování psti -- nezávislost, a její projevy v náhodných grafech.

17. října Využití linearity střední hodnoty: Existuje turnaj s mnoha hamiltonovskými cestami. Každý graf má řez obsahující alespoň polovinu hran. Plus-mínusové součty vektorů -- mohou být malé i velké.

24. října Ukázka derandomizace: algoritmus, který najde řez, který obsahuje alespoň polovinu hran. Třikrát náhodná permutace: Spernerova věta, Erdǒs-Ko-Rado a Bollobásova.

31. října. K čemu je dobrá Bollobásova věta z minula. Markovova nerovnost. Metoda změny: nalezení nezávislé množiny velikosti n/2d (d je průměrný stupeň) -- slabá verze Turánovy věty. Dolní odhad pro Ramseyova čísla.

7. listopadu Dopočtení odhadu pro Ramseyova čísla. Existence grafu s barevnosti větší než k a obvodem větším než l. Konstrukce množiny bodů ve čtverci bez malých trojúhelníků.

14. listopadu Množina bez malých trojúhelníků -- dokončení výpočtu. Dependent Random Choice -- existence množiny vrcholů, kde každá malá podmnožina má hodně společných sousedů. (Důkaz bude dokončen.) Aplikace na vnořovánání bipartitních grafů.

21. listopadu. JS
Rozptyl, standardní odchylka, kovariance. Výpočet rozptylu pro součet náhodných veličin. Čebyševova nerovnost (s důkazem). Prahová funkce pro "obsahovat K₄" je n^-2/3.

28. listopadu
Dokončení Dependent Random Choice lemma (metodou alterace). Odhad prostředního binomického čísla (pomocí rozptylu a Čebyševovy nerovnosti). Množiny s různými součty, horní odhad pro maximální velikost takové množiny obsažené v {1,2,...,n} pomocí Čebyševovy nerovnosti.

5. prosince Klikovost náhodného grafu G_n,1/2 je cca 2 log₂(n). Souvislost s Ramseyovou větou.

12. prosince Lovászovo lokální lemma (symetrická verze a obecná). Aplikace na 2-barvení hypergrafů. Důkaz. 19. prosince Hříčka s prostými zobrazeními. Orientovaný graf s dost velkým stupněm má orientované cykly s délkou dělitelnou daným číslem. (Dokončení příště.) Barvení reálných čísel tak, aby všechna posunutí dané množiny byla obarvena všemi barvami.

2. ledna Dokončení aplikace LLL na or. cykly. Černovova nerovnost pro součet nezávislých +1/-1 proměnných, důkaz. Varianta pro n.v. 0/1. Stupeň v náhodném grafu.

9. ledna -- PLAN Další verze Čern. nerovnosti, souvislost s Centrální limitní větou. Aplikace: stupně v náhodném grafu, počet společných vrcholů pro dva vrcholy. Skoro všechny grafy jsou protipříklad na Hájosovu domněnku. "Obrácená Černovova nerovnost" a náznak její aplikace. Příp. z intervalu [0,1]). Aplikace: náhodné zaokrouhlení LP relaxace problému k-párování v hypergrafech.