Expansion in supercritical random subgraphs of the hypercube and its consequences

DOI10.1214/22-AOP1592zbMath1506.05115arXiv2111.06752OpenAlexW3211981972MaRDI QIDQ2105142

Michael Krivelevich, Joshua Erde, Mihyun Kang

Publication date: 8 December 2022

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

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

zbMATH Keywords

graph expansionhypercube percolationlazy random walk

Mathematics Subject Classification ID

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

Related Items

Crux and Long Cycles in Graphs, Supercritical site percolation on the hypercube: small components are small, How to build a pillar: a proof of Thomassen's conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• Hypercube percolation
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• Random subgraphs of finite graphs. III: The phase transition for the \(n\)-cube
• Large components in random induced subgraphs of \(n\)-cubes
• A note on percolation on \(\mathbb Z^d\): isoperimetric profile via exponential cluster repulsion
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The longest path in a random graph
• Largest random component of a k-cube
• A note on the edges of the n-cube
• Evolution of the \(n\)-cube
• Random minimum length spanning trees in regular graphs
• Random walks on the random graph
• Paths and cycles in random subgraphs of graphs with large minimum degree
• Long cycles in locally expanding graphs, with applications
• Unlacing hypercube percolation: a survey
• Anatomy of the giant component: the strictly supercritical regime
• The phase transition in random graphs: A simple proof
• The mixing time of the giant component of a random graph
• Introduction to Random Graphs
• Minors in random regular graphs
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Percolation
• Coloring complete bipartite graphs from random lists
• Complete matchings in random subgraphs of the cube
• Expander graphs and their applications
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Evolution of the Cube
• The Evolution of Random Graphs
• Component behavior near the critical point of the random graph process
• The Evolution of Random Subgraphs of the Cube
• Percolation
• On the diameter and radius of randon subgraphs of the cube
• Assignment of Numbers to Vertices
• Finding and Using Expanders in Locally Sparse Graphs
• The Diameter of Sparse Random Graphs
• Slightly subcritical hypercube percolation
• Expanders – how to find them, and what to find in them
• On the Non-Planarity of a Random Subgraph
• The diameter of sparse random graphs
• Maximally Connected Arrays on the n-Cube
• Random Graphs
• Optimal Assignments of Numbers to Vertices
• Large complete minors in random subgraphs
• The order of the largest complete minor in a random graph
• The diameter of sparse random graphs
• The component structure of dense random subgraphs of the hypercube