pith. sign in

arxiv: 2605.16511 · v1 · pith:BRRZGLHRnew · submitted 2026-05-15 · 🧮 math.CO · math.PR

Diameters and mixing times for giant components of random graphs with given degrees

Louigi Addario-Berry , Bruce Reed , Corrine Yap This is my paper

Pith reviewed 2026-05-20 16:22 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords random graphsdegree sequencesgiant componentdiametermixing timerandom walkconfiguration modelcomponent sizes
0
0 comments X

The pith

For feasible degree sequences with a giant component, the random graph has a unique giant component with high probability and bounded diameter and random walk mixing time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines random graphs chosen uniformly at random from all simple graphs with a prescribed feasible degree sequence. When the degree sequence is such that a giant component forms, the authors prove that this component is the only one of its size with high probability. They derive bounds on the diameter of the giant component and on the mixing time for a random walk restricted to that component. Bounds are also given for the sizes and diameters of all remaining components, and the paper shows that many of these bounds are tight. A reader would care because the results describe the large-scale geometry and dynamics of random networks with arbitrary but fixed degree distributions.

Core claim

We consider sequences {D_ℓ}ℓ≥1 of feasible degree sequences which have a giant component. We show that with high probability this giant component is unique, and bound its diameter and the mixing time of the random walk on it. We also bound the size and diameter of the other components and show that many of these bounds are tight.

What carries the argument

The uniform random graph G(D) generated from a feasible degree sequence D, studied via the configuration model to track the emergence, uniqueness, and metric properties of its giant component.

If this is right

  • The giant component is unique with high probability.
  • The diameter of the giant component is bounded above.
  • The mixing time of the random walk on the giant component is bounded above.
  • The sizes and diameters of all smaller components are bounded.
  • Several of the upper bounds are tight.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The diameter and mixing-time bounds suggest that search and sampling algorithms restricted to the giant component remain efficient.
  • The results supply a template for analyzing random walks and distances in other random graph models with heterogeneous degrees.
  • Tightness constructions from the paper can serve as test cases for numerical verification of the bounds on large instances.

Load-bearing premise

The degree sequences are feasible and the giant component's uniqueness and size can be analyzed using the configuration model or counting arguments without further regularity conditions on the sequence.

What would settle it

A feasible degree sequence for which a random graph realization has two or more giant components each of linear size with probability bounded away from zero, or for which the diameter of the giant component exceeds the paper's stated upper bound.

read the original abstract

A sequence $D = \{d_1,...d_n\}$ is a feasible degree sequence if there is a graph on $\{1,...,n\}$ such that $i$ has degree $d_i$. For such a sequence, $G(D)$ is a graph chosen uniformly at random from those with the given degree sequence. We consider sequences $\{D_\ell\}_{\ell \geq 1}$ of feasible degree sequences which have a giant component. We show that with high probability this giant component is unique, and bound its diameter and the mixing time of the random walk on it. We also bound the size and diameter of the other components and show that many of these bounds are tight.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper considers sequences of feasible degree sequences {D_ℓ} that admit a giant component in the uniform random graph G(D). It proves that this giant component is unique with high probability, derives upper bounds on its diameter and on the mixing time of the simple random walk on the giant component, and provides bounds on the sizes and diameters of all other components. Several of the stated bounds are shown to be tight via explicit constructions.

Significance. If the derivations hold, the results extend diameter and mixing-time control from the Erdős–Rényi and regular cases to general degree sequences under only feasibility plus existence of a giant component. The explicit tightness examples and the transfer from configuration model to simple graphs are strengths; the work supplies quantitative expansion information that is useful for algorithmic and statistical applications on inhomogeneous networks.

