A quantitative container characterization of one-sided testability

Cameron Seth; Gaia Carenini; Yuichi Yoshida

REVIEW 1 major objections 4 minor 25 references

A quantitative container characterization of one-sided testability

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

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

Pith's one-line read This paper proves that, for hereditary graph properties, size-oblivious one-sided testability is quantitatively equivalent to the existence of ordered hypergraph containers, with explicit polynomial translations between query complexity and

desk verdict A genuinely new quantitative equivalence between one-sided testing and ordered containers; the main theorem is likely correct, but the size-oblivious canonicalization step is cited rather than proved and the application proofs are terse. read the letter →

arxiv 2608.01523 v1 pith:HWECUL3B submitted 2026-08-02 math.CO cs.CCcs.DS

Gaia Carenini , Cameron Seth , Yuichi Yoshida This is my paper · ORCID

classification math.COcs.CCcs.DS MSC 05C3505C6568Q1768W20

keywords one-sidedpropertytestingdensegraphmodelhypergraphcontainershereditarypropertiesorderedcontainerlemmasemi-hereditaryrandomizedalgorithmsrelationalstructures

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

The paper aims to give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, answering a question posed in earlier work. The main claim is that, for hereditary graph properties, one-sided testers with query complexity Q(epsilon) exist exactly when the property admits ordered hypergraph containers with comparable parameters: fingerprints of length O(Q(c epsilon)), containers missing $\Omega$(1/Q(c epsilon)) of the vertices, and thresholds O(Q(c epsilon)). Because the correspondence is effective in both directions, query complexity and container parameters are the same object up to explicit polynomial transformations. The result extends to all fixed finite relational signatures of bounded arity, and, via semi-hereditary envelopes, to arbitrary graph properties. If correct, container methods can serve as a regular tool for designing testers and for proving quantitative closure results such as partition properties and large induced substructures.

What carries the argument

The ordered container lemma: for a hereditary property Pi, a graph epsilon-far from Pi, and every vertex set U with G[U] in Pi, there is an ordered tuple f(U) (the fingerprint) of at most q vertices of U such that U lies in a container C(f(U)) of size at most (1-eta)n, and C is a function of f(U) alone. The construction maps the family of induced Pi-subgraphs to independent sets of a dense s-uniform hypergraph whose edges are the s-sets outside Pi; then an iterative pivot argument (Theorem 1.5) selects maximum-degree vertices in successive links, recording them in the fingerprint and discarding vertices that cannot belong to the independent set, until enough of the ambient set is removed. Th

What would settle it

For a fixed hereditary property Pi, e.g., 3-colourability, and small n, brute-force compute the minimal container size and fingerprint length achievable for every n-vertex graph that is epsilon-far from Pi, and check whether eta >= c/Q(epsilon) and q <= C Q(epsilon) hold with absolute constants; a violation would refute Theorem 1.4(i). Since the theorem is universal over properties, a single counterexample would be conclusive.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1.4: for a hereditary graph property Pi, Pi admits a size-oblivious one-sided tester with query complexity at most Q(epsilon) if and only if Pi admits an (epsilon, eta, N, q)-ordered container lemma for every epsilon, with q(epsilon)=O(Q(c epsilon)), eta(epsilon)=$\Omega$(Q(c epsilon)^{-1}), and N(epsilon)=O(Q(c epsilon)); conversely, ordered container lemmas with parameters eta,N,q yield a tester of complexity eO($N^{2}$ + (q+1)^2/$eta^{2}$). The constants c and the hidden constants are absolute. In other words, the query complexity of the simplest and most restrictive testing mode is, up to polynomials, the same as the efficiency of covering all induced Pi-subgraphs i

Load-bearing premise

The forward direction rests on the canonicalization theorem that any size-oblivious one-sided tester can be converted into a canonical one that samples only O(Q(c epsilon)) vertices after changing epsilon by a constant factor; if that conversion fails under the 'inspect the whole input on small samples' convention, the explicit container bounds q=O(Q(c epsilon)), eta=$\Omega$(1/Q(c epsilon)) would not follow.

