Pravdepodobnostni metoda TIN022
(Dalsi informace jsou tez na strance
J. Matouska. )
16. 10., 23. 10., 30. 10., 6. 11. a 13. 11. 2002 prednasel J.
Matousek.
20. 11. 2002 Pouziti pravdepodobnostni metody pri enumeraci
permutaci aneb veticka P. Valtra: Je-li f(n, pi) pocet permutaci
cisel
1, 2, ..., n neobsahujicich danou permutaci pi, potom
pro kazdou konstantu c, 0 < c< 1/e^3, existuje k_0
tak,
ze pro kazde k > k_0 a kazdou permutaci pi
delky k plati,
ze lim f(n, pi)^{1/n} > c.k^2. (Nelze dostat c vetsi nez
1,
protoze lim f(n, (1, 2, .., k))^{1/n} = (k-1)^2 ). Lovaszovo lokalni
lemma v nesymetricke forme a zacatek dukazu.
27. 11. 2002 Prednaska odpadla (prednasejici na sluzebni ceste).
4. 12. 2002 , 11. 12. 2002 a 18. 12. 2002 Dukaz Lovaszova lokalniho
lemmatu. Aplikace LLL na obarvovani realnych cisel: Pro kazde k existuje
m tak, ze pro kazdou m-prvkovou mnozinu realnych cisel X
existuje obarveni R k barvami takove, ze v kazdem posunuti
X+a nalezneme vsech k barev. Dukaz pro spocetnou mnozinu
posunuti pomoci Konigova lemmatu. Cernovova nerovnost. Kombinatoricka diskrepance.
Nahodne zaokrouhlovani a priblizne randomizovane reseni problemu nejvetsiho
k-parovani v hypergrafu. Konstrukce hypergrafu s velkou diskrepanci
pomoci Hadamardovych matic.
leden 2003