A tantárgy az alábbi témakörök ismeretére épít:
Valószínűségszámítás, kombinatorika, lineáris algebra és funkcionálanalízis alapjai
A tantárgy szerepe a képzés céljának megvalósításában:
szabadon választható tárgy matematikus BSc, MSc és PhD hallgatók számára
A tantárgy részletes tematikája magyarul és angolul:
1. A véletlen módszer a kombinatorikában (Ramsey-számok becslései, érdekes tulajdonságú gráfok létezése, stb.).
2. Kombinatorikus számelmélet (Erdős-Kac tétel a prímtényezők véletlenségéről, esetleg később Roth-tétel a 3 hosszú számtani sorozatokról).
3. Erdős-Rényi gráf fázisátmenetei.
4. Perkolációelmélet alapjai.
5. Koncentráció bizonyítások: második momentum módszer, Janson-egyenlőtlenség, Lovász Lokális Lemma, Azuma-Hoeffding martingál- koncentráció, Russo-formula, diszkrét Fourier-analízis alapjai.
6. Barabási-Albert skálafüggetlen gráfok.
7. Gráfokon való bolyongás keverési sebességének becslései:
a) csatolásokkal, megállási időkkel, b) spektrális módszerekkel,
c) izoperimetrikus tulajdonságokból, a Morris-Peres evolving sets módszer segítségével, d) elektromos hálózatokkal.
8. Propp-Wilson Coupling From The Past mintavételezési módszer.
9. Expanderek, nem-amenabilitás, Banach-Tarski paradoxon.
Követelmények szorgalmi időszakban:
Két hosszabb feladatsorból választható 4-4 darab HFbeadása, a jegy 50%-a.
Követelmények vizsgaidőszakban:
Tételjegyzék alapján szóbeli vizsga, a jegy 50%-a.
Pótlási lehetőségek:
Hibás HF-megoldások javíthatóak. Vizsga ismételhető.
Konzultációs lehetőségek:
Hetenkénti fogadóóra, vizsgaidőszakban is.
Jegyzet, tankönyv, felhasználható irodalom:
N. Alon, J, Spencer: The probabilistic method, 3rd Edition. Wiley Interscience, 2008.
D. Levin, Y. Peres, E. Wilmer. Markov chains and mixing times. AMS 2008. http://pages.uoregon.edu/dlevin/MARKOV/
G. Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html
Nyomtatóbarát változat
