Robert Šámal

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

Úterý od 10:40 na chodbě KAM ve 3. patře.

K přednášce jsou také cvičení (o něco dříve tamtéž, ale ne každý týden).
Zadani prvni serie prikladu uz je k maní.

Seznam probrane latky najdete na konci teto stranky.

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

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é v loňské přednášce.

Organizační poznámky

Cvičení 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 (a případně martingaly). 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ýva jen úvodní část přednášky)

Probraná látka

6. ří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.)
Užitečné odhady pro n! a binomická čísla. Zakladni nerovnost 1+x <= exp(x), Další občas užitečné vzorečky (většinu zatím nebudete potřebovat, pozor na překlepy).
Zopakovali jsme si základních pojmy teorie pravděpodobnosti (pravděpodobnostní prostor - hlavně konečný případ -, nezávislé jevy atd.). Kdo se s těmito pojmy setkal poprvé, přečtěte si prosím (pro jistotu :-) příslušné 4 stránky ve skriptech.
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. Kolik je m(3)? (Bude příště!)

13. října. m(3)=7 (Fanova rovina + pstní metoda + indukce) Střední hodnota a její linearita. Indikátor jevů I_A = [A] (pravdivostní hodnota A) E[I_A]=P[A]. Použití: střední hodnota počtu pevných bodů náhodně permutace, Existuje turnaj, který obsahuje alespoň n!/2^n-1 hamiltonovských cest. Každý graf G=(V,E) obsahuje bipartitní podgraf s aspoň |E|/2 hranami.

20. října. Ještě k max. bipartitnímu podgrafu (MAXCUT): 1) "derandomizace", 2) vylepšení o odmocninu z počtu vrcholů. Balancování vektorů pomocí linearity střední hodnoty. Důkazy pomocí náhodného uspořádání. 1) Věta (Erdös-Ko-Rado): Systém k-tic na n-prvkové množině, v němž se každé dvě k-tice protínají, má nejvýš n-1 nad k-1 k-tic (pro n aspoň 2k).

2) (náznak) Spernerova věta,

3) Bollobásova věta

27. října. Markovova nerovnost (znění a důkaz).

Metoda modifikace: vylepšení odhadu na R(k,k). Obojí dohromady: existence grafu s barevnosti větší než k a obvodem větším než l.

3. listopadu. Slabá verze Turanovy věty; existuje množina n bodů ve čtverci, kde nejmenší trojúhelník má plochu 1/(100n²). Rozptyl. Čebyševova nerovnost (s důkazem). Definice prahové funkce pro monotónní vlastnost grafu. Prahová funkce pro "obsahovat K₄ je n^-2/3. (Jedna část pomocí Markovovy nerovnosti, druhá bude příště, pomocí Čebyševovy.)

10. listopadu. Výpočet rozptylu pro součet náhodných veličin, kovariance. Množiny s různými součty, horní odhad pro maximální velikost takové množiny obsažené v {1,2,...,n}. Náhodné grafy s pravděpodobností o hodně větší než n^-2/3 s.j. obsahují K₄.

24. listopadu. Lovászovo lokální lemma. Důkaz symetrické i obecné verze. Příklad s prostými zobrazeními.

1. prosince. Aplikace Lovászova lokálního lemmatu. Splnitelnost formulí, důkaz, že každá Ek-CNF s omezeným počtem výskytů proměnných je splnitelná. Latinské transverzály, důkaz, že v každé matici s omezeným počtem výskytů proměnných existují. Barvení reálných čísel tak, aby všechna posunutí dané množiny byly obarvené všemi barvami.

8. prosince. Černovovy odhady pro součet nezávislých proměnných. Důkaz speciálního případu pro hody korunou a pro 0-1 náhodné proměnné, naznačení důkazu pro proměnné z (0,1).

15. prosince. Aplikace Černovových odhadů. Směrování v hyperkrychlích. Důkaz Černovových odhadů pro výběr z distribuce bez opakování.

5. ledna. Aplikace Černovových odhadů pro samplování. Martingaly, definice, Doobovy martingaly, grafové martingaly. Azumova nerovnost.

12. ledna. FKG nerovnost. Monotónní vlastnosti a jejich korelace. Aplikace na grafové vlastnosti. Věta o rozšiřování částečných uspořádání.