Jiří Sgall a Robert Šámal

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

Přednáška se koná ve čtvrtek od 8:10 v S7. K přednášce jsou také cvičení (tamtéž, do 10:40).

Seznam probrane latky 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. Vyzkoušet vás může kterýkoli z přednášejících, napište email s časovými návrhy.

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í 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 (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

7. října. RŠ 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.)
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, m(3)=7 (Fanova rovina + pstní metoda + indukce)

14. října. JS Důkazy pomocí náhodného uspořádání.
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).
Bollobásova věta o dvojicích množin, Spernerova věta jako důsledek. Souvislost s minimálními transverzálami v hypergrafech.
Rozdán text obsahující užitečné odhady.

21. října. JS Užitečné odhady pro n! a binomická čísla. Zakladni nerovnost 1+x <= exp(x), 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. Dva příklady z geometrie o balancování vektorů pomocí střední hodnoty normy na druhou.

4. listopadu. JS 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.

11. listopadu. JS Slabá verze Turanovy věty.
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^-1.

18. listopadu. JS Definice prahové funkce pro monotónní vlastnost grafu. Prahová funkce pro "obsahovat podgraf H".

25. listopadu. JS Konstrukce systému po dvou nezávislých binárních proměnných pomocí Sylvestrovy matice; optimalita konstrukce pomocí Č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.
Existuje množina n bodů v jednotkovém čtverci, kde nejmenší trojúhelník má plochu 1/(100n²) metodou modifikace.

2. prosince. RŠ Lovászovo lokální lemma. Důkaz symetrické verze. Aplikace na 2-barvení hypergrafů. Hříčka s prostými zobrazeními.

9. prosince. RŠ Důkaz obecné verze lok. lemmatu. Seznamové obarvení pokud všechny seznamy mají velikost l a každá barva se vyskytuje maximálně l/8-krát v každém okolí vrcholu. Vážená verze lok. lemmatu. Aplikace: hvězdicové obarvení grafu s omezeným stupněm. Barvení reálných čísel tak, aby všechna posunutí dané množiny byla obarvena všemi barvami.

16. prosince. RŠ Pozn. o algoritmické verzi LLL. Orientované cykly jejichž délka je násobek k. "Lopsided" (jednostranná) verze LLL. Aplikace: drobné vylepšení v barvení hypergrafů. Černovovy odhady pro součet nezávislých proměnných.

6. ledna. RŠ Důkaz speciálního případu Černovovy nerovnosti (všechny sčítané náhodné veličiny jsou +1 nebo -1 s pstí 1/2). Různá znění (n.v. 0/1, příp. z intervalu [0,1]). Aplikace: náhodné zaokrouhlení LP relaxace problému k-párování v hypergrafech.

13. ledna. RŠ Další verze Čern. nerovnosti. Aplikace: stupně v náhodném grafu, počet společných vrcholů pro dva vrcholy. Skoro všechny grafu jsou protipříklad na Hájosovu domněnku. "Obrácená Černovova nerovnost" a náznak její aplikace.