Pith. sign in

REVIEW 1 major objections 4 minor 1 cited by

Monotonicity and decompositions of random regular graphs

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For many degrees, sparse random regular graphs nest inside denser ones

desk verdict Strong paper with a real but fixable presentation gap in the covariance estimate that Proposition 3.8 relies on. read the letter →

arxiv 2505.22875 v1 pith:3J2VHJS2 submitted 2025-05-28 math.CO math.PR

Lawrence Hollom , Lyuben Lichev , Adva Mond , Julien Portier , Yiting Wang This is my paper · ORCID
classification math.COmath.PR MSC 05C8005C7005C30
keywords randomregulargraphsmonotonecouplinggraphdecompositionperfectmatchingstotalvariationdistancecontiguitysprinklingtriangles
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Random regular graphs are the uniform model on all $d$-regular graphs with $n$ vertices, and this paper proves that they are monotone under inclusion for a wide range of degrees. For even $n$, whenever $d_1$ lies between $3$ and $n^{1/7}/\log n$ and $d_2$ is any larger degree tending to infinity, there is a coupling of $G(n,d_1)$ and $G(n,d_2)$ under which the first graph is a subgraph of the second with probability $1-o(1)$. This confirms the monotone-coupling conjecture in a new regime that includes every constant $d_1 \ge 3$, which had previously been out of reach. The paper also shows that, for $d_2 = \omega(1)$ with $d_2 = O(n^{1/10})$, the disjoint union of a random $d_1$-regular graph and a random $(d_2-d_1)$-regular graph has asymptotically the same distribution whatever $d_1$ is chosen, as long as both parts are large, and that any high-probability property of the union of $d$ random edge-disjoint perfect matchings transfers to $G(n,d)$ for $3 \le d \le n^{1/10}$. These inclusion and decomposition statements matter because they give random regular graphs the kind of sprinkling-like flexibility that has long been available for binomial random graphs.

What carries the argument

The load-bearing object is the $\oplus$ operation on graph distributions: $\mu \oplus \nu$ samples two graphs from $\mu$ and $\nu$ on the same vertex set conditionally on being edge-disjoint and takes their union. Repeated use of $\oplus$ with the uniform $d$-regular distribution $\mu_d$ and the matching-weighted distribution $\nu_d$ (where each graph receives weight proportional to its number of 1-factorisations) lets the authors view $G(n,d_2)$ as $G(n,d_1)$ plus $d_2-d_1$ perfect matchings. The argument is carried by three mechanisms: a stability lemma (Corollary 2.9) saying that total variation distance and contiguity are preserved by $\oplus$ with a fixed third measure; a refined concentration bound for the number of perfect matchings in $G(n,d)$, obtained through the orthogonal-decomposition-and-projection method, in which the perfect-matching count is approximated by a linear regression on the triangle count; and a bipartite-degree coupling lemma that converts this concentration into the $O(d^{-1.1})$ bound on $d_{\mathrm{TV}}(\mu_d \oplus \mu_1, \mu_{d+1})$.

What would settle it

Directly compute the covariance $\mathrm{Cov}(X,Y)$ between triangle count $X$ and perfect-matching count $Y$ in $G(n,d)$ for growing $d \le n^{1/10}$ by moment or switching calculations; if the coefficient of $\mathbb{E}[X]\mathbb{E}[Y]/d^3$ in its leading term is not $1+o(1)$, then Proposition 3.8 fails and the claimed $d_{\mathrm{TV}}(\mu_d \oplus \mu_1, \mu_{d+1}) = O(d^{-1.1})$ bound is false, which would overturn the transfer theorems in that range.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for even $n$, every $d_1 \in [3, n^{1/7}/\log n]$ and every $d_2 \in [d_1, n-1]$ with $d_2 = \omega(1)$, there exists a coupling of $G_1 \sim G(n,d_1)$ and $G_2 \sim G(n,d_2)$ such that $\mathbb{P}(G_1 \subseteq G_2) = 1 - o(1)$. The supporting results are Theorem 1.4, which states that for $d_2 = \omega(1)$ and $d_2 = O(n^{1/10})$, the distributions of $G(n,d_1) \oplus G(n,d_2-d_1)$ and $G(n,d_1') \oplus G(n,d_2-d_1')$ can be coupled to be equal with probability $1-o(1)$ whenever $d_1$, $d_1'$, $d_2-d_1$ and $d_2-d_1'$ all tend to infinity, and Theorem 1.5, which states that any property holding with high probability for the union of $d$ random edge-disjoint perfect matchings holds with high probability for $G(n,d)$ when $3 \le d \le n^{1/10}$. The engine behind all three results is a sharp quantitative estimate: adding one random perfect matching to a random $d$-regular graph moves the distribution by at most $O(d^{-1.1})$ in total variation distance, uniformly for $d \le n^{1/10}$.

