Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Connectivity of random subgraphs of "nice" graphs

Mathematical Physics & Probability

Speaker: Benny Sudakov, Princeton University
Location: 693 Kerr
Start time: Tue, Apr 1 2003, 3:10PM

One of the most interesting phenomenon in the theory of random structures is the sharp threshold behavior" of random graphs properties. In this talk we will illustrate recent new methods for proving sharp thresholds on one particular example: network reliability. Consider the following popular model for network reliability problem. Given a graph $G$ with $n$ vertices and a real $p$ between 0 and 1, where $p$ may depend on $G$, a random subgraph $G_p$ of $G$ is obtained by keeping each edge og $G$ with probability $p$, randomly and independently. Denote the probability that $G_p$ is connected by $f(G,p)$. We would like to address the following question: For which families of graphs, the probability $f(G,p)$ exibits very sharp increase from 0 to 1 at a certain critical value of $p$ ? Strengthening a classical result of Margulis we obtain such a characterization of graph $G$. In particular we show that any "nice" graph $G$ has such property. Our result is in some sense asymptotically tight. (This is joint work with M.Krivelevich and V.Vu)