Member Seminar

Speaker: Michael Simkin

Title: Threshold phenomena in random graphs and hypergraphs

Abstract: In 1959 Paul Erdos and Alfred Renyi introduced a model of random graphs that is the cornerstone of modern probabilistic combinatorics. Now known as the “Erdos-Renyi” model of random graphs it has far-reaching applications in combinatorics, computer science, and other fields.

The model is defined as follows: Given a natural number $n$ and a parameter $p \in [0,1]$, let $G(n;p)$ be the distribution on graphs with $n$ vertices in which each of the $\binom{n}{2}$ possible edges is present with probability $p$, independent of all others. Despite their apparent simplicity, the study of Erdos-Renyi random graphs has revealed many deep and non-trivial phenomena.

A central feature is the appearance of threshold phenomena: For all monotone properties (e.g., connectivity and Hamiltonicity) there is a critical probability $p_c$ such that if $p >> p_c$ then $G(n;p)$ possesses the property with high probability (i.e., with probability tending to 1 as $n \to \infty$) whereas if $p << p_c$ then with high probability $G(n;p)$ does not possess the property. In this talk we will focus on basic properties such as connectivity and containing a perfect matching. We will see an intriguing connection between these global properties and the local property of having no isolated vertices. We will then generalize the Erdos-Renyi model to higher dimensions where many open problems remain.