Editorial extensions

If this is right

For any hereditary graph property, polynomial one-sided query complexity, polynomial container parameters, and polynomial removal-lemma parameters are equivalent; the qualitative characterization of hereditary one-sided testability now has a fully quantitative version.
The characterization passes to every fixed finite relational signature of bounded arity: digraphs, edge-coloured graphs, and hypergraphs are covered by the same container framework, with the same explicit translations.
Combined with semi-hereditary witnesses, the result gives a quantitative characterization of all size-oblivious one-sided testable graph properties, not just hereditary ones.
The container machinery yields new testers with explicit polynomial bounds: partition properties such as (r,s)-colourability, cochromatic number, and bounded dichromatic number, and properties asserting a linearly large induced substructure (e.g., rho-DAGs).
Inside any sufficiently large host that is epsilon-far from a hereditary property, every induced member lies in one of polynomially many containers of size (1-eta)n; this localizes induced substructures in random hosts, e.g., perfect induced subgraphs of G(n,1/2) are all contained in a few small sets.

Reading between the lines

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

If the equivalence holds at the level of absolute constants, any future improvement to container theorems (sharper eta or q) immediately produces better one-sided testers, and conversely any tester lower bound translates to a container-parameter lower bound; the paper does not itself draw this transfer principle.
The regularity-free proof suggests that a non-constructive regularity decomposition may be bypassed entirely: the same pivot argument could in principle yield quantitative container theorems in denser or sparser models where regularity lemmas have notoriously bad bounds, although the paper only treats the dense model.
The counting bound behind the converse yields an entropy-deficit statement for induced members; a testable extension is to check empirically on small graphs whether the distribution of induced members in random graphs matches the container localization, e.g., for perfect graphs.
The random-host corollary for perfect graphs is a concrete prediction: with high probability, every perfect induced subgraph of G(n,1/2) lies in a small container; a direct verification on an explicit construction or computation would test the underlying container bound.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

This paper delivers on the Alon–Fischer–Newman–Shapira question: a quantitative, two-way correspondence between one-sided testability in the dense graph model and a newly defined ordered-container parameter. The proof is elementary and regularity-free, and it extends uniformly to all bounded-arity relational signatures. That is a real and substantial step forward. The main engine, the ordered container lemma (Theorem 1.5), is a neat pivot argument that yields explicit parameters, and the reverse counting direction is clean. The applications—partition closure and linearly large induced substructures—are sensible and give concrete polynomial bounds. I also checked the citation pattern: self-citations are contextual, not load-bearing. No circularity.

The soft spots are real but localized. The forward direction of the main theorem (1.4) relies on a size-oblivious canonicalization theorem attributed to Goldreich–Trevisan. The paper states the version it needs (with the "inspect the whole input when the sample exceeds n" convention) but does not prove it, and the standard GT theorem is usually stated in the non-size-oblivious model. The stress-test is right that if that convention breaks the constant-factor canonicalization, the q=O(Q) and eta=Omega(1/Q) bounds would fail. I suspect the step is fixable—the GT argument should adapt—but a referee needs to see it written out, especially because the same step is reused for relational structures in Theorem 3.5.

The other issue is that the application proofs (Theorems 5.1 and 6.1) are terse where it matters: the "standard container-counting" arguments that bound the number of transcripts are summarized rather than shown. This is probably fillable, but it makes those parts hard to verify. It also matters because the applications are a large part of the paper's selling point.

Overall: this deserves a serious referee and a careful revision, not a desk reject. The central claim is well supported; the gaps are expositional and technical, not fundamental. I'd bring it to a reading group, and I'd cite it once the canonicalization issue is settled.

Recommendation: send it to peer review, with a request to expand the canonicalization proof and the container-counting steps.

Referee Report

1 major / 4 minor

