Random Structures and the probabilistic method

Random Structures and the probabilistic method

Date

Tue-Thu 17h-19h from 29 September to 19 December 2013

Registration

Location

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.

Date

Tue-Thu 17h-19h from September 26 2013

Registration

Location

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.

Lecturers

Gábor Lugosi, ICREA (UPF)

Elitza Maneva, (UB)

Oriol Serra (UPC).

Contents
  • 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.

utions in terms of stacks, with a view towards higher category theory and homotopy theory.

(Although the examples in Block A are chosen more on the exotic side (for pedagogical effect), the concepts they illustrate are general, and examples abound also in the five general mathematics subjects areas mentioned, and elsewhere in the mathematical sciences).

Bibliography
  • 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.
Share This