Irregular subgraph in a regular graph

Hehui Wu; Quanyu Tang; Tianyue Cao

arxiv: 2607.06465 · v1 · pith:ETKYJLAL · submitted 2026-07-07 · math.CO

Irregular subgraph in a regular graph

Tianyue Cao , Quanyu Tang , Hehui Wu This is my paper

Reviewed by Pith2026-07-08 04:44 UTCglm-5.2pith:ETKYJLAL open to challenge →

classification math.CO MSC 05C0705D4005C35

keywords Alon–Wei conjecturedegree distributionspanning subgraphthreshold random graphanti-diagonal lattice reductionedge-atom estimateprobabilistic methodregular graph

0 comments

The pith

Exact degree distributions realized in regular graphs

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

The paper proves that every sufficiently large d-regular graph admits a spanning subgraph whose degree-count vector matches any prescribed target, subject only to the constraints that the counts sum to n, the handshaking parity condition holds, and each count lies within 1 of n/(d+1). This resolves the Alon–Wei conjecture exactly (with additive error 1 rather than 2) for all fixed d when n is large enough, and more precisely for d up to n^{1/12−ε}. The proof starts from a threshold random subgraph where each vertex degree is uniformly distributed on {0,…,d}, then corrects the discrepancy to the target vector using single-edge additions and deletions restricted to two anti-diagonal degree-pair types. A lattice lemma shows these moves suffice to express any valid discrepancy, and a uniform edge-atom estimate of order d^{−4} guarantees enough candidate edges of each type for a greedy vertex-disjoint selection to complete the correction.

Core claim

The central mechanism is the restriction of all corrective edge moves to the two anti-diagonals a+b=d−2 and a+b=d−1 in the degree-pair space. This restriction is what bridges the algebraic task (expressing the discrepancy as an integer combination of move vectors) with the probabilistic task (finding enough candidate edges): the natural label points for these degree pairs lie near the threshold line x+y=1, so small rectangles on both sides of the line supply both addable non-edges and deletable edges. The cost of the lattice representation is controlled not by a coarse norm but by a twofold prefix norm whose expectation under the threshold model is O(d²√n), while the supply of each signed类型是

What carries the argument

