Pith. sign in

REVIEW 2 major objections 4 minor 32 references

Supersaturation for Hypergraph-Weighted Independent Sets

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read This paper establishes a universal supersaturation theorem: for any hereditary family of hypergraph pairs with extremal function O(n^β), having k n^β edges of H forces Ω(k^{f/(h−β)}) edges of F whenever f≥h−β.

desk verdict Strong framework and first bound, but the second bound of Theorem 1.7 rests on a false step in Claim 4.10; the paper needs a fix before the small-F applications are usable. read the letter →

arxiv 2607.14022 v1 pith:I65E6FFP submitted 2026-07-15 math.CO

Sam Spiro This is my paper
classification math.CO MSC 05C3505C6505D40
keywords supersaturationgeneralizedTuránnumbershypergraphpairsweightedindependentsetshereditaryfamiliesextremalcombinatoricssystemsoflinearequationspartitehypergraphs
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 establishes a general supersaturation theorem: in any hereditary family of hypergraph pairs (H,F) whose extremal function grows at most like n^β, any member with k n^β edges of H must contain Ω(k^{f/(h−β)}) edges of F, where h and f bound the edge sizes of H and F. It reaches this by viewing extremal problems as weighted independent sets: independent sets of F are rewarded by how many H-edges they induce. If correct, this yields the first fully general supersaturation bounds for generalized Turán problems, meaning graphs with many copies of one subgraph H are forced to contain many copies of another subgraph F. The same machinery gives counterparts for planar graphs and for subsets of integers that avoid one system of linear equations while maximizing solutions to another. The payoff is a single explanatory exponent that transfers supersaturation arguments from edge counts to arbitrary subgraph counts.

What carries the argument

The central object is the hypergraph pair (H,F) on a common vertex set, with α_H(F)=max{e(H[I]): I independent in F}; 'large' independent sets are those inducing many H-edges. The proof's engine is a part-shrinking process (Proposition 4.5) applied after Lemma 4.1 extracts an h-partite subhypergraph of H with a constant fraction of its edges. For each part V_i, Lemma 4.2 supplies a subset V_i′ and a factor p_i so that H loses at most a factor ∏p_i of its edges, while F-edges of type t=(t_1,…,t_h) — the vector of intersection sizes with the parts — are bounded in the surviving subhypergraph by ∏p_i^{t_i} times their original count, up to a (40h)^{O(h²f′)} constant. Iterating at most 4h² times

What would settle it

Take H=F∪K_1 and let G be a copy of F together with k isolated vertices. Then #(H,G)=k while #(F,G)=1, and since ex(n,H,F)=0 for sufficiently large n, the condition #(H,G)≥k ex(n,H,F) holds trivially; this concrete example settles that any universal supersaturation statement of Theorem 1.1 fails if the no-isolated-vertices assumption is dropped.

Watch

Extended reading notes

Core claim

The central claim is that supersaturation for a broad class of extremal problems is governed by one ratio, f/(h−β). Concretely, let P be a hereditary family of hypergraph pairs (H,F) in which H-edges have size at most h and F-edges have size between f and f′, and suppose the extremal value ex(n,P), the maximum H-edge count over n-vertex F-independent objects, grows at most like n^β. Theorem 1.7 asserts that if f≥h−β, any (H,F)∈P_n with e(H)≥k n^β must have e(F)=Ω(k^{f/(h−β)}); when f<h−β, the same conclusion holds in the weaker form Ω(k^{2/(h−β−min{f′,⌈h−β⌉−1}+2)}) provided no edge of any F is contained in an edge of any H. The proof reduces to partite subhypergraphs and shrinks each part by

Load-bearing premise

The load-bearing structural premise is that the forbidden object F has no isolated vertices (equivalently, in the small-parameter regime, that no F-edge sits inside an H-edge); without it the forced-count conclusion is simply false, as the paper's own counterexample shows.

Editorial extensions

