Probability on graphs

<p>Written and oral exam.</p>

The course is recommended starting from the fourth year of the corso ordinario, to which it is well suited due to the very limited technical prerequisites. However, it is also suitable for PhD students, given that the content is closely related to current research topics.

The prerequisites consist of the course "Elementi di Probabilità e Statistica" and the course "Probabilità"; some more advanced knowledge of stochastic processes (discrete- and continuous-time Markov chains, Gaussian vectors, Brownian motion) from the courses "Processi Stocastici" or "Istituzioni di Probabilità" may be useful but is not essential, as is some extremely basic knowledge of harmonic functions on R^n.

The course will explore various aspects of the behaviour of random processes on graphs, with an emphasis on the interplay between probabilistic and combinatorial techniques in producing surprising results rich in applications.

The main topics include:

• Random walks on graphs and their long-term behaviour; electrical network analogy, Pólya's theorem, the type problem;
• A dialogue between discrete and continuous: Donsker's theorem, Green's functions, harmonic measure, and Brownian motion;
• The discrete Gaussian free field;
• Uniform spanning trees and forests: Wilson’s algorithm, the matrix-tree theorem, and local limits;
• Percolation and related topics;
• Mixing times of Markov chains.

1. Grimmett G. Probability on Graphs: Random Processes on Graphs and Lattices. 2nd ed. Cambridge University Press; 2018.
2. Lyons R, Peres Y. Probability on Trees and Networks. Cambridge University Press; 2017.