Summary. The paper gives a quantitative container characterization of size-oblivious one-sided testability in the dense graph model. For a hereditary graph property Π, Theorem 1.4 asserts that Π admits a size-oblivious one-sided tester with query complexity Q(ε) if and only if Π admits, for every ε, an ordered container lemma with fingerprint length q=O(Q(cε)), shrinkage η=Ω(1/Q(cε)), and threshold N=O(Q(cε)); conversely, a container lemma with parameters (η,N,q) yields a tester of complexity eO(N^2+(q+1)^2/η^2). The proof factorizes through a removal–container equivalence for dense uniform hypergraphs (Theorem 2.2): an ε-far graph has many bad s-subsets, and an iterative pivot argument puts every induced Π-subgraph in a container of size at most (1−δ/s)n determined by a short ordered fingerprint; the reverse implication is a hypergeometric counting argument. The equivalence is extended to arbitrary graph properties via semi-hereditary envelopes (Corollary 1.7) and to all fixed bounded-arity relational signatures (Theorems 3.5, 4.4, 4.7). Part III derives closure under vertex partitions (Theorem 5.1), testers for linearly large induced substructures (Theorem 6.1), and entropy-deficit/counting consequences in far hosts (Section 7).

Significance. If the characterization is correct, it resolves the quantitative question of Alon–Fischer–Newman–Shapira in a strong form: one-sided testability and ordered-container parameters are equivalent up to explicit polynomial transformations, with an elementary regularity-free proof that extends uniformly to bounded-arity relational structures. The paper's positive contributions are substantial: the dense ordered container lemma (Theorem 1.5/Lemma 4.1) is explicit and constructive, the reverse counting argument is elementary, and the applications to partition properties and linearly large induced substructures are natural. The main caveat is that the forward direction of the central theorem imports a canonicalization step (queried-sample to canonical induced-sample) whose exact size-oblivious, one-sided, linear-rate form is not proved in the manuscript; if only a polynomial-rate canonicalization is available, the theorem's displayed constants and the application bounds change, though the qualitative polynomial equivalence may survive. The paper otherwise appears internally consistent, with no circularity or fitted parameters.

major comments (1)

[§2.1 (Theorem 1.4(i)) and §3 (Theorem 3.5)] The forward direction relies on converting a size-oblivious one-sided tester of query complexity Q(ε) into a canonical tester sampling O(Q(cε)) vertices after an ε-rescaling. This is attributed to [GT03], but the standard Goldreich–Trevisan theorem gives a polynomial (typically quadratic) sample-complexity blow-up and does not explicitly handle the size-oblivious convention or preservation of one-sidedness. Theorem 3.5 is only a sketch. The step is load-bearing: q=O(Q(cε)), η=Ω(Q(cε)^{-1}), N=O(Q(cε)) and all importers (Corollary 1.7, Corollary 4.5, Theorem 5.2) depend on it. Please give a complete proof or exact reference for this variant, or restate the bounds if only the quadratic version holds.

minor comments (4)

[§3 (Theorem 3.5)] Please state the precise dependence of the constants c_τ and C_τ on the signature, and spell out how the size-oblivious convention is preserved in the canonicalization proof.
[§5.1 (Theorem 5.1)] The 'standard container-counting' paragraph should be expanded: show how the (n)_j ordered fingerprints are summed together with the probability that a random t-set contains them, so the final bound is independent of n.
[§6.1 (Theorem 6.1)] The threshold n0 is described only as O_τ(...); the o(1) terms in the edit-cost estimates should be quantified so that the choice of n0 is checkable.
[Remark 4.8] This remark appears at the start of Part III but is numbered as a remark in Section 4; renumber.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the testability–container equivalence is proved by direct construction in both directions; self-citations are contextual only.

full rationale

