Expansion in supercritical random subgraphs of the hypercube and its consequences

DOI10.1214/22-AOP1592zbMATH Open1506.05115arXiv2111.06752OpenAlexW3211981972MaRDI QIDQ2105142FDOQ2105142

Authors: Joshua Erde, Mihyun Kang, Michael Krivelevich 

Publication date: 8 December 2022

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: It is well-known that the behaviour of a random subgraph of a $d$-dimensional hypercube, where we include each edge independently with probability $p$, undergoes a phase transition when $p$ is around $frac1d$. More precisely, standard arguments show that just below this value of $p$ all components of this graph have order $O(d)$ with probability tending to one as $doinfty$ (whp for short), whereas Ajtai, Koml'{o}s and Szemer'{e}di [Largest random component of a $k$-cube, Combinatorica 2 (1982), no. 1, 1--7; MR0671140] showed that just above this value, in the supercritical regime, whp there is a unique `giant' component of order $Thetaleft(2^{d}ight)$. We show that whp the vertex-expansion of the giant component is inverse polynomial in $d$. As a consequence we obtain polynomial in $d$ bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component, answering questions of Bollob'{a}s, Kohayakawa and {L}uczak [On the diameter and radius of random subgraphs of the cube, Random Structures and Algorithms 5 (1994), no. 5, 627--648; MR1300592] and of Pete [A note on percolation on $mathbb{Z}^d$: isoperimetric profile via exponential cluster repulsion, Electron. Commun. Probab. 13 (2008), 377--392; MR2415145]. Furthermore, our results imply lower bounds on the circumference and Hadwiger number of a random subgraph of the hypercube in this regime of $p$ which are tight up to polynomial factors in $d$.

Full work available at URL: https://arxiv.org/abs/2111.06752

Recommendations

• Slightly subcritical hypercube percolation
• On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
• Sharp threshold for percolation on expanders
• Hypercube percolation
• The sharp threshold for percolation on expander graphs

zbMATH Keywords

graph expansionhypercube percolationlazy random walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Percolation (82B43) Expander graphs (05C48)

Cites Work

• Title not available (Why is that?)
• Random Graphs
• Title not available (Why is that?)
• Percolation
• Percolation
• A note on the edges of the n-cube
• Evolution of the \(n\)-cube
• Long cycles in locally expanding graphs, with applications
• Random graphs.
• Expander graphs and their applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• The probabilistic method
• Minors in random regular graphs
• Component behavior near the critical point of the random graph process
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Coloring complete bipartite graphs from random lists
• The Evolution of Random Subgraphs of the Cube
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• Title not available (Why is that?)
• The Evolution of Random Graphs
• Random walks on the random graph
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• A note on percolation on \(\mathbb Z^d\): isoperimetric profile via exponential cluster repulsion
• Introduction to Random Graphs
• Assignment of Numbers to Vertices
• Large components in random induced subgraphs of \(n\)-cubes
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Largest random component of a k-cube
• The longest path in a random graph
• Random minimum length spanning trees in regular graphs
• The phase transition in random graphs: a simple proof
• The mixing time of the giant component of a random graph
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• Hypercube percolation
• On the non-planarity of a random subgraph
• The component structure of dense random subgraphs of the hypercube
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• Unlacing hypercube percolation: a survey
• The Evolution of the Cube
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• The diameter of sparse random graphs
• Slightly subcritical hypercube percolation
• Complete matchings in random subgraphs of the cube
• Anatomy of the giant component: the strictly supercritical regime
• Paths and cycles in random subgraphs of graphs with large minimum degree
• On the diameter and radius of randon subgraphs of the cube
• Finding and using expanders in locally sparse graphs
• Expanders -- how to find them, and what to find in them
• Title not available (Why is that?)
• Large complete minors in random subgraphs

Cited In (7)

• Supercritical site percolation on the hypercube: small components are small
• How to build a pillar: a proof of Thomassen's conjecture
• Isoperimetric inequalities and supercritical percolation on high-dimensional graphs
• Expansion in supercritical random subgraphs of expanders and its consequences
• Crux and Long Cycles in Graphs
• Climbing up a random subgraph of the hypercube
• A phase transition for the metric distortion of percolation on the hypercube

This page was built for publication: Expansion in supercritical random subgraphs of the hypercube and its consequences

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