Combinatorics Seminar
When: Sunday, March 9, 10am
Where: Schreiber 309
Speaker: Sonny Ben-Shimon, Tel Aviv University,
Title: Vertex Percolation on Expander Graphs
Abstract:
In this talk we explore the process of deleting vertices of a
expander graphs independently at random, and study the properties of
the resulting graph. Our main result states that as n, the number of
vertices, tends to infinity, the deletion process performed with
probability p=n^{-a} for some a>0, on some expander graph of bounded
degree will result w.h.p in a graph composed of a giant
component containing n-o(n) vertices that is in itself an expander
graph. Moreover, w.h.p. all other components will be of constant size.
We proceed by applying the main result to some expander graph
families, strengthening a recent result due to Greenhill, Holt and
Wormald who study vertex percolation on random d-regular graphs.
Joint work with M. Krivelevich.