Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

MaRDI QIDQ6398745zbMATH OpenFDO

Authors Sahar Diskin, Michael Krivelevich

Publication date 10 May 2022

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: In 2004, Frieze, Krivelevich and Martin [17] 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 $ildeOleft(epsilo{n}^{2}ight)$. From these expansion properties, we derive that the diameter of the giant is typically $O_{epsilon}left(lognight)$, and that the mixing time of a lazy random walk on the giant is asymptotically $O_{epsilon}left(lo{g}^{2}night)$. 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.

This page was built for publication: Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398745)