Expansion in Supercritical Random Subgraphs of Expanders and its Consequences

2022/05/10 by Sahar Diskin, Michael Krivelevich, Diskin, Sahar +1 · 1 citation
Computer Science · Mathematics · #05C80 #60K35 #82B43 #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2205.04852

openalex publication_date 2022/05/10 · openalex created_date 2022/05/22 · openalex updated_date 2026/07/28

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 O(ε²). From these expansion properties, we derive that the diameter of the giant is typically O_ε(log n), and that the mixing time of a lazy random walk on the giant is asymptotically O_ε(log² n). 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.

Cited by

• Cycle lengths in the percolated hypercube

Related

• Expansion in supercritical random subgraphs of the hypercube and its\n consequences
• Anatomy of a young giant component in the random graph
• The Evolution of the Mixing Rate
• The size of the giant component in random hypergraphs
• Anatomy of the giant component: The strictly supercritical regime