Tantárgy azonosító adatok
1. A tárgy címe Valószínűségszámítás gráfokon és csoportokon
2. A tárgy angol címe Probability on Graphs and Groups
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 2 + 0 + 0 v Kredit 3
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Sztochasztika Tanszék
7. A tantárgy felelős oktatója Dr. Pete Gábor beosztása egyetemi docens
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2022.01.31. Akkreditációs bizottság döntési időpontja 2022.02.01.
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
Valószínűségszámítás és sztochasztikus folyamatok alapjai (pld CHT, elágazó folyamatok, martingál-konvergencia és megállási idők). Gráfelméleti és lineáris algebra alapok (pld. sajátérték, sajátvektor).
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
Matematika- és Számítástudományok Doktori Iskola, ill. Matematikus és Alkalmazott matematikus MSc képzés szabadon választható tárgya
11. A tárgy részletes tematikája
Egy tér nagyléptékű geometriai tulajdonságai és a téren vett sztohasztikus folyamatok (pld. bolyongás, perkoláció, Ising modell, véletlen fesztítőfák) viselkedése között gazdag kapcsolat van. Diszkrét metrikus terekre két kézenfekvő forrás a hálózatelmélet véletlen gráfjai, illetve végesen generált csoportok Cayley-gráfjai; különösen, hogy a második esetben a nagyléptékű geometriai (és így valószínűségszámítási) tulajdonságok az algebrai tulajdonságokat is visszatükrözik. A kurzuson vizsgált témák függhetnek a diákok háttértudásától és érdeklődésétől, a lehetőségek következő listája alapján:
  • Reverzibilis Markov-láncok és elektromos hálózatok. Rekurrencia és tranziencia.
  • Bolyongás és perkoláció általános fákon: elágazás-szám és kapacitás. 
  • Keverési idők és hőmag-lecsengés izoperimetrikus egyenlőtlenségeken keresztül: a fejlődő halmazok módszere.
  • Expander-gráfok konstruálása, véletlenszerűen és Kazhdan-csoportokból.
  • Térfogatnövekedés és izoperimetria csoportokban. Amenabilitás. Példák: Heisenberg-csoport, lámpagyújtogató csoportok.
  • Gromov tétele a polinomiális térfogatnövekedés és a majdnem-nilpotensség ekvivalenciájáról.
  • Harmonikus függvények, Poisson-határ, entrópia.
  • Fázisátmenetek Bernoulli-perkolációban. 
  • Fázisátmenetek az Ising-modellben és más Gibbs-mértékekben. Farok-trivialitás, iid faktor folyamatok.
  • Szabad és huzalozott egyenletes feszítőerdők.
  • A diszkrét Gauss-féle szabad mező.
  • Ritka gráfsorozatok Benjamini-Schramm-limesze. Lokalitás kérdések: spektrum és független halmazok. Lokális-globális limesz.
 
There is a rich interplay between large-scale geometric properties of a space and the behaviour of stochastic processes (like random walks, percolation, Ising model, random spanning forests) on the space. Two obvious sources of discrete metric spaces are random graphs from network theory, and the Cayley graphs of finitely generated groups, especially that in the latter case their large-scale geometric (and hence, probabilistic) properties reflect the algebraic properties. The exact topics included in the course may depend on the background and interests of the students, but here is a list of possibilities:
  • Reversible Markov chains and electric networks. Recurrence and transience.
  • Random walks and percolation on general trees: branching number and capacity. 
  • Mixing times and heat kernel decay via isoperimetric inequalities: the method of evolving sets.
  • Constructing expander graphs, randomly and from Kazhdan groups.
  • Volume growth and isoperimetry in groups. Amenability. Examples: Heisenberg group, lamplighter groups.
  • Gromov's theorem on the equivalence between polynomial volume growth and being almost nilpotent.
  • Harmonic functions, Poisson boundary, entropy.
  • Phase transitions in Bernoulli percolation. 
  • Phase transitions in the Ising model and other Gibbs measures. Tail-triviality, factor of iid processes.
  • Free and Wired Uniform Spanning Forests.
  • The discrete Gaussian Free Field.
  • Benjamini-Schramm limit of sparse graph sequences. Locality questions: spectrum and independent sets. Local-global limits.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban
2 házifeladatsor beadása (50%) vizsga-
időszakban
Szóbeli vizsga: egy választott téma részletes ismertetése (50%)
13. Pótlási lehetőségek
A TVSZ-nek megfelelően
14. Konzultációs lehetőségek
Megbeszélés szerint
15. Jegyzet, tankönyv, felhasználható irodalom
Gábor Pete. Probability and geometry on groups. Book in preparation. http://www.math.bme.hu/~gabor/PGG.pdf
Russ Lyons and Yuval Peres. Probability on trees and networks. Cambridge University Press, 2016. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html
Geoffrey Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html.
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
28
16.2 Félévközi felkészülés órákra
14
16.3 Felkészülés zárthelyire
0
16.4 Zárthelyik megírása
0
16.5 Házi feladat elkészítése
20
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
16
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
12
16.9 Összesen
90
17. Ellenőrző adat Kredit * 30
90
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Pete Gábor
egyetemi docens
BME TTK Sztochasztika Tanszék és Rényi Alfréd Matematikai Kutatóintézet
A tanszékvezető
19. Neve aláírása
Dr. Simon Károly