Pravdepodobnostni metoda TIN022
(Dalsi informace jsou tez na strance J. Matouska.
)
Zkousky. Vypisuju dva terminy 18. 1. a 29. 1. 2002.
Sraz je v 10:00 u me v pracovne na Male Strane, fyzicke 2. patro
(vstupni dvere ze schodiste jsou oznaceny jako "4. nadzemni podlazi").
Dalsi dva terminy vypisuje J. Matousek. Zapis na zkousku - kontaktuje
me prosim e-mailem.
11. 10. 2001 (prednasel J. Matousek) Zakladni princip
pravdepodobnostni metody, odhady Ramseyova cisla R(k, k) a
cisla m(k), m(k) >= 2^{k-1} (m(k) je nejmensi pocet
hran v k-grafu, ktery neni 2-obarvitelny). Odhady faktorialu a
binomickych koeficientu.
18. 10. 2001 Veticka: m(3) = 7 (horni odhad pomoci
Fanovy roviny, ktera neni 2-obarvitelna, dolni odhad indukci a pravd.
argumentem). Erdos-Ko-Radoova veta: pocet hran k-grafu na n-prvkove
mnozine, jehoz kazde dve hrany se protinaji, je nejvyse B(n-1,
k-1). Bollobasova veta: pocet n dvojic mnozin A_1,
..., A_n, B_1, ..., B_n, kde A_i maji k prvku a B_imajilprvku,A_ije
disjunktni s B_i, ale A_i protina kazdou B_j proiruzne
od j, je nejvyse B(k+l, k) = B(k+l, l). Linearita
stredni hodnoty, indikatorove nahodne veliciny. Str. hodnota poctu
pevnych bodu nahodne permutace cisel 1, 2, ..., n je 1.
25. 10. 2001 Pripomenuti, ze Burnsideovo lemma z algebry je
vlastne vzorec pro str. hodnotu poctu pevnych bodu nah. permutace z
grupy G. Tri jednoduche veticky uzivajici linearity str.
hodnoty: 1) ex. turnaj na n vrcholech s alespon n!/2^{n-1} Hamiltonovymi
cestami, 2) graf s m hranami ma vzdy (ne nutne indukovany)
bipartitni podgraf s alespon m/2 hranami a 3) n jednotkovych
vektoru v R^n se vzdy da zkombinovat s koeficienty 1 nebo-1,
ze vysledny vektor ma delku nejvyse n^{1/2} . Povidani
o Buffonove jehle, coz je taky trochu o linearite str. hodnoty, a o
Bertrandove paradoxu. Markovova nerovnost a obecne o metode modifikace
(alteration). Priste bude napoveda k uloham 1, 2, 3 a 7!
1. 11. 2001 Dve aplikace metody modifikace: 1) R(k,
k) > (k/e).2^{k/2}.(1+1/k) pro velke k a 2) Erdosova
veta z r. 1959 o existenci grafu s velkym obvodem a chromatickym cislem.
Rozptyl Var(X), smerodatna odchylka, kovariance Cov(X, Y).
Cebysevova nerovnost. Odhad prostredniho binom. koeficientu B(2m,
m) pomoci Ceb. nerovnosti.
Napoveda k uloham. 1. Pro nahodnou permutaci picisel1,
2, ..., n a pevnou permutaci fi cisel 1, 2, ..., i jePr(poc.
usek pi delky i ma tvar fi) = 1/i!. 2. Hledana
pravdepodobnost je 1/2. 3. Uvazte pravdepodobnosti
prechodu z jednoho "behu" do druheho. 7. Trivialni, na
definice pojmu. Za 14 dni bude napoveda k uloham 4 a 5.
8. 11. 2001 Lemma: Jsou-li X_1, X_2, ... nezaporne
nah. veliciny takove, ze Var(X_n)/E(X_n)^2 -> 0 s n
-> nekonecno, pak i Pr(X_n>0) -> 0. Prahova
funkce. Veta: Je-li H vyvazeny graf s hustotou r (tj.
zadny podgraf nema podil E/V vetsi nez H), je f(n)=n^{-1/r}prahovou
funkci pro vlastnost "nah. graf G_{n,p}, p=p(n), obsahuje H jako
(ne nutne indukovany) podgraf". Zacatek dukazu teto vety: Pro kazde
pevne e>0 plati, ze Pr( (2-e).log_2(n) <
klika(G_{n,1/2}) < 2.log_2(n) ) -> 1 s n -> nekonecno.
15. 11. 2001 Dokonceni dukazu te vety. Poznamky o 0-1 zakonech
podle knihy Alona a Spencera (bez dukazu): Veta 1 (Glebskii et al.
1969, Fagin 1976) --- Je-li A grafova vlastnost prvniho radu a 0<p<1je
dana pravdepodobnost, pak lim Pr[G_{n, p} ma vl. A] = 0 nebo 1.
Veta 2 (Shelah a Spencer 1988) --- Je-li A grafova
vlastnost prvniho radu, 0<a<1 je iracionalni cislo
a p = p(n) = n^{-a}, pak opet plati lim Pr[G_{n, p} ma vl.
A] = 0 nebo 1. Dalsi veta bez dukazu: Ma-li G v vrcholu,ehran
a a automorfismu a je-li ostre vyvazeny (zadny jeho vlastni
podgraf nema vetsi hustotu nez G), pak, s p = p(n) =
c.n^{-v/e} a c>0, plati lim Pr[G_{n, p} obsahuje G]
= 1-exp(-c^e/a). Formulace problemu nalezeni co nejvetsi podmnoziny
mnoziny {1, 2, ..., n} s ruznymi soucty.
22. 11. 2001 Problem ruznych souctu: maximalni velikost
podmnoziny mnoziny {1, 2, ..., n} s ruznymi soucty je <
log_2(n) + (1/2).log_2(log_2(n)) + O(1); dukaz pomoci Cebysevovy
nerovnosti. Formulace Lovaszova lokalniho lemmatu. Jeho dve aplikace:
1. kazdy k-uniformni hypergraf, jehoz kazda hrana protina
nejvyse 2^{k-1}/e - 1 jinych hran, je 2-obarvitelny a
2. kazdy or. graf c minim. vystupnim stupnem d a maximalnim
vstupnim stupnem D obsahuje or. cyklus s delkou rovnou nasobku k,
jakmile k <= d/(1 + log(1+dD)). Poznamka k popletenemu
dukazu: Vyhazenim hran lze dosahnout, ze kazdy vystupni stupen je presneda
pak jiz vse funguje bez problemu. Napoveda k uloham. 4. G je
nesouvisly, prave kdyz se V rozklada na dve mnoziny, mezi
nimiz neni hrana. 5. Uvazte pravdepodobnost, ze f neposila
nic na i.
29. 11., 6. 12., 13. 12., 20. 12. a 3. 1. prednasel J.
Matousek.
10. 1. 2002 Dukaz Weiestrassovy aproximacni vety ( pro kazde eps>0a
kazdou spojitou funkci f: [0,1] -> R existuje polynom p(x)takovy,
ze | f(x) - p(x) | < eps pro kazde cislo x z
intervalu [0, 1] ) pomoci binomicke nahodne veliciny a
Cebysevovy nerovnosti. Erdosova veta (z r. 1956): Existuje posloupnost
prir. cisel A a konstanty 0<c_1<c_2 tak,
ze pro kazde dostatecne velke n plati nerovnosti c_1.log(n)
< # vyjadreni n =x + y, x a y jsou z A <
c_2.log(n). Dukaz vyuziva pravd. prostor nekonecnych posloupnosti
(vznikne soucinovou konstrukci z vhodnych dvouprvkovych prostoru),
odhad velkych odchylek Cernovova typu a Borel-Cantelliho lemma.
Prednaska, konana spolecne s J. Matouskem, se konala ve ctvrtek od
16:00 v E5 v Troji.
unor 2002