Random Structures and the probabilistic method

Material on line:Some material from the sessions.

Title: Random Structures and the probabilistic method
Summary: 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.
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.
Lecturers:
  • Gábor Lugosi, ICREA Research Professor, Universitat Pompeu Fabra
  • Elitza Maneva, “Ramón y Cajal” researcher at the University of Barcelona;
  • Oriol Serra, Professor at the Universitat Politècnica de Catalunya.
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.
Dates and place: Facultat de Matemàtiques i Estadística, UPC, Room 005, Tue-Thu 17h-19h starting September 26 2013
This entry was posted in BGSMath Courses 2013/2014. Bookmark the permalink.

One Response to Random Structures and the probabilistic method

  1. Pingback: Aquest setembre comencen els primers cursos de la Barcelona Graduate School of Mathematics | Blog de la Biblioteca de Matemàtiques

Comments are closed.