Threshold phenomena and random graphs

May 27 2013 - 00:00
May 31 2013 - 23:59

Paris, Institut Henri Poincaré (I.H.P.), May 27-31, 2013

Short description of the event: 

This Spring School will consist in two courses given by professors Chatterjee and Kahn on threshold phenomena and random graphs.

Sourav Chatterjee
(Courant Institute, New York University, USA) Applications of graph limits in probability and statistics. The theory of limits of dense graph sequences is a branch of modern graph theory, developed in a series of papers in the last seven years by Laszlo Lovasz and coauthors. This course will introduce the basic components of this theory, and demonstrate its applications to solve previously intractable questions in probability and statistics. The probabilistic application will involve a general large deviation principle for random graphs and its many surprising consequences. The statistical application will center around a certain class of models called “exponential random graph models” (ERGM's) that are becoming increasingly important in the analysis of social networks.
Jeff Kahn
(Rutgers University, USA) Thresholds. Thresholds for increasing properties are a central concern in probabilistic combinatorics and elsewhere. (An increasing property, say F, is a superset- closed family of subsets of some (here finite) set X, and the threshold question for such an F asks, roughly, about how many random elements of X should one choose to make it likely that the resulting set lies in F? For example: about how many random edges from the complete graph Kn are typically required to produce a Hamiltonian cycle?) These lectures will primarily focus on recent progress (and lack thereof) on threshold and related questions.

The school is part of the the A.N.R. project GeMeCoD.

Participation of postdocs and PhD students is strongly encouraged (we may provide some financial support).