The diameter of sparse random graphs

DOI10.1017/S0963548310000325MaRDI QIDQ4911116zbMATH OpenOpenAlexFDO

Authors Oliver Riordan, Nicholas Wormald

Publication date 13 March 2013

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

branching processdiameterrandom graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this paper we study the diameter of the random graph $G(n,p)$, i.e., the the largest finite distance between two vertices, for a wide range of functions $p=p(n)$. For $p=la/n$ with $la>1$ constant, we give a simple proof of an essentially best possible result, with an $O_p(1)$ additive correction term. Using similar techniques, we establish 2-point concentration in the case that $npoinfty$. For $p=(1+epsilon)/n$ with $epsilono0$, we obtain a corresponding result that applies all the way down to the scaling window of the phase transition, with an $O_p(1/epsilon)$ additive correction term whose (appropriately scaled) limiting distribution we describe. Combined with earlier results, our new results complete the determination of the diameter of the random graph $G(n,p)$ to an accuracy of the order of its standard deviation (or better), for all functions $p=p(n)$. Throughout we use branching process methods, rather than the more common approach of separate analysis of the 2-core and the trees attached to it.

Recommendations

• The diameter of sparse random graphs
• The diameter of sparse random graphs
• Diameters of random bipartite graphs
• The diameter of a random graph with bounded diameter
• Diameter of random spanning trees in a given graph

Cites work

• Branching Processes
• Component behavior near the critical point of the random graph process
• Counting connected graphs inside-out
• Critical random graphs: Diameter and mixing time
• Cycles in a random graph near the critical point
• Distance in random graphs with infinite mean degrees
• Distances in random graphs with finite mean and infinite variance degrees
• Distances in random graphs with finite variance degrees
• scientific article; zbMATH DE number 1380601 (Why is no real title available?)
• Inequalities with applications to percolation and reliability
• Proof of the Van den Berg–Kesten Conjecture
• The Average Distance in a Random Graph with Given Expected Degrees
• The average distances in random graphs with given expected degrees
• The Diameter of a Cycle Plus a Random Matching
• The diameter of a scale-free random graph
• The diameter of random regular graphs
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• The phase transition in inhomogeneous random graphs

Cited in

(47)

• Geodesic cycles in random graphs
• Transience and recurrence of random walks on percolation clusters in an ultrametric space
• Random walks on the random graph
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• The average distance and the diameter of dense random regular graphs
• The diameter of weighted random graphs
• Weak disorder asymptotics in the stochastic mean-field model of distance
• The continuum limit of critical random graphs
• Diameters of random circulant graphs
• Anatomy of the giant component: the strictly supercritical regime
• The diameter of the directed configuration model
• Concentration of rainbow \(k\)-connectivity of a multiplex random graph
• Diameter of random spanning trees in a given graph
• On the diameter of hyperbolic random graphs
• Mixing time of near-critical random graphs
• On the diameter of hyperbolic random graphs
• The diameter of dense random regular graphs
• The diameter of inhomogeneous random graphs
• scientific article; zbMATH DE number 6960780 (Why is no real title available?)
• The diameter of a random graph with bounded diameter
• scientific article; zbMATH DE number 1380601 (Why is no real title available?)
• Diameters in supercritical random graphs via first passage percolation
• Traveling in randomly embedded random graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Approximate lumpability for Markovian agent-based models using local symmetries
• The Mixing Time of the Newman-Watts Small-World Model
• On the diameter of random planar graphs
• Diameter of the stochastic mean-field model of distance
• Diameter in ultra-small scale-free random graphs
• On the diameters of commuting graphs arising from random skew-symmetric matrices.
• The diameter of sparse random graphs
• On random points in the unit disk
• On the spread of random graphs
• The mixing time of the Newman-Watts small world
• The diameter of sparse random graphs
• Strong noise sensitivity and random graphs
• scientific article; zbMATH DE number 7758311 (Why is no real title available?)
• Random walks on decorated Galton-Watson trees
• Expansion in supercritical random subgraphs of expanders and its consequences
• Reconstructing a point set from a random subset of its pairwise distances
• Minimum stationary values of sparse random directed graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Distances and isoperimetric inequalities in random triangulations of high genus
• Asymptotic diameter of preferential attachment model
• Diameter and stationary distribution of random r-out digraphs
• Diameters of random bipartite graphs
• Distributed algorithms for random graphs

This page was built for publication: The diameter of sparse random graphs

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