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