Anatomy of a young giant component in the random graph

DOI10.1002/rsa.20342zbMath1230.05260arXiv0906.1839OpenAlexW1989459250MaRDI QIDQ3094602

Eyal Lubetzky, Yuval Peres, Jian Ding, Jeong Han Kim

Publication date: 25 October 2011

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

contiguitygiant componentnear critical random graphPoisson cloning

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items

Universality of cutoff for graphs with an added random matching, On the Cover Time of the Emerging Giant, Cycle lengths in sparse random graphs, The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘), Heavy and light paths and Hamilton cycles, Mixing time of near-critical random graphs, Conformally invariant scaling limits in planar critical percolation, Diameter of the Stochastic Mean-Field Model of Distance, Asymptotics in percolation on high‐girth expanders, Random walks on the random graph, Anatomy of the giant component: the strictly supercritical regime, Speeding up non-Markovian first-passage percolation with a few extra edges, Expected Maximum Block Size in Critical Random Graphs, Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs, The maximal length of 2-path in random critical graphs, Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

Cites Work

• Unnamed Item
• Critical random graphs: Diameter and mixing time
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Tree-valued Markov chains derived from Galton-Watson processes
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Counting connected graphs inside-out
• First passage percolation on random graphs with finite mean degrees
• The continuum random tree. III
• An Elementary Proof of the Hitting Time Theorem
• 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 Random Graphs
• Component behavior near the critical point of the random graph process
• Cycles in a random graph near the critical point
• Almost all cubic graphs are Hamiltonian
• The Structure of a Random Graph at the Point of the Phase Transition
• Diameters in Supercritical Random Graphs Via First Passage Percolation
• The diameter of sparse random graphs
• The Multiplicative Process
• The diameter of sparse random graphs