REVIEW 1 major objections 4 minor 9 references
Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties
T0 review · 1 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read Every degree-sequence graph property is testable.
desk verdict A genuinely new structural result — ℓ1-closeness of degree sequences implies O(√δ n²) edit-distance closeness — yields a clean proof that every degree-sequence property is testable with poly(1/ε) queries; the only real flaw is a fixable rounding omission in Lemma 3.1. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object in the first theorem is the red/blue symmetric-difference graph $F$ between the input graph $G$ and a nearest graph $G'$ with the target degree sequence. An alternating cycle in a 2-edge-coloured graph is an even cycle whose edge colours alternate; if $F$ had one, the minimality of $G'$ would be contradicted by swapping the colours along the cycle. Lemma 2.3, proved by partitioning the vertices into $k=\delta^{-1/2}$ consecutive intervals and using a vertex ordering forced by the absence of alternating cycles, bounds such an $F$ by $O(\delta^{1/2}n^2)$ edges. In the testing half, the machinery is a degree statistic $\alpha=(\alpha_1,\dots,\alpha_k)$, a list of nonnegative proportions summing to 1, whose associated sequence $d(n,\alpha)$ has $\alpha_\ell n$ entries equal to $\frac{2\ell-1}{2k}n$. A sampling algorithm finds a statistic $\delta$-approximating $G$ with high probability, and the decision problem for $D$ against $d(n,\alpha)$ becomes the tester's final step.
What would settle it
Construct a family of 2-edge-coloured graphs on $n$ vertices with no alternating cycle, with red/blue degree discrepancy at most $\delta n^2$, and with more than $C\sqrt{\delta}\,n^2$ edges for a constant $C$ whose value tends to infinity with the family. No such family can exist if Lemma 2.3 is true, so it would refute the proof of Theorem 1.1.
Extended reading notes
Core claim
Let $d=(d_1,\dots,d_n)$ be a realizable degree sequence and suppose $\sum_{i=1}^n |d_G(i)-d_i|\le \delta n^2$. Theorem 1.1 states that, for $n\ge \delta^{-2}$, there is a graph $G'$ with $d_{G'}(i)=d_i$ for every $i$ and with $|E(G')\triangle E(G)|=O(\delta^{1/2}n^2)$. The proof chooses, among all graphs with degree sequence $d$, one $G'$ minimizing the symmetric difference with $G$, and colours the edges of $F=E(G')\triangle E(G)$ red if they are in $G'$ and blue if they are in $G$. The central observation is that $F$ contains no alternating cycle: switching the colours along such a cycle would preserve all degrees and strictly reduce $|E(G')\triangle E(G)|$. Lemma 2.3 then shows that an alternating-cycle-free 2-edge-coloured graph with red/blue degree discrepancy at most $\delta n^2$ has only $O(\delta^{1/2}n^2)$ edges. The paper then turns this into Theorem 1.2: approximating the degree sequence of $G$ by a sampled degree statistic, and using the robustness theorem, gives a tester for any degree-sequence property with $q(\varepsilon)=\mathrm{poly}(1/\varepsilon)$ queries.
Load-bearing premise
The proof of Lemma 3.1 assumes that the quantities $n/(2k)$ and $\alpha_\ell n$ are integers when it builds the approximating degree statistic; for arbitrary $n$ a rounding argument is needed, and the paper does not spell it out.
Editorial extensions
If this is right
- Any degree-sequence property can be tested with $\mathrm{poly}(1/\varepsilon)$ edge queries; query complexity does not grow with the input size.
- A graph $\varepsilon$-far from a degree-sequence property cannot have a sampled degree statistic that is too close to the property, because Theorem 1.1 would convert that closeness into edit distance.
- Known testability of $r$-regularity falls out as a special case; for degree sequences with only constantly many distinct values, the tester can also run in time independent of $n$.
- The quadratic-to-square-root conversion in Theorem 1.1 is the engine behind the polynomial query bound; any improved conversion would improve the tester's dependence on $\varepsilon$.
Reading between the lines
- Editorial inference: the alternating-cycle technique should transfer to directed degree sequences by substituting the directed alternating-cycle analogue the paper mentions, yielding the same robustness for directed graphs.
- Editorial inference: the $\varepsilon^{-16}$ query exponent is an artifact of the $\delta^{1/2}$ conversion and the $\delta\approx \varepsilon^2$ choice; improving Theorem 1.1 to a linear bound would reduce the exponent substantially.
- Editorial inference: for applications, the bottleneck is the decision oracle $A$; finding broad families of degree-sequence properties for which $A$ is fast in $1/\varepsilon$ and $\log n$ is the natural next problem, since query complexity alone no longer limits the tester.
Formalized claims in Lean
-
Claim #1: Let $d=(d_1,\dots,d_n)$ be a realizable degree sequence and suppose $\sum_{i=1}^n |d_G(i)-d_i|\le \delta n^2$. Theorem 1.1 states that, for $n\ge \delta^{-2}$, there is a graph $G'$ with $d_{G'}(i)=d_i$ for every $i$ and with $|E(G')\triangle E(G)|=O(\delta^{1/2}n^2)$. The proof chooses, among all graphs with degree sequence $d$, one $G'$ minimizing the symmetric difference with $G$, and colours t
/-- @claim 1 Let $d=(d_1,\dots,d_n)$ be a realizable degree sequence and suppose $\sum_{i=1}^n |d_G(i)-d_i|\le \delta n^2$. Theorem 1.1 states that, for $n\ge \delta^{-2}$, there is a graph $G'$ with $d_{G'}(i)=d_i$ for every $i$ and with $|E(G')\triangle E(G)|=O(\delta^{1/2}n^2)$. The proof chooses, among all graphs with degree sequence $d$, one $G'$ minimizing the symmetric difference with $G$, and colours t -/ def central_claim : Prop :=
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the relationship between the normalized ℓ1-distance of degree sequences and the normalized edit distance of graphs. Theorem 1.1 states that if an n-vertex graph G has degree sequence within ℓ1-distance δ of a realizable sequence d, then G is within O(δ^{1/2}) edit distance of some graph with degree sequence d, provided n ≥ δ^{-2}. The proof colors the symmetric difference between G and a closest graph G' with the target degree sequence red and blue, shows that no alternating cycle exists in this 2-edge-coloured graph, and then bounds the number of edges of the symmetric difference via an interval-partition argument (Lemma 2.3). As an application, the paper proves (Theorem 1.2 / Theorem 3.2) that every graph property defined by a degree-sequence property is testable in the dense graph model with query complexity poly(1/ε), by approximating the degree sequence through sampling (Lemma 3.1) and then invoking a decision oracle for the property on the approximate degree statistic.
Significance. The results are significant and natural. Theorem 1.1 is a general robustness statement for degree sequences, previously known only for regular sequences, and its proof is elegant and self-contained, using the Grossman–Haggkvist alternating-cycle theorem and a clean interval-partition argument. Theorem 1.2 is a broad testability result: it shows that a large class of natural graph properties, namely all degree-sequence properties, is testable with query complexity independent of n. The paper is honest about the caveat that the running time of the resulting tester may depend on n, even exponentially, and it identifies the open problem of linear dependence in Theorem 1.1 and the question of time-efficient testers for general families. The proof of Theorem 1.1 is rigorous and the reduction to testing via statistical estimation is conceptually clear.
major comments (1)
- [Section 3, definition of d(n,α) and proof of Lemma 3.1] The proof of Lemma 3.1 assumes, as stated in the definition of d(n,α), that n/(2k) and α_i n are integers. This assumption is not valid for arbitrary n: the algorithm outputs α_i = c_i/s, so α_i n is generally not integral, and the target degrees (2ℓ-1)n/(2k) are not necessarily integral either. Consequently d(n,α) may not be an integer sequence, the sets A_ℓ defined in the proof are not well-defined subsets of [n] when their boundaries are not integers, and the bound |Z| ≤ 2kγ n can be off by O(k), adding an O(kn) term to the computed ℓ1 error. The final inequality (1/(2k)+(2k+1)γ)n^2 ≤ δn^2 has no slack when k=ceil(1/δ) and δ=1/k, so this additive error is not absorbed. Since Theorem 3.2 applies Lemma 3.1 to arbitrary n, the proof of the tester's correctness is incomplete as written. The gap appears fixable by taking k=ceil(C/δ) for a sufficiently large absolute constant C and by rounding the α_i n counts and the interval boundaries in A_ℓ to integers while preserving the δ-approximation, but the rounding argument must be written out in full.
minor comments (4)
- [Title and abstract] The title and abstract contain typos: 'Testablity' should be 'Testability', 'De gree' should be 'Degree', and 'independe nt' should be 'independent'; in the introduction, 'efficietly' should be 'efficiently'.
- [Proof of Lemma 3.1] In the proof of Lemma 3.1, the displayed sum uses '∑_{ℓ=1}^k |A_i|'; this should be '∑_{ℓ=1}^k |A_ℓ|' for consistency with the definition of the sets.
- [Lemma 2.3] In Lemma 2.3, k=δ^{-1/2} is used as the number of intervals, but k and n/k may not be integers; a remark that floors and ceilings can be used without affecting the asymptotic bounds would avoid a similar, though more benign, rounding issue.
- [Section 3, degree statistic definition] In the definition of degree statistic, the notation 'αℓn' and 'α1n,...,αkn' lacks spacing; it should read 'α_ℓ n' and 'α_i n'.
Circularity Check
No circularity: the derivation chain is self-contained, uses external standard theorems, and contains no fitted parameters renamed as predictions.
full rationale
The paper's central derivation is not circular. Theorem 1.1 is proved from first principles using the external Grossman–Haggkvist alternating-cycle theorem (Theorem 2.1) and a counting lemma (Lemma 2.3); the proof does not assume the desired edit-distance bound or any fitted parameter. Theorem 1.2 / Theorem 3.2 is a reduction: it shows that if an algorithm A decides closeness of a bounded-size degree statistic to a degree-sequence property D, then P(D) is testable. This is an oracle reduction, not a circular invocation of the target property, and the tester's correctness follows from Theorem 1.1 and the triangle inequality. Lemma 3.1 is a standard sampling argument using Hoeffding's inequality; it estimates the degree distribution of the input graph and explicitly constructs a degree statistic. The only fragile point is the simplifying assumption that n/(2k) and α_i n are integers, which is acknowledged in the text but not resolved by an explicit rounding argument. That is a technical gap, not circularity: the missing step would preserve the δ-approximation by standard rounding, and no prediction is being forced by construction. There are no self-citations used as load-bearing evidence, no uniqueness theorem imported from the author's prior work, and no known result merely renamed. Thus the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (3)
- domain assumption Grossman-Haggkvist theorem: every 2-connected 2-edge-colored graph with both color degrees at least 1 at each vertex contains an alternating cycle.
- standard math Hoeffding's inequality for binomial random variables.
- domain assumption Dense graph model conventions for property testing, including edit distance and query access.
Cite this review
Pith. "Pith review of Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties." pith.science (2026). https://pith.science/paper/547VGH3E
@misc{pith2026200912697,
author = {Pith},
title = {Pith review of: Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties},
year = {2026},
howpublished = {\url{https://pith.science/paper/547VGH3E}},
note = {Machine review of arXiv:2009.12697}
}
abstract
We show that if the degree sequence of a graph $G$ is close in $\ell_1$-distance to a given realizable degree sequence $(d_1,\dots,d_n)$, then $G$ is close in edit distance to a graph with degree sequence $(d_1,\dots,d_n)$. We then use this result to prove that every graph property defined in terms of the degree sequence is testable in the dense graph model with query complexity independent of $n$.
Reference graph
Works this paper leans on
-
[1]
J. M. Burns, The number of degree sequences of graphs (Doc toral dissertation, Massachusetts Institute of Technology), 2007
work page 2007
-
[2]
P. Erd˝ os and T. Gallai, Graphs with prescribed degrees o f vertices, Mat. Lapok 11 (1960), 264–274 (in Hungarian)
work page 1960
-
[3]
Goldreich, Introduction to Property T esting
O. Goldreich, Introduction to Property T esting . Cambridge University Press, 2017
work page 2017
-
[4]
O. Goldreich, S. Goldwasser, and D. Ron, Property testin g and its connection to learning and approximation. J. ACM 45 (1998), 653–750
work page 1998
-
[5]
J. W. Grossman and R. H¨ aggkvist, Alternating cycles in e dge-partitioned graphs, Journal of Com- binatorial Theory, Series B, 34(1), 77–81, 1983
work page 1983
- [6]
-
[7]
S. L. Hakimi, On the realizability of a set of integers as d egrees of the vertices of a graph.” SIAM J. Appl. Math. 10, 496–506, 1962
work page 1962
-
[8]
S. L. Hakimi and E.F. Schmeichel, Graphs and their degree sequences: A survey. In Theory and applications of graphs, 225–235 (1978). Springer, Berlin, Heidelberg
work page 1978
Show all 9 references
-
[9]
Havel, A remark on the existence of finite graphs, ˇCasopis Pest
V. Havel, A remark on the existence of finite graphs, ˇCasopis Pest. Mat. 80 (1955), 477–480, (in Czech). 9
1955
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.