Random Structures and the probabilistic method

Gábor Lugosi, ICREA (UPF), Elitza Maneva, (UB) and Oriol Serra (UPC).
Tue-Thu 17h-19h from September 26 2013
Room 005, Facultat de Matemàtiques i Estadística, UPC

Probabilistic methods have a wide range of applications in several areas of mathematics, including analysis, geometry, combinatorics, computer science, number theory or graph theory. The course provides an introduction to these methods, whose common theme is the use of the language of probability and the analysis of random structures and processes to derive results about deterministic structures. Some applications will be discussed to illustrate some standard techniques within this approach. Perhaps one of the simplest models of random structures is the Erdös-Rényi model of random graphs. Within this simple model some appealing general features of random structures can be analyzed thoroughly, like threshold phenomena, concentration of measure or 0-1 laws. Some additional models, like geometric random graphs or preferenctial attachment models will be also discussed. A final part of the course discusses Markov chains and their application to counting and sampling problems. One of the main targets of the analysis of Markov chain processes is their speed of convergence.The course will be mostly of interest to PhD students in combinatorics, computer science, graph theory, probability and statistics, and it can be also appealing to students in analysis, number theory and other fiedls. Only some basic background in probability at graduate level is required.

  • Probabilistic method: First and second moment methods. Lovàsz Local lema. Applications in combinatorics, number theory and graph theory.
  • Random graphs: The Erdös-Rényi model and the emergence of the giant component. Concentration of some graph parameters. Geometric random graphs. Preferential attachment model.
  • Finite Markov chains: Random walks, stationary distribution, mixing time. Metropolis and Glauber chains. Coupling. Counting and sampling problems in statistical physics and computer science.
  •  Noga Alon; Joel H. Spencer. The probabilistic method}. Wiley, New York, 2008.
  • Béla Bollobás. Random Graphs. Cambridge University Press, 2001.
  • Olle Häggström. Finite Markov chains and algorithmic applications. Cambridge Univ. Press, 2002.
  • Some  material on line.