If this is right

  • Graphs: if #(H,G)≥k n^β and ex(n,H,F)=O(n^β), then #(F,G)=Ω(k^{f/(h−β)}) when f≥h−β, and Ω(k^{2/(h−β−f+2)}) when f<h−β and F is not a subgraph of H; in particular, graphs with C′ex(n,H,F) copies of H have at least C copies of F.
  • Planar graphs satisfy the same two exponents, so n^ε·ex_P(n,H,F) copies of H force n^δ copies of F for some δ>0.
  • Sets of integers: a set A of size n with #_N(H,A)≥k n^β must contain Ω(k^{f/(h−β)}) solutions from F when F-solutions have size at least h−β, giving a common framework for problems about arithmetic progressions and Sidon-type equations.
  • A deletion-based general bound gives Ω(k^{(f+h−1−β)/(h−β)} n^{β−h+1}) in all hereditary bounded pairs, and this bound is best possible in the extremal case e(H)=Θ(n^h) with f-uniform F.

Reading between the lines

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

  • The exponent f/(h−β) looks like a dimension: h is the ambient edge size and h−β is the codimension of the extremal family. If this reading is right, the same formula should predict supersaturation exponents for other hereditary settings with ex(n,P)=O(n^β), including hypergraph Turán problems, before a dedicated proof is found.
  • The paper's second-case bound is self-consciously an artifact of the method, and its Question 5.1 asks whether Ω(k^{f/(h−β)}) can hold even when f<h−β under stronger intersection conditions; resolving that question would tell whether the two regimes are genuinely different.
  • The hypergraph-pair formalism points toward counting: supersaturation theorems are the standard input for counting results and container-type arguments, so one natural next step is to use these bounds to count the number of large H-rich, F-poor sets, in both the graph and integer settings.
  • For systems of linear equations, the type decomposition suggests the framework extends to configurations with unequal variable roles, not just uniform arithmetic progressions, as long as solutions are encoded as hyperedges of size between f and f′.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper introduces a general framework for supersaturation in which one seeks subsets that are independent in a hypergraph F while inducing many edges in another hypergraph H on the same vertex set, encoded by the quantity α_H(F). The main abstract results are Theorem 1.5, proved by a randomized deletion argument in the style of Ferber–McKinley–Samotij, and Theorem 1.7, proved by a more involved partite-shrinking argument that gives two bounds depending on whether f ≥ h−β or f < h−β. These are applied to generalized Turán numbers, planar generalized Turán numbers, and extremal problems for subsets of integers with forbidden/encouraged configurations. The paper is well motivated and carefully written, with explicit discussion of the necessity of hypotheses such as the no-isolated-vertices condition.

Significance. If the technical results are fully correct, the paper makes a substantial contribution: Theorem 1.5 gives a clean, general supersaturation bound with a short proof, and the partite-shrinking Proposition 4.5 is an interesting new technique. The applications to essentially arbitrary H and F, and to additive-combinatorial configurations, go beyond previous sporadic results. The paper also honestly identifies necessary conditions and gives counterexamples when they fail. However, the proof of the second bound of Theorem 1.7 contains a specific gap that is load-bearing: as written, it does not establish Proposition 4.8's second alternative, and hence Theorems 1.1(iii), 1.3, and 1.4(iii) are not proved. The first bound of Theorem 1.7 and Theorem 1.5 appear sound.

major comments (2)
  1. [Section 4, Claim 4.10] The proof asserts: 'if |I_t|<|t| then |I_t|≤|t|−2 since such a t has some t_i≥2.' This is false. For example, in a 3-partite H with |V'_1|=1 and |V'_2|,|V'_3|≥2, a type t=(1,1,0) has |t|=2 and |I_t|=1, with no t_i≥2. Such a type is compatible with the no-containment hypothesis: an H'-edge can use a vertex in V'_2 different from the vertex used by the F-edge. For |I_t|=|t|−1, the bound (7) gives only (C^{-1}k)^{1/(h−β−|t|+1)}, which is larger than k^{-2/(h−β−|t|+2)} for large k; hence the assumed upper bound e_t(F)≤c k^{2/(h−β−|t|+2)} does not imply (6). Consequently the proof does not establish e_t(F')=0, so Proposition 4.8's second bound and the second part of Theorem 1.7 are unproved. This also affects Theorem 1.1(iii), Theorem 1.3, and Theorem 1.4(iii).
  2. [Section 4, proof of Proposition 4.5] In Claim 4.7 the proof uses the inequality 'C>(20)^{4h^3}' to absorb the factor (20)^{j(h−s)}. The stated hypothesis of Proposition 4.5 only gives k≥C≥(30)^{4h^2}. For h≥2, (30)^{4h^2}<(20)^{4h^3}, so this inequality does not follow. This is repairable by enlarging the constant in Proposition 4.5 or by choosing C in Proposition 4.8 accordingly, but as written the proof of Proposition 4.5 is incomplete.