Three components: (1) a threshold random subgraph H₀ defined by X_u + X_v ≥ 1 for independent uniform labels X_v, giving each vertex a degree uniformly distributed on {0,…,d}; (2) an anti-diagonal lattice lemma showing any valid discrepancy vector z ∈ L_d can be written as an integer combination of move vectors β_{a,b} with a+b ∈ {d−2, d−1}, with total coefficient cost bounded by a prefix-norm expression; (3) a uniform edge-atom estimate (Lemma 3.4) giving a d^{−4} lower bound on the probability that any fixed edge is a candidate of any required signed type, which drives the supply of order nd^{−3} per type and must exceed the demand of order d³√n — this comparison yields the range d ≤ n^{1/

If this is right

The exact realization result (additive error 1) is stronger than what the Alon–Wei conjecture asks (additive error 2), so the conjecture is resolved in the polynomial range d ≤ n^{1/12−ε}.
The anti-diagonal restriction means only two degree-pair families are needed for correction, suggesting that the full set of possible move types is redundant — the lattice structure of L_d is generated by a sparse subset.
The greedy vertex-disjoint selection succeeds whenever supply (nd^{−3}) dominates demand (d³√n), i.e., d⁶√n ≪ n, giving the exponent 1/12 as the natural threshold where d⁶ ≤ n^{1/2−ε}.
The result is complementary to the asymptotic resolution by Montgomery, Pokrovskiy and Sudakov for d = o(n): that work gives (1+o(1))n/(d+1) in the full range, while this work gives exact counts in a narrower range.

Where Pith is reading between the lines

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

The exponent 1/12 is not intrinsic to the Alon–Wei problem but is an artifact of the supply-vs-demand comparison d⁶√n ≪ n. Any improvement to the edge-atom estimate (beyond d^{−4}) or to the discrepancy bound (beyond d²√n) would widen the range, so the bottleneck is local probability estimation rather than global structure.
If the edge-atom estimate could be sharpened to d^{−3} (one factor of d better), the range would extend to d ≤ n^{1/8−ε}; if the discrepancy norm could be reduced to d√n, the range would extend to d ≤ n^{1/10−ε}. The current bound sits at the intersection of both limitations.
The anti-diagonal lattice lemma is purely deterministic and may apply to other degree-distribution realization problems beyond the Alon–Wei setting, wherever the target vector satisfies the same lattice constraints.

Load-bearing premise

The greedy correction step requires that the supply of candidate edges of each type (at least c·n·d^{−3}) exceeds the number blocked by previously selected edges (at most C·d³·√n). This holds when d ≤ n^{1/12−ε}, and the entire argument depends on the uniform edge-atom estimate giving the d^{−4} probability lower bound that drives the supply.

What would settle it

Find a d-regular graph in the stated range where the threshold random subgraph has a degree-count discrepancy whose prefix-norm exceeds C·d²√n with probability bounded away from zero, or where the edge-atom probability for some anti-diagonal type is o(d^{−4}) due to local graph structure (e.g., dense common-neighborhood patterns that force the conditional binomial variances into degenerate regimes).

read the original abstract

A conjecture of Alon and Wei states that, for any $d$-regular graph $G$ with $n$ vertices, there exists a spanning subgraph $H$ such that for all $0\le i\le d$, we have $m(H, i)$, the number of vertices in $H$ with degree $i$, is between $\frac{n}{d+1}-2$ and $\frac{n}{d+1}+2$. We prove the conjecture for all fixed $d$ when $n$ is sufficiently large. More precisely, if $q=(q_0,\ldots,q_d)$ satisfies $$ \sum_{i=0}^d q_i=n,\qquad \sum_{i=0}^d i q_i\equiv 0\pmod 2,\qquad \left|q_i-\frac{n}{d+1}\right|\le 1 \quad (0\le i\le d), $$ then there is a spanning subgraph $H\subseteq G$ such that $$ m(H,i)=q_i \qquad (0\le i\le d). $$

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.

Desk Editor's Note private letter to a colleague

Solid paper proving exact Alon–Wei for polynomial-degree graphs; deserves careful refereeing, mainly to verify the compactness case analysis in Lemma 3.2.

read the letter

This paper proves that every admissible degree-count vector (subject to total-size and parity constraints) can be exactly realized as the degree distribution of a spanning subgraph, for d-regular graphs with d ≤ n^{1/12−ε}. This is stronger than the Alon–Wei conjecture, which only asks for additive error 2, and it's complementary to the Montgomery–Pokrovskiy–Sudakov result which gets asymptotic counts in the full range d = o(n) but not exact ones. The exact realization in a polynomial range is genuinely new. The anti-diagonal lattice lemma (Lemma 4.1) is a clean idea: restrict corrections to edge types on a+b = d−2 and a+b = d−1, which keeps you near the threshold line where supply is plentiful. The twofold prefix norm that controls correction cost is also novel and well-motivated. The proof architecture — probabilistic initialization, deterministic lattice correction, greedy vertex-disjoint matching — is clear and the pieces fit together honestly. The supply/demand arithmetic is transparent: supply is Ω(nd^{−3}), demand is O(d²√n), blocking is O(d³√n), and the range d ≤ n^{1/12−ε} is exactly where these separate. The soft spot is Lemma 3.2 part 2, the threshold-convolution estimate. Its proof is by compactness-by-contradiction with several boundary regimes (α = 0, α = 1/2 with τ = 1). I worked through these cases and they appear correct — the Poisson convergence arguments in each degenerate regime do yield positive limits, contradicting the hypothesis. But this is the kind of argument where a referee should check every sub-case carefully, because a missed boundary configuration could silently break the d^{−4} edge-atom bound, which is load-bearing for the entire supply chain. The reader flagged this as the reason for CONDITIONAL; I agree it warrants scrutiny but I don't think it's likely to be wrong — the case structure is complete and the limiting arguments are standard. One minor point: the range restriction is far from d = o(n), but the paper is upfront about this and doesn't oversell. The result stands on its own as an exact theorem in a nontrivial range. This is for combinatorial probabilists and anyone working on degree distribution problems. It deserves a serious referee — the ideas are original, the execution is careful, and the main risk is concentrated in one lemma that a good referee can verify in a reasonable time. I'd recommend sending it out for review.

Referee Report

0 major / 1 minor

Summary. This paper proves an exact version of the Alon–Wei conjecture on irregular subgraphs of regular graphs. For every fixed $d$ and sufficiently large $n$, the authors show that for any $d$-regular graph $G$ on $n$ vertices with $d$ up to $n^{1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1

Significance. This paper makes a strong contribution to the study of irregular subgraphs. While the asymptotic version of the Alon–Wei conjecture was recently settled by Montgomery, Pokrovskiy, and Sudakov for $d=o(n)$, this work achieves an exact realization of the degree-count vector (up to the unavoidable parity constraint) in the polynomial range $d$ up to $n^{1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/

minor comments (1)

The abstract states the result is proved for 'all fixed d when n is sufficiently large,' but the formal statement (Theorem 2.1) allows d to grow as $d$ up to $n^{1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/12-1/1

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. The referee's report appears to have been affected by a rendering issue (the exponent in the range d ≤ n^{1/12−ε} was repeated many times), but the substantive assessment—that the paper proves an exact version of the Alon–Wei conjecture in the polynomial range d ≤ n^{1/12−ε}, complementary to the asymptotic result of Montgomery, Pokrovskiy, and Sudakov—is accurate. We address the report below.

read point-by-point responses

Referee: The referee's report contains no specific major comments; the 'MAJOR COMMENTS' section is empty. The referee's summary and significance assessment are accurate, and the recommendation is minor revision.

Authors: We thank the referee for the accurate summary and the positive assessment. Since no specific revision requests were made, we have reviewed the manuscript carefully for any minor issues that should be addressed before final publication. We will make the following small improvements in the revised version: (1) In the proof of Lemma 3.2, part (2), the notation c* is introduced as 'an integer such that' certain conditions hold, but it would be clearer to state explicitly that c* is chosen as the mode of the hypergeometric distribution from part (3), applied with the appropriate parameters. (2) In Section 2.1, the phrase 'the natural label point (a/(d−1), b/(d−1))' could be clarified by noting that this is the point where the binomial degree distributions of the two endpoints are centered at a and b respectively. (3) We will add a brief remark after Theorem 2.1 noting that the constant 1/12 in the exponent arises from the comparison between the supply bound c_S n d^{−3} and the demand bound C d^3 √n, specifically from requiring n d^{−3} ≫ d^3 √n, i.e., n ≫ d^{12}. These are purely expository changes; no mathematical content is altered. revision: partial

Circularity Check

0 steps flagged

No circularity found; the derivation is self-contained with no fitted parameters or self-citation chains.

full rationale

The paper proves Theorem 2.1 via a self-contained chain: (1) Lemma 3.4 provides a uniform edge-atom lower bound c_at * d^{-4} using a compactness-by-contradiction argument over binomial/hypergeometric point probabilities, with all distributional facts (Bin, hypergeometric, Poisson approximation) derived from first principles or standard external results (Le Cam, Auld–Neammanee). (2) Lemma 4.1 reduces the lattice L_d to anti-diagonal generators with a controlled prefix-norm cost, proved by explicit algebraic manipulation of the generators A_i, B_i. (3) Lemma 5.1 bounds the expected refined discrepancy using Efron–Stein (cited from Boucheron–Lugosi–Massart, an external source). (4) Lemma 5.2 uses Chebyshev with a dependency-graph second moment to get simultaneous supply. (5) Section 6 combines supply (c_S * n * d^{-3}) against demand (C * d^2 * sqrt(n)) via greedy vertex-disjoint selection. No step is defined in terms of its output. No parameter is fitted to data and then 'predicted.' The constants c_at, c_S, C_R, C_L are absolute constants arising from proofs, not fitted values. The threshold model and uniform degree distribution (Eq. 28) are standard facts computed from scratch. The only self-reference is Remark 2.2 noting temporal priority over [9], which is not load-bearing for any proof step. The derivation chain is genuinely independent of its conclusion.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

No new entities are postulated. The proof uses standard probabilistic and combinatorial tools. The threshold random subgraph model is from prior work. The anti-diagonal restriction and prefix norm are proof techniques, not new mathematical objects requiring independent evidence.

free parameters (2)

ε (epsilon) = arbitrary fixed positive
Controls the range d ≤ n^{1/12-ε}. Not fitted to data; any fixed ε > 0 works.
n_0(ε) = sufficiently large (existential)
Threshold for n beyond which the asymptotic estimates hold. Not explicitly computed.

axioms (5)

standard math Bounded-differences form of Efron–Stein inequality [3, Corollary 3.2]
Used in Lemma 5.1 to bound Var(P_j(M)) and Var(S(M)). Standard concentration inequality.
standard math Le Cam total-variation Poisson approximation
Used in Lemma 3.1(5) and the compactness proof of Lemma 3.2. Standard tool.
standard math Local CLT for Poisson-binomial variables [2, Theorem 1.2]
Used in Lemma 3.1(4) to approximate point probabilities of sums of independent Bernoullis.
standard math Chebyshev's inequality
Used in Lemma 5.2 for the second-moment supply bound.
standard math Markov's inequality
Used in Section 6 to bound R_0.

pith-pipeline@v1.1.0-glm · 17472 in / 2607 out tokens · 432892 ms · 2026-07-08T04:44:36.004616+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · 1 internal anchor

[1]

Alon and F

N. Alon and F. Wei, Irregular subgraphs,Combinatorics, Probability and Computing32(2023), 269–283

work page 2023
[2]

Auld and K

G. Auld and K. Neammanee, Explicit constants in the nonuniform local limit theorem for Poisson-binomial random variables,Journal of Inequalities and Applications2024, Article 67 (2024)

work page 2024
[3]

Boucheron, G

S. Boucheron, G. Lugosi and P. Massart,Concentration Inequalities: A Nonasymptotic Theory of Inde- pendence, Oxford University Press, 2013

work page 2013
[4]

J. Fox, S. Luo and H. T. Pham, On random irregular subgraphs,Random Structures & Algorithms64 (2024), 899–917

work page 2024
[5]

Frieze, R

A. Frieze, R. J. Gould, M. Karoński and F. Pfender, On graph irregularity strength,Journal of Graph Theory41(2002), 120–137

work page 2002
[6]

Le Cam, An approximation theorem for the Poisson-binomial distribution,Pacific Journal of Mathe- matics10(1960), 1181–1197

L. Le Cam, An approximation theorem for the Poisson-binomial distribution,Pacific Journal of Mathe- matics10(1960), 1181–1197

work page 1960
[7]

Lužar, J

B. Lužar, J. Przybyło and R. Soták, Degree-balanced decompositions of cubic graphs,European Journal of Combinatorics128(2025), Article 104169

work page 2025
[8]

Ma and S

J. Ma and S. Xie, Finding irregular subgraphs via local adjustments,Journal of Combinatorial Theory, Series B174(2025), 71–98

work page 2025
[9]

Nearly-uniform degree distributions in spanning subgraphs

R. Montgomery, A. Pokrovskiy and B. Sudakov, Nearly-uniform degree distributions in spanning sub- graphs, arXiv:2606.30612, 2026. School of Mathematical Sciences, Fudan University, Shanghai 200433, P. R. China Email address:cao_tianyue@hotmail.com School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, P. R. China Email address:tang...

work page internal anchor Pith review Pith/arXiv arXiv 2026

[1] [1]

Alon and F

N. Alon and F. Wei, Irregular subgraphs,Combinatorics, Probability and Computing32(2023), 269–283

work page 2023

[2] [2]

Auld and K

G. Auld and K. Neammanee, Explicit constants in the nonuniform local limit theorem for Poisson-binomial random variables,Journal of Inequalities and Applications2024, Article 67 (2024)

work page 2024

[3] [3]

Boucheron, G

S. Boucheron, G. Lugosi and P. Massart,Concentration Inequalities: A Nonasymptotic Theory of Inde- pendence, Oxford University Press, 2013

work page 2013

[4] [4]

J. Fox, S. Luo and H. T. Pham, On random irregular subgraphs,Random Structures & Algorithms64 (2024), 899–917

work page 2024

[5] [5]

Frieze, R

A. Frieze, R. J. Gould, M. Karoński and F. Pfender, On graph irregularity strength,Journal of Graph Theory41(2002), 120–137

work page 2002

[6] [6]

Le Cam, An approximation theorem for the Poisson-binomial distribution,Pacific Journal of Mathe- matics10(1960), 1181–1197

L. Le Cam, An approximation theorem for the Poisson-binomial distribution,Pacific Journal of Mathe- matics10(1960), 1181–1197

work page 1960

[7] [7]

Lužar, J

B. Lužar, J. Przybyło and R. Soták, Degree-balanced decompositions of cubic graphs,European Journal of Combinatorics128(2025), Article 104169

work page 2025

[8] [8]

Ma and S

J. Ma and S. Xie, Finding irregular subgraphs via local adjustments,Journal of Combinatorial Theory, Series B174(2025), 71–98

work page 2025

[9] [9]

Nearly-uniform degree distributions in spanning subgraphs

R. Montgomery, A. Pokrovskiy and B. Sudakov, Nearly-uniform degree distributions in spanning sub- graphs, arXiv:2606.30612, 2026. School of Mathematical Sciences, Fudan University, Shanghai 200433, P. R. China Email address:cao_tianyue@hotmail.com School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, P. R. China Email address:tang...

work page internal anchor Pith review Pith/arXiv arXiv 2026