Content: Probability on finite (discrete) sets is naturally based on a use of combinatorics. On the other hand probabilistic methods are often very useful in combinatorics and graph theory. Even though it might seem paradoxical at first glance, various deep existence statements in discrete mathematics (e.g. existence of a graph satisfying certain property) are actually proven by showing that, in a given set of structures, the probability that the structure has certain property is not vanishing.

This module examines interrelations between probability and combinatorics.

The module will:

1. Begin with simple random walks and use this particular example to illustrate (review) several basic notions and statements of probability theory.
2. Investigate the beautiful connection between random walks on weighted graphs with harmonic functions and electric networks.
3. Proceed to basics of the theory of Markov chains on finite set (random walks are their special case).
4. With a view on applications to percolations on trees and random graphs, discuss another example: the branching Galton-Watson process.
5. Investigate probabilistic methods in discrete mathematics, discussing random graphs, Ramsey and chromatic numbers, and other applications in graph theory, combinatorics, and number theory.

Books:

The module will not follow a particular book. Lecture notes will be available on a website. However, much of the material covered in the module (and much more) may be found in:

G. F. Lawler, L. N. Coyle: Lectures on Contemporary Probability, American Mathematical Society (2000)

H-O. Georgii: Stochastics, de Gruyter (2008)

N. Alon, J. H. Spencer: The Probabilistic Method (second edition), Wiley-Interscience (2000)

J. Matousek and J. Vondrak: The Probabilistic Method (lecture notes), can be downloaded from: http://kam.mff.cuni.cz/~matousek/lectnotes.html

R. van der Hofstad: Random Graphs and Complex Networks (lecture notes), can be downloaded from: http://www.win.tue.nl/~rhofstad/RGCN.html