Return to Colloquia & Seminar listing
Connectivity of random subgraphs of "nice" graphsMathematical 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)