Expansion in supercritical random subgraphs of expanders and its consequences.

In 2004, Frieze, Krivelevich and Martin established the emergence of a giant component in random subgraphs of pseudo‐random graphs. We study several typical properties of the giant component, most notably its expansion characteristics. We establish an asymptotic vertex expansion of connected sets in the giant by a factor of Õϵ2$$ \overset{\widetilde }{O}\left({\epsilon}^2\right) $$. From these expansion properties, we derive that the diameter of the giant is whpOϵ(logn)$$ {O}_{\epsilon}\left(\log n\right) $$, and that the mixing time of a lazy random walk on the giant is asymptotically Oϵlog2n$$ {O}_{\epsilon}\left({\log}^2n\right) $$. We also show similar asymptotic expansion properties of (not necessarily connected) linear‐sized subsets in the giant, and the typical existence of a large expander as a subgraph. [ABSTRACT FROM AUTHOR]