major comments (2)
  1. [§3] §3 (configuration-model approximation): the error term between the multigraph neighborhood exploration and the simple-graph exploration is controlled only by the total number of edges; when max d_i ≫ n^ε the probability of long-range multiple edges is not shown to be o(1) uniformly over all vertices, which directly affects the claimed diameter upper bound. Please add either a max-degree hypothesis or a quantitative error estimate that remains o(diam) under the stated assumptions.
  2. [Theorem 1.2] Theorem 1.2 (mixing-time bound): the proof invokes a conductance lower bound derived from the branching-process approximation, but the conductance estimate is stated only for the giant component; it is unclear whether the same argument yields the claimed O(log n) mixing time when the second-moment condition on D is allowed to grow with n. A concrete counter-example or an additional regularity hypothesis is needed to confirm the bound is load-bearing.
minor comments (2)
  1. [§1.1] The definition of 'feasible' in §1.1 should explicitly recall the handshaking lemma and the graphicality condition used later in the configuration-model coupling.
  2. [§5] In the tightness constructions of §5, the degree sequences are given only asymptotically; please state the exact finite-n sequences used to obtain the matching lower bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address each major comment below, indicating where revisions will be made and where we believe the existing arguments suffice.

read point-by-point responses

  1. Referee: [§3] §3 (configuration-model approximation): the error term between the multigraph neighborhood exploration and the simple-graph exploration is controlled only by the total number of edges; when max d_i ≫ n^ε the probability of long-range multiple edges is not shown to be o(1) uniformly over all vertices, which directly affects the claimed diameter upper bound. Please add either a max-degree hypothesis or a quantitative error estimate that remains o(diam) under the stated assumptions.

    Authors: We agree that a more uniform control is desirable when the maximum degree grows faster than n^ε. In the current proof the total number of edges controls the expected number of multiple edges globally, but uniformity over vertices in the exploration tree requires an additional estimate. We will add a quantitative bound showing that the probability of a long-range multiple edge affecting the diameter exploration is o(1) uniformly, using a first-moment calculation over pairs at distance roughly diam/2; this error remains o(diam) under the paper’s standing assumptions. The revised Section 3 will include this estimate as a new lemma. revision: yes

  2. Referee: [Theorem 1.2] Theorem 1.2 (mixing-time bound): the proof invokes a conductance lower bound derived from the branching-process approximation, but the conductance estimate is stated only for the giant component; it is unclear whether the same argument yields the claimed O(log n) mixing time when the second-moment condition on D is allowed to grow with n. A concrete counter-example or an additional regularity hypothesis is needed to confirm the bound is load-bearing.

    Authors: The branching-process approximation yields a conductance lower bound of Ω(1) for the giant component whenever the giant exists (i.e., whenever the mean offspring exceeds 1 by a fixed margin). This lower bound is insensitive to polynomial growth of the second moment provided the giant-component assumption holds; the resulting Cheeger inequality still produces an O(log n) mixing-time upper bound. We will insert a short paragraph after the conductance estimate clarifying that the same branching-process comparison applies verbatim when the second moment grows (slowly) with n, and we will note that no additional regularity hypothesis is required under the paper’s hypotheses. No counter-example is expected. revision: no

Circularity Check

0 steps flagged

No circularity detected; derivation is self-contained

full rationale

The paper uses standard probabilistic arguments on the configuration model to establish uniqueness of the giant component and derive diameter and mixing-time bounds for feasible degree sequences. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described claims. The central results rest on direct counting and coupling arguments that are independent of the target quantities, with feasibility and giant-component existence as explicit hypotheses. This is the typical honest outcome for rigorous random-graph papers without parameter fitting or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard definition of feasible degree sequences and the uniform random model G(D); no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption A degree sequence D is feasible if at least one simple graph on n vertices realizes exactly those degrees.
    Invoked in the opening definition of G(D).
  • domain assumption The sequence family {D_ℓ} produces a giant component whose size is linear in n.
    Stated as the setting in which the uniqueness and diameter results are proved.

