The mixing time of the giant component of a random graph
From MaRDI portal
Publication:2930052
DOI10.1002/rsa.20539zbMath1373.05172arXivmath/0610459OpenAlexW1488446430MaRDI QIDQ2930052
Itai Benjamini, Gady Kozma, Nicholas C. Wormald
Publication date: 17 November 2014
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0610459
Related Items
Mixing times of random walks on dynamic configuration models, A threshold for cutoff in two-community random graphs, Random walk on sparse random digraphs, Smoothed Analysis on Connected Graphs, Simple random walk on long range percolation clusters. I: Heat kernel bounds, Voter models on subcritical scale‐free random graphs, Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs, Speeding up random walk mixing by starting from a uniform vertex, On the threshold for \(k\)-regular subgraphs of random graphs, Mixing time of near-critical random graphs, On the tree-depth of random graphs, Bipartitioning of directed and mixed random graphs, Expansion properties of a random regular graph after random vertex deletions, Critical random graphs: Diameter and mixing time, \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph, Random walks on the random graph, Hypercube percolation, Cutoff for random walk on dynamical Erdős-Rényi graph, Anatomy of the giant component: the strictly supercritical regime, Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439, On giant components and treewidth in the layers model, Speeding up non-Markovian first-passage percolation with a few extra edges, Interactive knowledge discovery from hidden data through sampling of frequent patterns, Phase transition for the vacant set left by random walk on the giant component of a random graph, Expansion in supercritical random subgraphs of the hypercube and its consequences
Cites Work
- Unnamed Item
- Mixing time of near-critical random graphs
- Mixing and hitting times for finite Markov chains
- Mixing times are hitting times of large sets
- Mixing time bounds via the spectral profile
- Faster mixing and small bottlenecks
- Random walk on the incipient infinite cluster for oriented percolation in high dimensions
- Critical random graphs: Diameter and mixing time
- Birth control for giants
- Eigenvalues and expanders
- Approximate counting, uniform generation and rapidly mixing Markov chains
- On the mixing time of a simple random walk on the super critical percolation cluster
- Analysis of edge deletion processes on faulty random regular graphs.
- Counting connected graphs inside-out
- Percolation on finite graphs and isoperimetric inequalities.
- Random walk on the incipient infinite cluster on trees
- Evolving sets, mixing and heat kernel bounds
- Almost all graphs with 1.44n edges are 3-colorable
- The evolution of the mixing rate of a simple random walk on the giant component of a random graph
- Some Inequalities for Reversible Markov Chains
- The phase transition in inhomogeneous random graphs
- The diameter of sparse random graphs
- Random regular graphs with edge faults: Expansion through cores