Load-bearing premise

The load-bearing premise is that the covariance between the triangle count and the perfect-matching count in $G(n,d)$ has leading term exactly $d^{-3}\,\mathbb{E}[X]\mathbb{E}[Y]$; if that coefficient is off by any constant factor, the $d^{-1.1}$ total-variation bounds used to prove Theorems 1.4 and 1.5, and the small-$d_2$ part of Theorem 1.2, collapse.

Editorial extensions

If this is right

  • For even $n$, the monotone-coupling conjecture now holds for every constant $d_1 \ge 3$ with any larger $d_2 = \omega(1)$ up to $n-1$, a regime far beyond the previous polylogarithmic-degree results.
  • In the range $d_2 = \omega(1)$, $d_2 = O(n^{1/10})$, the split point $d_1$ in the two-way decomposition of a random regular graph is asymptotically irrelevant: the resulting distributions coincide up to $o(1)$ in total variation.
  • Any property that holds with high probability in the union of $d$ random edge-disjoint perfect matchings also holds with high probability in $G(n,d)$, for $3 \le d \le n^{1/10}$, giving a one-way transfer from a tractable matching model to random regular graphs.
  • Adding a single random perfect matching to $G(n,d)$ moves the distribution by $O(d^{-1.1})$ in total variation distance, and because this error is summable over $d$, repeated one-matching steps accumulate only $o(1)$ total error.
  • The inclusion $G(n,d_1) \subseteq G(n,d_2)$ is achieved with high probability for all $d_2$ up to $n-1$ when $d_1$ is small, by chaining the new small-degree decomposition with previously known large-degree coupling regimes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable strengthening of the paper's range is that the same one-matching-at-a-time decomposition should work up to $d \le n^{1/7-\varepsilon}$ once the variance estimates for perfect matchings are sharpened; the paper's own bounds are what stop at $n^{1/10}$.
  • If the converse of Theorem 1.5 also holds, then every high-probability question about random regular graphs of degree up to $n^{1/10}$ would reduce to the same question about a union of $d$ random perfect matchings, making the transfer genuinely two-way.
  • The $d^{-1.1}$ exponent appears calibrated to make the harmonic sum $\sum_d d^{-1.1}$ converge, which suggests the decomposition viewpoint is stable under many iterations and that the missing ingredient for larger $d$ is likely a concentration estimate for 2-factors rather than a structural obstruction.
  • For odd $n$, the same programme would require concentration for the number of 2-factors of growing degree, which the paper identifies as unavailable; obtaining that estimate would open the odd-$n$ analogue of the monotonicity theorem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper studies monotone couplings and decompositions of random regular graphs. Its main results are Theorem 1.2, confirming the Gao–Isaev–McKay monotonicity conjecture for even n, 3 ≤ d1 ≤ n^{1/7}/log n, d2 ∈ [d1, n−1] with d2 = ω(1); Theorem 1.4, showing asymptotic equivalence of two disjoint-union models G(n,d1) ⊕ G(n,d2−d1) and G(n,d1') ⊕ G(n,d2−d1') when all relevant degrees grow; and Theorem 1.5, transferring whp properties from a union of d perfect matchings to G(n,d) for d ≤ n^{1/10}. The technical core is Proposition 3.1, a refined concentration bound for the number of perfect matchings in G(n,d), proved via Janson's orthogonal projection method, and Corollary 3.2, a total-variation bound between μ_d ⊕ μ_1 and μ_{d+1}.

Significance. If the results are correct, they resolve new cases of two open conjectures and provide a useful toolbox for random regular graphs: an iteration-friendly total-variation estimate, a random-overlay sampling procedure, and a transfer principle from unions of perfect matchings. The proofs are detailed and build on established external results (McKay's enumeration, Wormald's contiguity, Gao's moment estimates); no parameters are fitted and the theorems are not assumed. The main concern is that one load-bearing covariance estimate is stated too weakly for the proof that uses it, so the central concentration result currently lacks support as written.

major comments (1)
  1. [Section 3, Proposition 3.8, Eq. (18)] The proof of Var[Y−Y*]=O(E[Y]^2/d^4) requires the asymptotic Cov(X,Y)=(d^{-3}+O(d^{-4}+d/n))E[X]E[Y]. This is used to write Var[Y*]=Cov(X,Y)^2/Var[X]=E[Y]^2/(6d^3)+O(E[Y]^2/d^4), which cancels the leading term of Var[Y] in (17). However, Claim 3.3(1), attributed to [6, Theorem 10], states only Cov(X,Y)=O(E[X]E[Y]/d^3). That weaker bound yields Var[Y*]=O(E[Y]^2/d^3), so the residual Var[Y]−Var[Y*] may be of order E[Y]^2/d^3 rather than E[Y]^2/d^4. In that case Chebyshev's inequality in (20) gives only O(d^{-0.8}) for the tail P(|Y−Y*| ≥ d^{-1.1}E[Y]/2), not O(d^{-1.8}); the same failure propagates to Proposition 3.1, Corollary 3.2, Theorems 1.4 and 1.5, and the d2 ≤ (log n)^8 part of Theorem 1.2. The manuscript must either state and justify the precise covariance expansion with the correct leading coefficient, or provide an alternative derivation of the variance bound.
minor comments (4)
  1. [Lemma 5.3] The lemma is stated for every d ≥ 1, but its proof invokes Theorem 2.2 to justify contiguity of μ_d and ν_d; Theorem 2.2 is stated only for d = sum d_i ≥ 3. The cases d = 1 and d = 2 should either be excluded or handled separately.
  2. [Corollary 3.2] In the proof, Proposition 3.1 is applied to the number of perfect matchings in G(n,d+1) although Proposition 3.1 is formulated for G(n,d). The constant can absorb the shift, but the application should be made explicit.
  3. [Section 6, proof of Theorem 1.2] The quantity d' = d2/2 may be non-integral. Since d2 = ω(1) in the relevant case, rounding is harmless, but the text should state that floors or ceilings are being used.
  4. [Lemma 2.10] The claim that contributions from edges repeated at least three times are o(1) is asserted without the detail given for the pairwise-repetition contribution; a brief justification would improve the rigor of the factorial-moment computation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from external enumeration, contiguity, and moment-estimate results, and the only self-citation is a non-load-bearing forward reference.

full rationale

The paper's derivation chain is self-contained against external benchmarks and no circular reduction is exhibited. Theorem 1.2 is built from Corollary 2.9, which uses McKay's enumeration (Theorem 2.1); Corollary 3.2, which uses Proposition 3.1 and Strassen-type coupling from Isaev, McKay, Southwell and Zhukovskii (Theorem 2.3); and the large-degree case imported from Gao's [6, Theorem 6]. Theorems 1.4 and 1.5 are derived from Corollaries 2.9 and 3.2 together with Wormald's contiguity result (Theorem 2.2). Proposition 3.1 relies on Gao's moment estimates (Claim 3.3), Janson's orthogonal projection method, and the paper's own Lemma 3.5 computed from Gao's conditional edge-probability estimates; none of these inputs assumes the target coupling, decomposition, or monotonicity statements. The only self-citation is [11], a forthcoming application of Theorem 1.5, and it is not used as evidence in any proof. The covariance-coefficient concern raised in the reader's take is a potential correctness gap: Claim 3.3(1) is stated only as O(E[X]E[Y]/d^3), while equation (18) uses a leading coefficient of 1 in Cov(X,Y). This is an internal unstated strengthening of an external estimate, not a circular step, because the missing coefficient is not the paper's own conclusion and is not assumed from the theorem being proved. No parameter is fitted to the target outcomes, and no cited uniqueness or determinacy result is used to forbid alternatives.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no free parameters and no invented entities. The axioms are the external theorems it imports: McKay's asymptotic enumeration, Wormald's contiguity, the Strassen-type coupling, Gao's moment estimates for triangles and perfect matchings, and Gao's conditioned edge probabilities. The flagged covariance issue is an axiom-statement mismatch: the imported estimate is quoted too weakly for the use made of it.

assumptions (6)
  • standard math McKay's asymptotic enumeration of graphs with a given sparse degree sequence in the complement of a sparse graph (Theorem 2.1).
    Used in Corollary 2.9 to show the factor beta_n(G) in the direct-sum operation is nearly constant, and in the proof of Theorem 1.2 to show uniformity of decomposition probabilities.
  • standard math Contiguity of the uniform d-regular graph model G(n,d) and the union model G(n,d1) direct-sum ... direct-sum G(n,dk) for d1 + ... + dk = d >= 3 (Theorem 2.2, Wormald).
    Used in Lemma 5.3 and Theorem 1.5 to transfer whp events between mu_d and nu_d.
  • standard math Strassen-type coupling lemma for bipartite graphs with almost all vertices of high degree (Theorem 2.3, from Isaev-McKay-Southwell-Zhukovskii).
    Converts the perfect-matching concentration of Proposition 3.1 into the total variation bound of Corollary 3.2.
  • domain assumption Gao's moment estimates for triangles and perfect matchings in random regular graphs (Claim 3.3, from [6,7]), including the E[Y^2] expansion and the Cov(X,Y) estimate.
    These estimates are imported from prior literature; the Cov(X,Y) part is quoted as an O-bound but used in a stronger asymptotic form, which is a flagged gap.
  • standard math Gao's conditional edge inclusion probability in random regular graphs given a partially exposed subgraph (Theorem 3.4).
    Used in Lemma 3.5 to compute the third and fourth moments of the triangle count.
  • domain assumption All results assume n even and d2 n even so that d-regular graphs and perfect matchings exist.
    Stated at the start of Theorem 1.2; the models G(n,d) are defined only when dn is even.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monotonicity and decompositions of random regular graphs." pith.science (2026). https://pith.science/paper/3J2VHJS2

@misc{pith2026250522875,
  author       = {Pith},
  title        = {Pith review of: Monotonicity and decompositions of random regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3J2VHJS2}},
  note         = {Machine review of arXiv:2505.22875}
}
abstract

In this work we establish several monotonicity and decomposition results in the framework of random regular graphs. Among other results, we show that, for a wide range of parameters $d_1 \leq d_2$, there exists a coupling of $G(n,d_1)$ and $G(n,d_2)$ satisfying that $G(n,d_1) \subseteq G(n,d_2)$ with high probability, confirming a conjecture of Gao, Isaev and McKay in a new regime. Our contributions include new tools for analysing contiguity and total variation distance between random regular graph models, a novel procedure for generating unions of random edge-disjoint perfect matchings, and refined estimates of Gao's bounds on the number of perfect matchings in random regular graphs. In addition, we make progress towards another conjecture of Isaev, McKay, Southwell and Zhukovskii.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Sums along the edges of bounded degree graphs

    math.CO 2025-07 conditional novelty 8.0 of 10

    Random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group, proving a polynomial lower bound that is tight up to polylog factors.

Reference graph

Works this paper leans on

28 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [1]

    S. Bau, N. C. Wormald, and S. Zhou,Decycling numbers of random regular graphs, Random Struc- tures and Algorithms21 (2002), no. 3-4, 397–413

    work page 2002

  2. [2]

    Den Hollander, Probability theory: The coupling method, 2012, Lecture notes available online (https://prob.math.leidenuniv.nl/lecturenotes/CouplingLectures.pdf)

    F. Den Hollander, Probability theory: The coupling method, 2012, Lecture notes available online (https://prob.math.leidenuniv.nl/lecturenotes/CouplingLectures.pdf)

    work page 2012

  3. [3]

    Dudek, A

    A. Dudek, A. Frieze, A. Ruciński, and M. Šileikis,Embedding the Erdős–Rényi hypergraph into the random regular hypergraph and Hamiltonicity, Journal of Combinatorial Theory, Series B122 (2017), 719–740

    work page 2017

  4. [4]

    A.FerberandV.Jain, 1-factorizations of pseudorandom graphs, 2018IEEE59thAnnualSymposium on Foundations of Computer Science (FOCS), IEEE, 2018, pp. 698–708

    work page 2018

  5. [5]

    Fountoulakis, F

    N. Fountoulakis, F. Joos, and G. Perarnau,Percolation on random graphs with a fixed degree se- quence, SIAM Journal on Discrete Mathematics36 (2022), no. 1, 1–46

    work page 2022

  6. [6]

    Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures and Algorithms62 (2023), no

    P. Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures and Algorithms62 (2023), no. 4, 935–955

    work page 2023

  7. [7]

    Gao,Triangles and subgraph probabilities in random regular graphs, The Electronic Journal of Combinatorics (2024), paper P1.2

    P. Gao,Triangles and subgraph probabilities in random regular graphs, The Electronic Journal of Combinatorics (2024), paper P1.2

    2024

  8. [8]

    P. Gao, M. Isaev, and B. McKay,Kim–Vu’s sandwich conjecture is true ford≥ log4n, 2020, arXiv preprint arXiv:2011.09449

    arXiv 2020

Show all 28 references
  1. [9]

    P. Gao, M. Isaev, and B. D. McKay,Sandwiching dense random regular graphs between binomial random graphs, Probability Theory and Related Fields184 (2022), no. 1-2, 115–158

    2022

  2. [10]

    4, 911– 934

    P.GaoandY.Ohapkin, Subgraph probability of random graphs with specified degrees and applications to chromatic number and connectivity, Random Structures and Algorithms62 (2023), no. 4, 911– 934

    2023

  3. [11]

    Hollom, L

    L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang,Approximate Itai-Zehavi conjecture for random graphs, In preparation

  4. [12]

    Isaev, B

    M. Isaev, B. D. McKay, A. Southwell, and M. Zhukovskii,Sprinkling with random regular graphs, Electronic Journal of Probability30 (2025), 1–20

    2025

  5. [13]

    Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, Memoirs of the American Mathematical Society111 (1994), no

    S. Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, Memoirs of the American Mathematical Society111 (1994), no. 534, vi+78

    1994

  6. [14]

    Janson,Random regular graphs: asymptotic distributions and contiguity, Combinatorics, Proba- bility and Computing4 (1995), no

    S. Janson,Random regular graphs: asymptotic distributions and contiguity, Combinatorics, Proba- bility and Computing4 (1995), no. 4, 369–405. 18

    1995

  7. [15]

    8, 3321–3332

    F.JoosandG.Perarnau, Critical percolation on random regular graphs, ProceedingsoftheAmerican Mathematical Society146 (2018), no. 8, 3321–3332

    2018

  8. [16]

    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 Fields170 (2018), no. 1-2, 263–310

    2018

  9. [17]

    J. H. Kim and V. H. Vu,Sandwiching random graphs: universality between random graph models, Advances in Mathematics188 (2004), no. 2, 444–469

    2004

  10. [18]

    J. H. Kim and N. C. Wormald,Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, Journal of Combinatorial Theory, Series B81 (2001), no. 1, 20–44

    2001

  11. [19]

    Klimošová, C

    T. Klimošová, C. Reiher, A. Ruciński, and M. Šileikis,Sandwiching biregular random graphs, Com- binatorics, Probability and Computing32 (2023), no. 1, 1–44

    2023

  12. [20]

    Koperberg,Couplings and Matchings: Combinatorial notes on Strassen’s theorem, Statistics and Probability Letters209 (2024), 110089

    T. Koperberg,Couplings and Matchings: Combinatorial notes on Strassen’s theorem, Statistics and Probability Letters209 (2024), 110089

    2024

  13. [21]

    Krivelevich, B

    M. Krivelevich, B. Sudakov, V. H. Vu, and N. C. Wormald,Random regular graphs of high degree, Random Structures and Algorithms18 (2001), no. 4, 346–363

    2001

  14. [22]

    Lichev, D

    L. Lichev, D. Mitsche, and G. Perarnau,Percolation on dense random graphs with given degrees, Journal of Combinatorial Theory, Series B167 (2024), 250–282

    2024

  15. [23]

    B. D. McKay, Subgraphs of random graphs with specified degrees, Congressus Numerantium 33 (1981), 213–223

    1981

  16. [24]

    B. D. McKay,Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combinatoria 19 (1985), 15–25

    1985

  17. [25]

    B. D. McKay and N. C. Wormald,Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2), Combinatorica11 (1991), no. 4, 369–382

    1991

  18. [26]

    M. S. O. Molloy, H. Robalewska, R. W. Robinson, and N. C. Wormald,1-factorizations of random regular graphs, Random Structures and Algorithms10 (1997), no. 3, 305–321

    1997

  19. [27]

    H. D. Robalewska,2-factors in random regular graphs, J. Graph Theory23 (1996), no. 3, 215–224

    1996

  20. [28]

    N. C. Wormald,Models of random regular graphs, London Mathematical Society lecture note series (1999), 239–298. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge, CB3 0W A, United Kingdom Email address: lh569@cam.ac.uk Institute of ...

    1999

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.