The paper's central claim (Theorem 1.4) is an equivalence between independently defined objects: size-oblivious one-sided testers and ordered container lemmas. The forward direction uses the external Goldreich–Trevisan canonicalization theorem and then constructs containers from the resulting removal statement (Theorem 2.2); the reverse direction is a counting argument (Lemma 4.2) that derives a removal lemma and tester from assumed container parameters. Neither direction fits a parameter to the data it later 'predicts'; the container parameters in Theorem 4.4(1) are explicit functions of the sample complexity and are obtained by construction, not by definitional identification. The citations to [BS24; BS25; Set25; GNS26] appear only in the introduction as context and are not used in any proof. The only non-external step that could be questioned is the reliance on the GT canonicalization theorem under the size-oblivious convention (proof of Theorem 1.4 and Theorem 3.5); this is an unproved assumption about an external theorem's scope, not a circular reduction. There is no self-definitional equivalence, no fitted input called a prediction, and no uniqueness imported from the authors' prior work.

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

The central characterization is self-contained given standard testing theorems. The listed external results are used in applications and in the canonicalization step, not fitted to data.

assumptions (5)

domain assumption Goldreich-Trevisan canonicalization theorem (GT03): any size-oblivious tester in the dense graph model can be converted to a canonical tester sampling O(Q(c epsilon)) vertices.
Used in the forward direction of Theorem 1.4 to pass from query complexity Q(epsilon) to a uniform sampling tester; entered at Section 1.1 and proof of Theorem 1.4.
domain assumption Alon-Shapira hereditary testing theorem (AS08a): every hereditary graph property admits a size-oblivious one-sided tester (with not necessarily effective complexity).
Used in Corollary 7.2 to obtain a tester for the hereditary property Pi, then Theorem 1.4 converts it to container parameters.
domain assumption Alon-Stav theorem (AS08b): for hereditary Pi with 2 <= chi_B(Pi) < infinity, d_Pi(G(n,1/2)) = (1/(2(chi_B(Pi)-1)) +/- o(1)) binom(n,2) with high probability.
Used in Section 7 to establish that G(n,1/2) is at constant positive distance from the perfect graph property, enabling Corollary 7.4.
domain assumption Bender-Ron acyclicity detection: a uniformly random set of eO(1/delta) vertices detects a directed cycle with probability at least 2/3 in any digraph delta-far from acyclic.
Used in Corollaries 5.6 and 6.2 to supply S_acyc(delta)=eO(1/delta) for the testers.
standard math Standard hypergeometric tail and Hoeffding inequalities.
Used in Lemma 4.2 and Theorem 6.1 to bound probabilities of random subsets.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A quantitative container characterization of one-sided testability." pith.science (2026). https://pith.science/paper/HWECUL3B

@misc{pith2026260801523,
  author       = {Pith},
  title        = {Pith review of: A quantitative container characterization of one-sided testability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HWECUL3B}},
  note         = {Machine review of arXiv:2608.01523}
}

read the original abstract

We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira. For hereditary graph properties, we prove that one-sided testability is quantitatively equivalent to the existence of suitable hypergraph containers, a central and widely used tool in modern combinatorics. Combining this equivalence with the Alon-Shapira notion of semi-hereditariness yields a quantitative characterization of arbitrary graph properties. The correspondence is effective in both directions and provides explicit translations between tester complexity and container parameters. Our proof is regularity-free and extends uniformly to every fixed finite relational signature of bounded arity, including digraphs, coloured graphs, and hypergraphs. As applications, we obtain quantitative closure results for partition properties and testers for properties defined by the existence of a linearly large induced substructure.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Journal of the ACM , volume =

Goldreich, Oded and Goldwasser, Shafi and Ron, Dana , title =. Journal of the ACM , volume =

work page
[2]

Goldreich, Oded , title =

work page
[3]

Bhattacharyya, Arnab and Yoshida, Yuichi , title =

work page
[4]

Random Structures & Algorithms , volume =

Goldreich, Oded and Trevisan, Luca , title =. Random Structures & Algorithms , volume =

work page
[5]

SIAM Journal on Computing , volume =

Alon, Noga and Shapira, Asaf , title =. SIAM Journal on Computing , volume =

work page
[6]

SIAM Journal on Computing , volume =

Alon, Noga and Fischer, Eldar and Newman, Ilan and Shapira, Asaf , title =. SIAM Journal on Computing , volume =

