Probability on graphs 1000-1M24PGR
The focus of this course will be probability on discrete objects such as graphs, finite groups, permutations. This is currently a very active field of research, closely related to combinatorics, group theory, statistical physics and theoretical computer science. We will learn selected probabilistic and geometric techniques for analyzing random walks, Markov chains, spectral properties of graphs and phase transitions.
Among other things we will cover:
- basics of random graphs theory (the Erdos-Renyi model, random d-regular graphs, phase transitions in random graphs)
- Markov chain mixing times (card shuffling, coupling, spectral methods, the cutoff phenomenon)
- random permutations (the interchange process and its cycle structure, Poisson-Dirichlet distribution)
and, if time permits, also:
- spectral graph theory (Cheeger's inequality, expanders, Ramanujan graphs)
- Benjamini-Schramm graph limits, basics of spectral theory of infinite graphs
Depending on students' interests we may cover additional topics (for example, percolation on finite graphs, applications of non-backtracking random walks, connections to geometric group theory, the probabilistic method in combinatorics)
The course will be aimed at ambitious students, or more precisely - at students willing to put some effort in learning a piece of mathematics well, for example by regularly solving homework problems. In return I offer a lot of fun in learning new mathematics.
Main fields of studies for MISMaP
Type of course
Mode
Prerequisites (description)
Course coordinators
Learning outcomes
Satisfaction from learning new mathematics.
Feeling of well-spent time.
Knowledge of problems and methods appearing in probability on discrete structures.
Assessment criteria
Weekly homework assignments + short talk at the end of semester on a chosen topic.
Bibliography
R. Lyons, Y. Peres "Probability on Trees and Networks"
G. Pete "Probability on Graphs and Groups"
L. Saloff-Coste "Random Walks on Finite Groups"
S. Janson, T. Łuczak, A. Ruciński "Random Graphs"
D. Levin, Y. Peres "Markov Chains and Mixing Times"
F. Chung "Spectral Graph Theory"
Additional information
Information on level of this course, year of study and semester when the course unit is delivered, types and amount of class hours - can be found in course structure diagrams of apropriate study programmes. This course is related to the following study programmes:
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: