{"id":"75ea37aa-2ed9-498f-9335-d8f9c6cb223d","arxiv_id":"2505.22875","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For many pairs of degrees, the random lower-degree regular graph can be embedded inside the random higher-degree regular graph with high probability, and unions of random regular graphs can mimic a single random regular graph.","lead":"Random regular graphs are models where every vertex has the same number of connections, and this paper studies when a random one with fewer connections can be placed inside a random one with more connections. It proves this nesting works for a wide range of degrees, and that certain random graph unions are statistically indistinguishable from single random graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Proposition 3.8 implicitly relies on an exact leading coefficient for Cov(X,Y) that Claim 3.3(1) states only as a big-O; without that coefficient Proposition 3.1's d^-1.1 bound is not established, so Corollary 3.2 and the main theorems lack support.","rationale":"The reader's verdict is CONDITIONAL, and I agree with that assessment. The central claim of the paper requires a coupling with probability 1-o(1), and the main technical lever is the d^{-1.1} total-variation bound of Corollary 3.2. The paper has real independent content: the direct-sum transfer lemmas (Proposition 2.8 and Corollary 2.9) are proved carefully from McKay's enumeration theorem, and the alternative sampling procedure of Section 5 is a nontrivial construction. However, Proposition 3.8's use of Claim 3.3(1) is not justified by the text: the big-O covariance bound is too weak to force the required cancellation, and the exact expansion is never stated. This is a repair-to-proof gap rather than a demonstrated false theorem, because the needed expansion is plausibly present in the cited Gao paper. The concrete check above will settle whether the concern lands; until then, conditional acceptance is the right verdict, and my read does not change the reader's verdict.","tokens_in":24535,"tokens_out":19602,"duration_ms":204025,"concrete_test":"Independently extract the full asymptotic for Cov(X,Y) from [6, Theorem 10] and check whether it has the form Cov(X,Y) = (d^{-3} + O(d^{-4} + d/n)) E[X]E[Y] with leading coefficient exactly 1. Then re-derive equation (18) and Proposition 3.8 from that statement. If the leading coefficient differs from 1, or the error term is coarser than O(d^{-4} + d/n), recompute the Chebyshev bound in Proposition 3.1; a Var[Y - Y*] of order E[Y]^2/d^3 gives only O(d^{-0.8}) and Corollary 3.2 loses the summability on which Theorems 1.4, 1.5 and the d2 <= (log n)^8 case of Theorem 1.2 depend.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All main theorems route through Corollary 3.2, which is derived from Proposition 3.1. In the proof of Proposition 3.1, Chebyshev's inequality is applied to Y - Y* with threshold d^{-1.1}E[Y]/2, so Proposition 3.8 must give Var[Y - Y*] = O(E[Y]^2/d^4). Equation (18) obtains this only by substituting Cov(X,Y) = (d^{-3} + O(d^{-4} + d/n)) E[X]E[Y]. But Claim 3.3(1), attributed to [6, Theorem 10], states only Cov(X,Y) = O(E[X]E[Y]/d^3). From the weaker bound alone, Var[Y*] = Cov(X,Y)^2/Var[X] is only O(E[Y]^2/d^3), and subtracting the leading term Var[Y] ~ E[Y]^2/(6d^3) need not leave O(E[Y]^2/d^4). If the leading covariance coefficient is not exactly 1, a term of order E[Y]^2/d^3 remains; the best tail bound for |Y - E[Y]| >= d^{-1.1}E[Y] is then O(d^{-0.8}), not O(d^{-1.1}). That weaker exponent is not summable in the telescoping sums used in Theorems 1.4 and 1.5, nor in equations (26) and (27) for d2 <= (log n)^8. As written, Proposition 3.1 is therefore unsupported, and the correctness of Theorem 1.2 in the d2 <= (log n)^8 regime, together with Theorems 1.4 and 1.5, depends on an exact covariance expansion that is not stated in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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}.","tokens_in":24803,"tokens_out":15923,"duration_ms":161117,"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":[{"comment":"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.","section":"Section 3, Proposition 3.8, Eq. (18)"}],"minor_comments":[{"comment":"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.","section":"Lemma 5.3"},{"comment":"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.","section":"Corollary 3.2"},{"comment":"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.","section":"Section 6, proof of Theorem 1.2"},{"comment":"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.","section":"Lemma 2.10"}],"recommendation":"major_revision","confidential_remarks":"The covariance gap is the only obstacle I see to the central claims; it is likely fixable by quoting or deriving the precise expansion from Gao's work, which the paper already cites. If the authors can confirm the leading coefficient and adjust Claim 3.3 or Proposition 3.8 accordingly, the paper would be a solid contribution. The self-citation [11] is not used as evidence, so I do not see a circularity concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a substantial paper and the main theorem is genuinely new: it confirms the Gao–Isaev–McKay monotonicity conjecture for all constant d1 ≥ 3 and slowly growing d1 up to n^{1/7}/log n, a regime nobody had touched. Theorems 1.4 and 1.5 are also new, and the tools — the TV-transfer lemma under direct sums (Proposition 2.8) and the alternative sampling procedure of Section 5 — are useful beyond these applications. I came away believing the high-level architecture is sound and the overall result is likely true.\n\nThe soft spot is exactly where the reader flagged it. Proposition 3.8 computes Var[Y*] = Cov(X,Y)^2/Var[X] and needs the leading coefficient of Cov(X,Y) to be exactly d^{-3} in order to cancel the leading Var[Y] term and get the O(E[Y]^2/d^4) bound. But Claim 3.3(1), as stated, gives only Cov(X,Y) = O(E[X]E[Y]/d^3). The big-O does not carry the coefficient information that the subsequent algebra uses. Without a precise statement of the asymptotic expansion, the proof of Proposition 3.1 is incomplete, and Corollary 3.2 together with Theorems 1.4 and 1.5 are unsupported. This is a presentation gap, not necessarily a mathematical error: Gao's paper likely contains the sharper covariance expansion, and the fix may be as simple as restating and citing it precisely. But as it stands, the preprint has a load-bearing missing reference.\n\nThe rest of the paper is careful and detailed. The moment computations for triangle counts are honest, the contiguity arguments are standard but applied cleanly, and the self-citation to the forthcoming Itai–Zehavi work is not used as evidence anywhere. The proofs are long but well-organized, and the level of dependence on external results is clearly acknowledged.\n\nWho should read this: anyone working on random regular graphs, sandwiching, or coupling problems for combinatorial structures. It deserves a serious referee — the result is important enough, and the gap is local enough, that the paper should go to review with a request to fix the covariance statement. I would send it out, with a note to the authors to either prove the exact coefficient or quote it verbatim from Gao's Theorem 10.","headline":"Strong paper with a real but fixable presentation gap in the covariance estimate that Proposition 3.8 relies on.","tokens_in":25537,"tokens_out":1320,"would_cite":true,"duration_ms":16821,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C70","05C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"For many degrees, sparse random regular graphs nest inside denser ones","keywords":["random regular graphs","monotone coupling","graph decomposition","perfect matchings","total variation distance","contiguity","sprinkling","triangles"],"falsifier":"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.","tokens_in":24183,"feed_emoji":"🕸️","tokens_out":14145,"duration_ms":131378,"temperature":0.7,"pith_summary":"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.","feed_headline":"For many degrees, sparse random regular graphs nest inside denser ones","feed_subtitle":"New couplings make the sparser graph a subgraph of the denser one with probability tending to 1, for a wide degree range.","key_machinery":"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})$.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the base estimates for the number of perfect matchings and the high-degree nesting range used at the start of Theorem 1.2's proof","marker":"[6]"},{"why":"provides the triangle-count variance and edge-exposure probability estimates used in Lemma 3.5 and Theorem 3.4","marker":"[7]"},{"why":"establishes the dense sandwiching regime $d \\ge (\\log n)^4$ that supplies the large-degree starting point","marker":"[8]"},{"why":"states the monotone-coupling conjecture (Conjecture 1.1) whose new regime Theorem 1.2 confirms","marker":"[9]"},{"why":"states the decomposition conjecture (Conjecture 1.3) and supplies the bipartite-degree coupling lemma used to derive the total-variation bound","marker":"[12]"},{"why":"introduces the orthogonal decomposition and projection method used to approximate the number of perfect matchings by a linear function of the triangle count","marker":"[13]"},{"why":"provides the asymptotic enumeration of graphs with prescribed sparse degree sequence inside a sparse host graph, used repeatedly to control the disjoint-union operation","marker":"[24]"},{"why":"supplies the contiguity result for unions of fixed-regular graphs and the random regular model, used in the transfer arguments","marker":"[28]"},{"why":"supplies the coupling lemma that realises total-variation closeness as agreement of two samples with controlled independence structure","marker":"[2]"}],"fun_headline_variants":["Random regular graphs nest for wide degree ranges","Sparse random regular graphs embed in denser ones","Coupling shows random d1-regular is subgraph of d2-regular","Monotonicity confirmed for random regular graphs","New proof: random regular graphs are monotone in degree"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random regular graphs nest for wide degree ranges","Sparse random regular graphs embed in denser ones","Coupling shows random d1-regular is subgraph of d2-regular","Monotonicity confirmed for random regular graphs","New proof: random regular graphs are monotone in degree"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1570,"prompt_tokens":1047,"completion_tokens":523,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":663,"completion_tokens_details":{"reasoning_tokens":443}},"tokens_in":663,"tokens_out":523,"duration_ms":6033,"temperature":1.0,"reasoning_tokens":443,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:00:33.509817+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gao, The number of perfect matchings, and the nesting properties, of random regular graphs, Random Structures and Algorithms62 (2023), no","cited_arxiv_id":null,"evidence_quote":"supplies the base estimates for the number of perfect matchings and the high-degree nesting range used at the start of Theorem 1.2's proof"},{"cited_title":"Isaev, B","cited_arxiv_id":null,"evidence_quote":"states the decomposition conjecture (Conjecture 1.3) and supplies the bipartite-degree coupling lemma used to derive the total-variation bound"},{"cited_title":"Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, Memoirs of the American Mathematical Society111 (1994), no","cited_arxiv_id":null,"evidence_quote":"introduces the orthogonal decomposition and projection method used to approximate the number of perfect matchings by a linear function of the triangle count"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the asymptotic enumeration of graphs with prescribed sparse degree sequence inside a sparse host graph, used repeatedly to control the disjoint-union operation"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the contiguity result for unions of fixed-regular graphs and the random regular model, used in the transfer arguments"},{"cited_title":"Den Hollander, Probability theory: The coupling method, 2012, Lecture notes available online (https://prob.math.leidenuniv.nl/lecturenotes/CouplingLectures.pdf)","cited_arxiv_id":null,"evidence_quote":"supplies the coupling lemma that realises total-variation closeness as agreement of two samples with controlled independence structure"}],"review_version":1}