work page
[7]

Combinatorica , volume =

Alon, Noga and Fischer, Eldar and Krivelevich, Michael and Szegedy, Mario , title =. Combinatorica , volume =

work page
[8]

Borgs, Christian and Chayes, Jennifer T. and Lov. Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing , journal =

work page

Show all 25 references

[9]

Testing Properties of Graphs and Functions , journal =

Lov. Testing Properties of Graphs and Functions , journal =
[10]

A Measure-Theoretic Approach to the Theory of Dense Hypergraphs , journal =

Elek, G. A Measure-Theoretic Approach to the Theory of Dense Hypergraphs , journal =
[11]

Independent Sets in Hypergraphs , journal =

Balogh, J. Independent Sets in Hypergraphs , journal =
[12]

Inventiones Mathematicae , volume =

Saxton, David and Thomason, Andrew , title =. Inventiones Mathematicae , volume =
[13]

and Winston, Kenneth J

Kleitman, Daniel J. and Winston, Kenneth J. , title =. Discrete Mathematics , volume =
[14]

The Method of Hypergraph Containers , booktitle =

Balogh, J. The Method of Hypergraph Containers , booktitle =
[15]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =

Blais, Eric and Seth, Cameron , title =. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages =
[16]

SIAM Journal on Computing , volume =

Blais, Eric and Seth, Cameron , title =. SIAM Journal on Computing , volume =
[17]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =

Seth, Cameron , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =
[18]

Property Testing in Hypergraphs and the Removal Lemma , booktitle =

R. Property Testing in Hypergraphs and the Removal Lemma , booktitle =
[19]

Random Structures & Algorithms , volume =

Austin, Tim and Tao, Terence , title =. Random Structures & Algorithms , volume =
[20]

Proceedings of the 58th IEEE Symposium on Foundations of Computer Science , pages =

Alon, Noga and Ben-Eliezer, Omri and Fischer, Eldar , title =. Proceedings of the 58th IEEE Symposium on Foundations of Computer Science , pages =
[21]

and Ron, Dana , title =

Bender, Michael A. and Ron, Dana , title =. Random Structures & Algorithms , volume =
[22]

The Structure of Almost All Graphs in a Hereditary Property , journal =

Alon, Noga and Balogh, J. The Structure of Almost All Graphs in a Hereditary Property , journal =
[23]

Random Structures & Algorithms , volume =

Alon, Noga and Stav, Uri , title =. Random Structures & Algorithms , volume =
[24]

Journal of Combinatorial Theory, Series B , volume =

Alon, Noga and Stav, Uri , title =. Journal of Combinatorial Theory, Series B , volume =
[25]

arXiv preprint arXiv:2607.13011 , year=

Testing the Independent Set Property in Hypergraphs , author=. arXiv preprint arXiv:2607.13011 , year=

arXiv

Pith tools

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

[1] [1]

Journal of the ACM , volume =

Goldreich, Oded and Goldwasser, Shafi and Ron, Dana , title =. Journal of the ACM , volume =

work page

[2] [2]

Goldreich, Oded , title =

work page

[3] [3]

Bhattacharyya, Arnab and Yoshida, Yuichi , title =

work page

[4] [4]

Random Structures & Algorithms , volume =

Goldreich, Oded and Trevisan, Luca , title =. Random Structures & Algorithms , volume =

work page

[5] [5]

SIAM Journal on Computing , volume =

Alon, Noga and Shapira, Asaf , title =. SIAM Journal on Computing , volume =

work page

[6] [6]

SIAM Journal on Computing , volume =

Alon, Noga and Fischer, Eldar and Newman, Ilan and Shapira, Asaf , title =. SIAM Journal on Computing , volume =

work page

[7] [7]

Combinatorica , volume =

Alon, Noga and Fischer, Eldar and Krivelevich, Michael and Szegedy, Mario , title =. Combinatorica , volume =

work page

[8] [8]

Borgs, Christian and Chayes, Jennifer T. and Lov. Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing , journal =

work page