{"id":"02d76efa-447d-4eaa-bb6b-a5755afeeebd","arxiv_id":"2608.01523","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"One-sided testability of hereditary graph properties is quantitatively equivalent to ordered hypergraph container parameters, with effective translations in both directions.","lead":"This paper proves that one-sided testability of graph properties is quantitatively equivalent to the existence of 'ordered containers', a combinatorial condition from extremal combinatorics, resolving an open question. It gives polynomial query bounds for testing partition properties and linearly large induced substructures, and extends to all bounded-arity relational structures.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Forward direction of Theorem 1.4 relies on an unproved size-oblivious one-sided canonicalization; if the n<s convention breaks it, the q=O(Q) and eta=Omega(1/Q) bounds fail.","rationale":"The manuscript's own combinatorial core, the removal-container equivalence (Theorem 2.2), is self-contained, elementary, and appears correct: the pivot argument in the forward direction and the counting argument in the reverse direction both check out. The main theorem's forward direction, however, is not purely internal: it depends on converting an arbitrary size-oblivious one-sided tester into a canonical one-sided induced-sampling tester with only a constant-factor loss in epsilon and a linear sample bound. The paper states this as standard and gives only a sketch for the relational extension. This is exactly the reader's weakest assumption. I do not see evidence that the canonicalization claim is false; it is likely true and the paper is probably correct. But because the entire quantitative translation q=O(Q), eta=Omega(1/Q) is built on that step, and the step is not fully proved here, conditional acceptance remains the appropriate verdict. The concern does not change the reader's verdict, hence UNCHANGED.","tokens_in":22212,"tokens_out":23071,"duration_ms":241162,"concrete_test":"Write out the full Goldreich-Trevisan canonicalization argument for size-oblivious one-sided testers, explicitly handling the case where the prescribed sample size exceeds the input. Prove directly that the resulting canonical rejection family contains no member of the property and no induced substructure of a member, and that the sample size is at most C Q(c ε) with absolute constants. If the proof instead requires sample size Theta(Q^2) to preserve one-sidedness, Theorem 1.4(i) must be weakened accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative equivalence rests on the assertion in the proof of Theorem 1.4 that a size-oblivious one-sided tester of query complexity Q can be converted, after changing epsilon by a constant factor, into a canonical one-sided tester sampling O(Q(c ε)) vertices, with the convention that requests exceeding the input size trigger full inspection. This is not proved in the paper; it is attributed to the Goldreich-Trevisan canonicalization theorem, which is stated for the standard dense-graph model and does not explicitly address the size-oblivious convention. The same unproved step is reused for bounded-arity relational structures in Theorem 3.5 and Corollary 4.5, where the proof is only a sketch. If the size-oblivious convention changes the canonicalization, or if preserving one-sidedness forces a larger sample, then the removal-lemma step with delta=2/3 no longer yields the stated parameters q=O(Q(c ε)), eta=Omega(Q(c ε)^{-1}), N=O(Q(c ε)). Since every subsequent result imports Theorem 1.4, the quantitative characterization is only as secure as this canonicalization step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":22580,"tokens_out":25892,"duration_ms":248094,"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":[{"comment":"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.","section":"§2.1 (Theorem 1.4(i)) and §3 (Theorem 3.5)"}],"minor_comments":[{"comment":"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.","section":"§3 (Theorem 3.5)"},{"comment":"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.","section":"§5.1 (Theorem 5.1)"},{"comment":"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.","section":"§6.1 (Theorem 6.1)"},{"comment":"This remark appears at the start of Part III but is numbered as a remark in Section 4; renumber.","section":"Remark 4.8"}],"recommendation":"major_revision","confidential_remarks":"The only serious issue is the canonicalization step. If the authors can provide a complete proof of the size-oblivious one-sided canonicalization with linear sample complexity, or adjust the bounds to the provable polynomial rate, I would be willing to accept. The remaining concerns are expository. I do not see circularity or fitted parameters."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nOverall: 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.\n\nRecommendation: send it to peer review, with a request to expand the canonicalization proof and the container-counting steps.","headline":"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.","tokens_in":22924,"tokens_out":7453,"would_cite":true,"duration_ms":69372,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C65","68Q17","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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","keywords":["one-sided property testing","dense graph model","hypergraph containers","hereditary graph properties","ordered container lemma","semi-hereditary properties","randomized algorithms","relational structures"],"falsifier":"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.","tokens_in":22211,"feed_emoji":"🧩","tokens_out":8634,"duration_ms":76351,"temperature":0.7,"pith_summary":"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.","feed_headline":"Container lemmas characterize one-sided graph testability","feed_subtitle":"Explicit polynomial translations turn any tester into a container bound and back, yielding new testers for colouring and large substructures","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the canonicalization theorem that turns any size-oblivious one-sided tester into a canonical sampler, the crucial step for extracting container bounds from query complexity.","marker":"[GT03]"},{"why":"Establishes the qualitative one-sided testability of hereditary graph properties and introduces semi-hereditariness; the present paper quantifies this statement.","marker":"[AS08a]"},{"why":"Poses the question of a quantitative characterization and supplies the regularity-based framework that the present paper avoids.","marker":"[Alo+09]"},{"why":"Introduces the hypergraph container method, which the ordered container lemma adapts to the testing setting.","marker":"[BMS15]"},{"why":"Independent introduction of the container method, equally central to the methodology.","marker":"[ST15]"},{"why":"Defines the dense graph model and the basic testing guarantees used throughout.","marker":"[GGR98]"},{"why":"Supplies the acyclicity tester used in the applications to dichromatic number and rho-DAG properties.","marker":"[BR02]"},{"why":"Provides the edit-distance asymptotics for G(n,1/2) that the random-host corollary needs.","marker":"[AS08b]"}],"fun_headline_variants":["One-sided testability equals container efficiency","Containers pin down one-sided testing complexity","Quantitative link: containers and one-sided testers","From testers to containers and back"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["One-sided testability equals container efficiency","Containers pin down one-sided testing complexity","Quantitative link: containers and one-sided testers","From testers to containers and back"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000127,"raw_usage":{"total_tokens":927,"prompt_tokens":697,"completion_tokens":230,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":441,"completion_tokens_details":{"reasoning_tokens":174}},"tokens_in":441,"tokens_out":230,"duration_ms":2985,"temperature":1.0,"reasoning_tokens":174,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:08:20.897747+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}