The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Sharp threshold for percolation on expanders

Lugosi, G (Barcelona)
Wednesday 30 March 2011, 10:00-11:00

Seminar Room 1, Newton Institute


In this joint work with I. Benjamini, S. Boucheron, and R. Rossignol, we study the appearance of the giant component in random subgraphs of a given finite graph G = (V,E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c in (0,1), the property that the random subgraph contains a giant component of size c|V | has a sharp threshold. The main technical tools are based on variance inequalities for functions of independent random variables.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