pith-pipeline@v0.9.0 · 5643 in / 1402 out tokens · 64851 ms · 2026-05-20T16:22:11.926650+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    J. K. A Bekessy, P. Bekessy. Asymptotic enumeration of regular matrices.Studio Scientiarum mathematicum Hungarica, 7:343–353, 1972. 5

    work page 1972

  2. [2]

    Addario-Berry and G

    L. Addario-Berry and G. Crudele. Universal diameter bounds for random graphs with given degrees. arXiv:2507.10759 [math.PR], 2025. 17

    work page arXiv 2025

  3. [3]

    Benjamini, G

    I. Benjamini, G. Kozma, and N. Wormald. The mixing time of the giant component of a random graph.Random Structures & Algorithms, 45(3):383–407, 2014. 6

    work page 2014

  4. [4]

    Fernholz and V

    D. Fernholz and V. Ramachandran. The diameter of sparse random graphs.Random Structures & Algorithms, 31(4):482–516, 2007. 6

    work page 2007

  5. [5]

    Flajolet and R

    P. Flajolet and R. Sedgewick.Analytic Combinatorics. Cambridge University Press,

    work page

  6. [6]

    Fountoulakis and B

    N. Fountoulakis and B. Reed. Faster mixing and small bottlenecks.Probability Theory and Related Fields, 137(1):475–486, 2007. 6, 8

    work page 2007

  7. [7]

    Fountoulakis and B

    N. Fountoulakis and B. A. Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph.Random Structures & Algorithms, 33(1):68–86, 2008. 6

    work page 2008

  8. [8]

    Hildebrand

    M. Hildebrand. Random walks on random simple graphs.Random Structures & Algorithms, 8(4):301–318, 1996. 6

    work page 1996

  9. [9]

    S. Janson. The probability that a random multigraph is simple.Combin. Probab. Comput., 18(1-2):205–225, 2009. 6 MIXING FOR GIANT COMPONENT OF RANDOM GRAPHS WITH GIVEN DEGREES 41

    work page 2009

  10. [10]

    S. Janson. The probability that a random multigraph is simple. II.J. Appl. Probab., 51A:123–137, 2014. 6

    work page 2014

  11. [11]

    F. Joos, G. Perarnau, D. Rautenbach, and B. Reed. How to determine if a random graph with a fixed degree sequence has a giant component.Probability Theory and Related Fields, 170(3-4):263–310, 2018. 2, 4, 6

    work page 2018

  12. [12]

    McDiarmid

    C. McDiarmid. Concentration. InProbabilistic methods for algorithmic discrete math- ematics, volume 16 ofAlgorithms Combin., pages 195–248. Springer, Berlin, 1998. 21

    work page 1998

  13. [13]

    Nachmias and Y

    A. Nachmias and Y. Peres. Critical random graphs, diameter and mixing time.Annals of Probability, 36(4):1267–1286, 2008. 3

    work page 2008

  14. [14]

    Nachmias and Y

    A. Nachmias and Y. Peres. Critical random graphs: Diameter and mixing time. Annals of Probability, pages 1267–1286, 2008. 6

    work page 2008

  15. [15]

    Van Den Esker, R

    H. Van Den Esker, R. Van Der Hofstad, G. Hooghiemstra, and D. Znamenski. Dis- tances in random graphs with infinite mean degrees.Extremes, 8(3):111–141, 2005. 6

    work page 2005

  16. [16]

    van der Hofstad, G

    R. van der Hofstad, G. Hooghiemstra, and P. Van Mieghem. Distances in random graphs with finite variance degrees.Random Structures & Algorithms, 27(1):76–123,

    work page

  17. [17]

    6 Department of Mathematics and Statistics, McGill University, Montr´eal, Canada Email address:louigi.addario@mcgill.ca Institute of Mathematics, Academia Sinica, Taipei, Taiwan Email address:bruce.al.reed@gmail.com School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA Email address:math@corrineyap.com

    work page