minor comments (4)
  1. [Theorem 1.1 statement] In the paragraph before part (ii), '1 β=0' should read 'β=0'.
  2. [Proof of Theorem 1.3] The phrase 'the h-partite result' is unclear; partite language is defined for hypergraphs in Section 4, while the planar graph context here may confuse the reader.
  3. [Claim 4.3] Typo: 'there must exists some v' should be 'there must exist some v'.
  4. [Proof of Proposition 4.8] The displayed definition of C is missing a closing brace: it should be C = max{C' h^β (30)^{4h^2 β}, (30)^{4h^2}}.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: central theorem derived from elementary probability; the only notable issue is a non-circular proof gap in Claim 4.10.

full rationale

The derivation chain is self-contained. Theorem 1.7 is the technical engine and is proved from Propositions 4.5 and 4.8, which in turn are built from Lemma 4.2, Chernoff/Chebyshev estimates, and the hypothesis ex(n,P)=O(n^β). No equation in the proof reduces to the target e(F)=Ω(k^...) by construction; the extremal hypothesis is an input, not a renamed version of the conclusion. The applications in Section 2 are genuine reductions: the generalized Turán and integer-set families are constructed from the original graphs/sets, and the no-isolated-vertices condition is explicitly used in Claim 2.2, with the paper itself providing the counterexample H=F∪K_1 when it fails. Self-citations ([7] in the introduction, [12,22] in concluding remarks) are contextual and not load-bearing; no uniqueness theorem or prior result of the authors is invoked to forbid alternatives. The only flag worth making is a rigor gap, not circularity: in the proof of Proposition 4.8, Claim 4.10 asserts 'if |I_t|<|t| then |I_t|≤|t|−2 since such a t has some t_i≥2.' This is false in general (e.g. a type (1,1,0) with one non-singleton part has |t|=2, |I_t|=1, and no ti≥2), so the written proof of the second bound of Theorem 1.7 is incomplete. That is a missing or erroneous proof step, not an equivalence between input and output, so it does not raise the circularity score.

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

The paper's claims rest on standard probabilistic tools and the unproved but standard extremal hypothesis ex(n,P)=O(n^β). No parameters are fitted to data; the constants c, k_0, C are existentially quantified and chosen in the proof, not estimated from examples. The only new objects are mathematical definitions (α_H(F), types, partite shrinking) that are fully specified in the text.

assumptions (5)
  • domain assumption P is a hereditary family of (h,f,f')-bounded hypergraph pairs
    Used throughout; it turns the supersaturation condition into the edge condition e(H) large implies e(F) large (Definition 3, §1.3).
  • domain assumption ex(n,P)=O(n^β) for some β<h
    Central hypothesis of Theorems 1.5/1.7; used in the contradiction argument in §4 (e.g., Claim 4.9).
  • domain assumption No edge of F is contained in an edge of H when f<h−β
    Necessary for the second bound of Theorem 1.7; used in Claim 4.10 to control |I_t|.
  • standard math Standard concentration inequalities (Chernoff, Chebyshev, Markov) and linearity of expectation
    Used in Lemma 4.2 and Proposition 4.5.
  • domain assumption F has no isolated vertices in graph applications
    Used in Claim 2.2 to compare ex(n',H,F) and ex(n,H,F); see weakest_assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Supersaturation for Hypergraph-Weighted Independent Sets." pith.science (2026). https://pith.science/paper/I65E6FFP

@misc{pith2026260714022,
  author       = {Pith},
  title        = {Pith review of: Supersaturation for Hypergraph-Weighted Independent Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I65E6FFP}},
  note         = {Machine review of arXiv:2607.14022}
}
abstract

Many extremal problems can be viewed as finding large independent sets in an auxiliary hypergraph. We propose a generalization of this by looking for ``large'' independent sets $I$ in a hypergraph $\mathcal{F}$ where ``large'' is measured by how many edges $I$ induces in another hypergraph $\mathcal{H}$ on the same vertex set as $\mathcal{F}$. We prove general supersaturation results for such extremal problems motivated by the breakthrough work of Ferber, McKinley and Samotij on counting $F$-free graphs. As applications, we prove new supersaturation bounds for generalized Tur\'an problems, as well as supersaturation bounds for a new set of extremal problems inspired by work of Fox and Pohoata on finding subsets $A\sub\mathbb{N}$ which maximize the number of solutions to a given system of equations while avoiding solutions to another system.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 1 linked inside Pith

  1. [13]

    Gerbner, Z

    D. Gerbner, Z. Nagy, and M. Vizer,Unified approach to the generalized Tur´ an problem and supersaturation, Discrete Mathematics345(2022), no. 3, 112743

    2022

  2. [1]

    Alon and C

    N. Alon and C. Shikhelman,ManyTcopies inH-free graphs, J. Combin. Theory Ser. B121(2016), 146–172

    2016

  3. [2]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij,Independent sets in hypergraphs, Journal of the American Mathematical Society28(2015), no. 3, 669–709

    2015

  4. [3]

    2, 131–150

    J´ ozsef Balogh and Wojciech Samotij,The number ofK m,m-free graphs, Combinatorica31(2011), no. 2, 131–150

    2011

  5. [4]

    2, 368– 388

    ,The number ofK s,t-free graphs, Journal of the London Mathematical Society83(2011), no. 2, 368– 388

    2011

  6. [5]

    Greg Blekherman and Ruilin Shi,Orders of growth of cycles in planar graphs, Forthcoming

  7. [6]

    Cutler, J

    J. Cutler, J. Nir, and A. Radcliffe,Supersaturation for subgraph counts, Graphs and Combinatorics38(2022), no. 3, 65

    2022

  8. [7]

    Dubroff, B

    Q. Dubroff, B. Gunby, B. Narayanan, and S. Spiro,Clique supersaturation, SIAM Journal on Discrete Math- ematics39(2025), no. 3, 1787–1805

    2025

Show all 32 references
  1. [8]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits,Cube-supersaturated graphs and related problems, Progress in graph theory (Wa- terloo, Ont., 1982) (1984), 203–218. 21

    1982

  2. [9]

    London Math

    Paul Erd˝ os and P´ al Tur´ an,On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc16(1941), no. 4, 212–215

    1941

  3. [10]

    Ferber, G

    A. Ferber, G. McKinley, and W. Samotij,Supersaturated sparse graphs and hypergraphs, International Math- ematics Research Notices2020(2020), no. 2, 378–402

    2020

  4. [11]

    3, 383–389

    Jacob Fox and Cosmin Pohoata,Sets without k-term progressions can have many shorter progressions, Random Structures & Algorithms58(2021), no. 3, 383–389

    2021

  5. [12]

    Jacob Fox, Jonathan Tidor, and Shengtong Zhang,Triangle Ramsey numbers of complete graphs, Journal of Combinatorial Theory, Series B176(2026), 268–286

    2026

  6. [14]

    Gerbner, E

    D. Gerbner, E. Gy˝ ori, A. Methuku, and M. Vizer,Generalized Tur´ an problems for even cycles, J. Combin. Theory Ser. B145(2020), 169–213

    2020

  7. [15]

    Gerbner and C

    D. Gerbner and C. Palmer,Survey of generalized Tur´ an problems – counting subgraphs, arXiv:2506.03418 (2025)

    2025 arXiv

  8. [16]

    Gerbner and B

    D. Gerbner and B. Patk´ os,Generalized Tur´ an problems for complete bipartite graphs, Graphs Combin.38 (2022), no. 5, Paper No. 164, 20

    2022

  9. [17]

    3, 493–510

    Andrzej Grzesik, Ervin Gy˝ ori, Addisu Paulos, Nika Salia, Casey Tompkins, and Oscar Zamora,The maximum number of paths of length three in a planar graph, Journal of Graph Theory101(2022), no. 3, 493–510

    2022

  10. [18]

    Ervin Gy˜ ori, Nika Salia, Addisu Paulos, Oscar Zamora, et al.,Generalized planar Tur´ an numbers, Electronic Journal of Combinatorics28(2021), no. 4, 1–15

    2021

  11. [19]

    2, 232–240

    Anastasia Halfpap and Cory Palmer,On supersaturation and stability for generalized Tur´ an problems, Journal of Graph Theory97(2021), no. 2, 232–240

    2021

  12. [20]

    Jiang and S

    T. Jiang and S. Longbrake,Balanced supersaturation and Tur´ an numbers in random graphs, Advances in Combinatorics (2024)

    2024

  13. [21]

    Zarankiewicz, Colloquium mathematicum, vol

    Tam´ as Kov´ ari, Vera S´ os, and P´ al Tur´ an,On a problem of K. Zarankiewicz, Colloquium mathematicum, vol. 3, Instytut Matematyczny Polskiej Akademii Nauk, 1954, pp. 50–57

    1954

  14. [22]

    1, 214–222

    Sammy Luo and Zixuan Xu,On off-diagonal F-Ramsey numbers, SIAM Journal on Discrete Mathematics40 (2026), no. 1, 214–222

    2026

  15. [23]

    Zequn Lv, Ervin Gy˝ ori, Zhen He, Nika Salia, Casey Tompkins, and Xiutao Zhu,The maximum number of copies of an even cycle in a planar graph, Journal of Combinatorial Theory, Series B167(2024), 15–22

    2024

  16. [24]

    J. Ma, X. Yuan, and M. Zhang,Some extremal results on complete degenerate hypergraphs, J. Combin. Theory Ser. A154(2018), 598–609

    2018

  17. [25]

    Robert Morris and David Saxton,The number ofC 2ℓ-free graphs, Advances in Mathematics298(2016), 534–580

    2016

  18. [26]

    4, 675–681

    Jaroslav Neˇ setˇ ril and Vojtˇ ech R¨ odl,Van der Waerden theorem for sequences of integers not containing an arithmetic progression ofkterms, Commentationes Mathematicae Universitatis Carolinae17(1976), no. 4, 675–681

    1976

  19. [27]

    3, 259–282

    Imre Z Ruzsa,Solving a linear equation in a set of integers i, Acta arithmetica65(1993), no. 3, 259–282

    1993

  20. [28]

    1, 211–233

    Tom Sanders,Three-term arithmetic progressions and sumsets, Proceedings of the Edinburgh Mathematical Society52(2009), no. 1, 211–233

    2009

  21. [29]

    Saxton and A

    D. Saxton and A. Thomason,Hypergraph containers, Inventiones mathematicae201(2015), no. 3, 925–992

    2015

  22. [30]

    Joel Spencer,Restricted ramsey configurations, J. Comb. Theory A19(1975), no. 3, 278–286

    1975

  23. [31]

    1, 199–245

    Endre Szemer´ edi,On sets of integers containing k elements in arithmetic progression, Acta Arithmetica27 (1975), no. 1, 199–245

    1975

  24. [32]

    X. Zhu, E. Gy˝ ori, Z. He, Z. Lv, N. Salia, and C. Xiao,Stability version of Dirac’s theorem and its applications for generalized Tur´ an problems, Bull. Lond. Math. Soc.55(2023), no. 4, 1857–1873. 22

    2023

Pith tools

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