Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

Bounded VC$_2$ dimension shrinks 3-graph regularity partitions from wowzer-type to double-tower size.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

For 3-graphs of bounded VC2 dimension, an (ε,ψ)-regular partition exists with twr(twr(poly(1/ε))) vertex parts, improving the generic wowzer bound to tower type.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection Main theorem is real news — double-tower regularity for 3-graphs with bounded VC2 dimension — but the proof of Lemma 4.1 has an arithmetic slip that needs fixing before the paper is complete. the 2 major comments →

arxiv 2508.09969 v1 pith:4K7J2IFJ submitted 2025-08-13 math.CO

Regularity for hypergraphs with bounded VC$_2$ dimension

Lior Gishboliner , Asaf Shapira , Yuval Wigderson This is my paper
classification math.CO MSC 05C6505D10
keywords hypergraph regularityVC2 dimension3-uniform hypergraphscylinder regularity lemmaAckermann hierarchyinduced counting lemmaquasirandomness
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

Hypergraph regularity lemmas for 3-uniform hypergraphs normally produce partitions with wowzer-type (extremely fast-growing) bounds. This paper shows that if a 3-graph has bounded VC$_2$ dimension—a weak, combinatorially natural analogue of VC dimension for higher uniformity—then the vertex partition can be found with only double-tower size, dropping one level in the Ackermann hierarchy. The same bounded-dimension assumption forces most triples of parts to be nearly homogeneous: the hypergraph occupies either almost all or almost none of the triangles of the underlying graph. A tower-type lower bound shows that polynomial or exponential bounds, which are available for stronger hypergraph VC notions, are impossible here; the exact gap between tower and double-tower is left as an open problem. The proof introduces a hypergraph cylinder regularity lemma, which the paper applies to new quasirandom-subset and induced-density results for 3-graphs.

Core claim

The main theorem (Theorem 2.9) states that for every fixed $d$, every sufficiently large 3-graph with VC$_2$ dimension at most $d$ admits a chain partition (a partition of vertices and of pairs) with at most $\operatorname{twr}(\operatorname{twr}(\psi(\eta)^{-C}))$ vertex parts, where $\psi$ is any increasing polynomial with $\psi(x)\le x$, such that for a $(1-\eta)$-fraction of vertex triples the induced chain has a $\psi(\delta(G))$-quasirandom graph and relative hyperedge density in $[0,\eta]\cup[1-\eta,1]$, with $C$ depending only on $d$. This improves the generic wowzer-type vertex bound of the 3-graph regularity lemma by one level in the Ackermann hierarchy. A lower bound (Proposition

What carries the argument

The central object is a cylinder regularity lemma for 3-graphs (Theorem 2.13): every tripartite 3-graph admits a product-shaped partition of vertex tuples into cylinders, together with an edge partition, with only tower-type size, such that almost every cylinder is quasirandom in the sense of [34]. The proof combines this with an induced counting lemma with polynomial error terms (Lemma 4.1, derived from the counting lemma of [35]): a quasirandom chain whose relative density is bounded away from $0$ and $1$ contains every fixed tripartite 3-graph as an induced subhypergraph. Since a bounded-VC$_2$ hypergraph forbids one such graph, almost every quasirandom cylinder in its partition must be n

Load-bearing premise

The argument rests on the hypergraph counting lemma of [35] holding with error and regularity parameters that are polynomial in the target density; if those errors degraded with tower-type speed, the choices of $\eta$ and $\psi$ in Lemma 4.2 would fail and the double-tower bound would not follow.

What would settle it

Build an infinite family of 3-graphs with VC$_2$ dimension 1 for which every $(\varepsilon,\psi)$-regular partition with a polynomial $\psi$ uses at least $\mathrm{wow}(\operatorname{poly}(1/\varepsilon))$ vertex parts, contradicting Theorem 2.9. Equivalently, exhibit a tripartite chain meeting the hypotheses of Lemma 4.2 whose relative density is bounded away from $0$ and $1$ and which contains no induced copy of $V_{d+1}$, which would refute the induced counting lemma.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • With a polynomial error function $\psi$, bounded VC$_2$ dimension reduces the vertex-part count from wowzer-type to $\operatorname{twr}(\operatorname{twr}(\psi(\eta)^{-C}))$.
  • Most triples of parts are nearly homogeneous (relative density in $[0,\eta]\cup[1-\eta,1]$), which is stronger than plain quasirandomness.
  • Tower-type vertex parts remain necessary for VC$_2$ dimension 1, so no polynomial or exponential improvement is possible; the precise rate between tower and double-tower is open (Conjecture 6.6).
  • The hypergraph cylinder regularity lemma yields a quasirandom subset lemma for 3-graphs and a hypergraph analogue of the induced-density theorem (Theorems 6.2 and 6.3), with tower-type bounds.
  • The proof avoids packing-based arguments from the graph VC dimension theory, replacing them with a cylinder-partition method that extends to hypergraphs.

Where Pith is reading between the lines

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

  • If the polynomial dependence on the target density in the counting lemma of [35] is truly necessary, then closing the gap from double-tower to tower (Conjecture 6.6) will require a structurally different argument rather than a sharper choice of parameters.
  • The same cylinder technique may yield one-level Ackermann improvements for $k$-uniform hypergraphs with bounded VC$_{k-1}$ dimension, a direction the paper says it plans to address.
  • The double-tower cylinder regularity lemma should apply to any 3-graph regularity application that currently pays wowzer costs—removal lemmas, counting lemmas, or property testing—whenever the input is assumed to have bounded VC$_2$ dimension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies quantitative bounds for hypergraph regularity under bounded VC2 dimension. Its main theorem (Theorem 2.9) asserts that every sufficiently large 3-graph with VC2 dimension at most d admits an (η,ψ)-regular chain partition with at most twr(twr(ψ(η)^{-C})) vertex parts, for any increasing polynomial ψ with ψ(x)≤x, and moreover that most chains are ε-homogeneous in the sense that the relative density of the hypergraph is near 0 or 1. This improves the generic wowzer-type bound by one level of the Ackermann hierarchy. The proof introduces a cylinder regularity lemma for 3-graphs (Theorem 2.13/3.5), proved by an energy-increment argument, and combines it with Gowers's counting lemma and an induced counting lemma (Lemma 4.1). The paper also derives, from results of Terry, a matching tower-type lower bound (Proposition 1.5) and sketches applications to a hypergraph analogue of Rödl's theorem.

Significance. If the proof is repaired, this is a substantial contribution. It answers, in a strong quantitative form, a question of Chernikov–Towsner, Terry, and Wolf about whether bounded VC2 dimension improves the worst-case bounds for 3-graph regularity. The paper gives the first method that bypasses the absence of a Haussler-type packing lemma in uniformity 3, and the new hypergraph cylinder regularity lemma is likely to have further applications. The lower bound proof is clean and shows that the double-tower upper bound is only one level above the true tower-type complexity. The energy-increment proof of Theorem 3.5 is detailed, and the paper is careful about tracking quantitative dependencies. However, the proof as written contains a concrete arithmetic error in a key counting lemma (Lemma 4.1), so the main theorem is not yet fully proved.

major comments (2)
  1. [Appendix A.2, proof of Lemma 4.1] After applying Theorem A.1, the copy probability is bounded below by (1/2)δ^{t^2}γ^{t^3}, and the collision probability is bounded above by t^2δ^{t^2}γ^{t^3}. The text then claims the difference is positive. For t=r≥20 (indeed for all t≥1), t^2>1/2, so the collision bound is larger than the copy bound. Thus the argument that a collision-free K_t copy exists fails. Since Lemma 4.2, Lemma 4.3, Lemma 4.6 and Theorem 2.9 all rely on Lemma 4.1, this is a load-bearing gap. The fix is straightforward: strengthen the lower bound on min{|U1|,|U2|,|U3|} to Cδ^{-t^2}γ^{-t^3} for a constant C>2t^2, or equivalently use a sharper collision estimate; this changes only the constant in the 'sufficiently large' condition and does not affect the double-tower form. But as written the proof is incomplete.
  2. [Section 4, proof of Lemma 4.3] The passage 'as long as |V(H)| is sufficiently large...' asserts that at least a (1−3η)-fraction of tuples lie in cylinders with all t vertex parts of size at least δ^{-r^2}γ^{-r^3}. This does not follow immediately from Theorem 3.5, which only guarantees product density and quasirandomness. The missing argument is that for each coordinate i, the total measure of cylinders with |Y_i|<T is at most tT/n, since ∑_Y |Y_{-i}| = n^{t-1}. Please add this or an equivalent justification; otherwise a reader cannot verify the threshold conditions needed to apply Lemma 4.2.
minor comments (5)
  1. [Appendix A.2] In the collision estimate, the union bound should be over unordered pairs of coordinates with the same index. Writing t^2 is correct up to the constant needed for the repair, but once the main gap is fixed, the explicit binomial factor should be used.
  2. [Lemma 4.4] The statement treats d(H0|G)<γ and d(H0|G)>1−γ, leaving the boundary cases d(H0|G)=γ or 1−γ unhandled. Replacing γ by γ/2 in the assumption, or adding a negligible perturbation, removes this edge case.
  3. [Definition 4.5] The bound |QE(Yi×Yj)| ≤ 2^{|PE||PV|} is correct but loose; writing |PE|^{|PV|} would be more transparent and avoids a minor notational surprise.
  4. [Proof of Theorem 3.5] In the final displayed bound, the iteration count appears once as 104t^6η^{-3} and once as 104t^3η^{-3}; the former is the one matching the preceding bound on τ. This is a harmless typo but should be corrected.
  5. [Proof of Theorem 2.9] The final constant bookkeeping (4ζ+√ζ+η/3+3α ≤ η) is compressed into a single sentence. A one-line numerical verification would help, especially because the definitions ζ=η^2/16 and α=ψ((η/(9L))^3) are substituted simultaneously.

Circularity Check

0 steps flagged

No significant circularity: the main derivation is independent and rests on external counting and regularity lemmas; the few self-citations are contextual and not load-bearing.

full rationale

The paper's central claim, Theorem 2.9, is not obtained by renaming an input or by fitting a parameter to its conclusion. Its proof chain is: (1) Theorem 3.5 proves a cylinder regularity lemma for all 3-graphs by an energy-increment argument using Gowers's Lemma 3.3 and the Duke–Lefmann–Rödl cylinder regularity lemma (Lemma 3.4); no bounded VC2 assumption is used there. (2) Lemma 4.1 is an induced counting lemma whose proof reduces to Gowers's external counting lemma [35, Cor 5.3], stated as Theorem A.1. That is an independent, non-self-cited external result. (3) Lemma 4.2 applies Lemma 4.1 to show that a quasirandom chain in a bounded-VC2 hypergraph must have relative density near 0 or 1; the bounded-VC2 assumption enters through the forbidden tripartitely induced subgraph V_{d+1}, not through the desired regularity conclusion. (4) Lemmas 4.3, 4.6, and 4.7 convert the cylinder partition into a true chain partition, using Markov's inequality and Szemerédi's graph regularity lemma. None of these steps assumes the theorem's conclusion. The self-citations are contextual: [32] is an earlier single-exponential bound for a different (slicewise) VC notion, and [47] is mentioned when discussing general hypergraph regularity and in an open-problem conjecture, not in the proof of Theorem 2.9. The lower bound Proposition 1.5 is explicitly derived from Terry's external results [61, 62]. The paper's reliance on Gowers's counting lemma with polynomial dependencies is a stated assumption, not a hidden circular input. The skeptic's arithmetic objection to Appendix A.2 is a correctness gap in a proof detail, not a circularity: even if the collision bound as written is too coarse, the claimed reduction is from an external counting lemma and does not make the theorem's output an input. Therefore no circular step is exhibited, and the score reflects only the presence of minor, non-load-bearing self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

The central claim itself is a new theorem; what it pulls from outside is a set of standard regularity and counting tools, plus the structural definition of VC2 dimension. No parameters are fitted to data; all constants are explicit functions of d and γ.

axioms (5)
  • domain assumption VC2 dimension at most d means H has no tripartitely induced copy of V_{d+1}
    This is the defining structural assumption of the theorem; the proof of Lemma 4.2 uses it to trigger Lemma 4.1.
  • standard math Gowers's hypergraph counting lemma with polynomial bounds (Theorem A.1, special case of [35, Cor 5.3])
    Loaded at Lemma 4.1; if this counting lemma had non-polynomial bounds, the argument setting η,ψ polynomially in γ would fail.
  • standard math Duke-Lefmann-Rödl cylinder regularity lemma for graphs, extended to multiple graphs (Lemma 3.4)
    Used iteratively in the proof of Theorem 3.5 to maintain quasirandomness of the graphs in edge partitions; the bound |P_V|≤2^{mt^2α^{-20}} is critical for the tower height.
  • standard math Szemerédi's regularity lemma for simultaneously regularizing multiple graphs (Lemma 4.7, [34, Theorem 7.8])
    Applied once at the end of the proof of Theorem 2.9; its twr(16α^{-3}T^2L) bound is absorbed into the outer tower.
  • standard math Terry's results [61, Theorem 5.4] and [62, Lemma 5.15] for the lower bound (Propositions 5.1, 5.2 and hence Proposition 1.5)
    The lower bound is not proved from scratch; the paper derives it from Terry's results.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Regularity for hypergraphs with bounded VC$_2$ dimension." pith.science (2026). https://pith.science/paper/4K7J2IFJ

@misc{pith2026250809969,
  author       = {Pith},
  title        = {Pith review of: Regularity for hypergraphs with bounded VC$_2$ dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4K7J2IFJ}},
  note         = {Machine review of arXiv:2508.09969}
}
Share X Bluesky LinkedIn Reddit HN
abstract

While Szemer\'edi's graph regularity lemma is an indispensable tool for studying extremal problems in graph theory, using it comes with a hefty price, since a worst-case graph may only have regular partitions of tower-type size. It is thus sensible to ask if there is some natural restriction which forces graphs to have much smaller regular partitions. A celebrated result of this type, due to Alon-Fischer-Newman and Lov\'asz-Szegedy, states that for graphs of bounded VC dimension, one can reduce the tower-type bounds to polynomial. The graph regularity lemma has been extended to the setting of $k$-graphs by Gowers, Nagle-R\"odl-Schacht-Skokan, and Tao. Unfortunately, these lemmas come with even larger Ackermann-type bounds. Chernikov-Starchenko and Fox-Pach-Suk considered a strong notion of $k$-graph VC dimension and proved that $k$-graphs of bounded VC dimension have regular partitions of polynomial size. Shelah introduced a weaker and combinatorially natural notion of dimension, called VC$_2$ dimension, which has since been extensively studied. In particular, Chernikov, Towsner, Terry, and Wolf asked if one can improve the worst case bounds for 3-graph regularity when the 3-graph has bounded VC$_2$ dimension. Our main result in this paper answers this question positively in the following strong sense: in the setting of bounded VC$_2$ dimension, one can reduce the bounds for 3-graph regularity by one level in Ackermann hierarchy. Furthermore, our new bound is best possible. Our proof has two key steps. We first introduce a new method for designing regularity lemmas for graphs of bounded VC dimension, based on the cylinder regularity lemma. We then prove a hypergraph version of the cylinder regularity lemma, which allows us to extend this method to hypergraphs. We also highlight a few other applications of this cylinder regularity lemma, which we expect to find many other uses.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On n-distality, n-triviality and hypergraph regularity in NIP theories

    math.LO 2026-05 unverdicted novelty 7.0

    Strongly n-distal NIP theories admit a hypergraph regularity lemma, compact domination for definable fsg groups, and the n-distality hierarchy is strict among stable theories; infinite such fields have characteristic zero.

  2. Homogeneous hypergraph regularity lemmas via $k$-strong honest definitions

    math.LO 2026-07 conditional novelty 6.0

    (k+1)-uniform hypergraphs definable in NIP strongly k-distal structures admit homogeneous regularity lemmas whose partitions are uniformly definable and polynomially bounded in 1/δ.

Reference graph

Works this paper leans on

73 extracted references · 64 canonical work pages · cited by 2 Pith papers · 2 internal anchors

  1. [1]

    N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs, Combi- natorica 20 (2000), 451–476

    work page 2000

  2. [2]

    N. Alon, E. Fischer, and I. Newman, Efficient testing of bipartite graphs for forbidden induced subgraphs, SIAM J. Comput. 37 (2007), 959–976

    work page 2007

  3. [3]

    N. Alon, J. Fox, and Y. Zhao, Efficient arithmetic regularity and removal lemmas for induced bipartite patterns, Discrete Anal. (2019), Paper No. 3, 14pp

    work page 2019

  4. [4]

    N. Alon, R. Livni, M. Malliaris, and S. Moran, Private PAC learning implies finite Littlestone dimension, in STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , ACM, New York, 2019, 852–860

    work page 2019

  5. [5]

    M. Amir, A. Shapira, and M. Tyomkyn, Two Erd˝ os–Hajnal-type theorems in hypergraphs, J. Combin. Theory Ser. B 146 (2021), 417–438

    work page 2021

  6. [6]

    Balogh, A

    J. Balogh, A. Bernshteyn, M. Delcourt, A. Ferber, and H. T. Pham, Sunflowers in set systems with small VC-dimension, 2024. Preprint available at arXiv:2408.04165

    arXiv 2024

  7. [7]

    Beyarslan, Random hypergraphs in pseudofinite fields, J

    ¨O. Beyarslan, Random hypergraphs in pseudofinite fields, J. Inst. Math. Jussieu 9 (2010), 29–47

    work page 2010

  8. [8]

    Blumer, A

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, Learnability and the Vapnik- Chervonenkis dimension, J. Assoc. Comput. Mach. 36 (1989), 929–965

    work page 1989

  9. [9]

    Brukhim, D

    N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff, A characterization of multiclass learnability, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, 2022, 943–955

    work page 2022

  10. [10]

    Buci´ c, J

    M. Buci´ c, J. Fox, and H. T. Pham, Equivalence between Erd˝ os–Hajnal and polynomial R¨ odl and Nikiforov conjectures, 2024. Preprint available at arXiv:2403.08303

    Pith/arXiv arXiv 2024

  11. [11]

    Chernikov and N

    A. Chernikov and N. Hempel, On n-dependent groups and fields II, Forum Math. Sigma 9 (2021), Paper No. e38, 51

    work page 2021

  12. [12]

    Chernikov, D

    A. Chernikov, D. Palacin, and K. Takeuchi, On n-dependence, Notre Dame J. Form. Log. 60 (2019), 195–214

    work page 2019

  13. [13]

    Chernikov and S

    A. Chernikov and S. Starchenko, Definable regularity lemmas for NIP hypergraphs, Q. J. Math. 72 (2021), 1401–1433

    work page 2021

  14. [14]

    Chernikov and H

    A. Chernikov and H. Towsner, Hypergraph regularity and higher arity VC-dimension, 2020. Preprint available at arXiv:2010.00726

    Pith/arXiv arXiv 2020

  15. [15]

    F. R. K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures Algorithms 2 (1991), 241–252

    work page 1991

  16. [16]

    F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362. 37

    work page 1989

  17. [17]

    Conant, A

    G. Conant, A. Pillay, and C. Terry, Structure and regularity for subsets of groups with finite VC-dimension, J. Eur. Math. Soc. (JEMS) 24 (2022), 583–621

    work page 2022

  18. [18]

    Conlon and J

    D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), 1191–1256

    work page 2012

  19. [19]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov, Hereditary quasirandomness without regularity, Math. Proc. Cambridge Philos. Soc. 164 (2018), 385–399

    work page 2018

  20. [20]

    Conlon, J

    D. Conlon, J. Fox, and Y. Wigderson, Ramsey numbers of books and quasirandomness, Com- binatorica 42 (2022), 309–363

    work page 2022

  21. [21]

    Conlon, H

    D. Conlon, H. H` an, Y. Person, and M. Schacht, Weak quasi-randomness for uniform hyper- graphs, Random Structures Algorithms 40 (2012), 1–38

    work page 2012

  22. [22]

    R. A. Duke, H. Lefmann, and V. R¨ odl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), 598–620

    work page 1995

  23. [23]

    Fox and R

    J. Fox and R. Li, On edge-ordered Ramsey numbers, Random Structures Algorithms 57 (2020), 1174–1204

    work page 2020

  24. [24]

    Fox and L

    J. Fox and L. M. Lov´ asz, A tight lower bound for Szemer´ edi’s regularity lemma,Combinatorica 37 (2017), 911–951

    work page 2017

  25. [25]

    J. Fox, J. Pach, A. Sheffer, A. Suk, and J. Zahl, A semi-algebraic version of Zarankiewicz’s problem, J. Eur. Math. Soc. (JEMS) 19 (2017), 1785–1810

    work page 2017

  26. [26]

    J. Fox, J. Pach, and A. Suk, A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing, SIAM J. Comput. 45 (2016), 2199–2223

    work page 2016

  27. [27]

    J. Fox, J. Pach, and A. Suk, Erd˝ os-Hajnal conjecture for graphs with bounded VC-dimension, Discrete Comput. Geom. 61 (2019), 809–829

    work page 2019

  28. [28]

    J. Fox, J. Pach, and A. Suk, Bounded VC-dimension implies the Schur-Erd˝ os conjecture, Combinatorica 41 (2021), 803–813

    work page 2021

  29. [29]

    Fox and B

    J. Fox and B. Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), 1771–1800

    work page 2008

  30. [30]

    Frankl and V

    P. Frankl and V. R¨ odl, Extremal problems on set systems,Random Structures Algorithms 20 (2002), 131–164

    work page 2002

  31. [31]

    Frieze and R

    A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175–220

    work page 1999

  32. [32]

    Gishboliner, A

    L. Gishboliner, A. Shapira, and Y. Wigderson, Is it easy to regularize a hypergraph with easy links?, 2025. Preprint available at arXiv:2506.15582

    arXiv 2025

  33. [33]

    W. T. Gowers, Lower bounds of tower type for Szemer´ edi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322–337

    work page 1997

  34. [34]

    W. T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), 143–184. 38

    work page 2006

  35. [35]

    W. T. Gowers, Hypergraph regularity and the multidimensional Szemer´ edi theorem, Ann. of Math. (2) 166 (2007), 897–946

    work page 2007

  36. [36]

    Green, A Szemer´ edi-type regularity lemma in abelian groups, with applications, Geom

    B. Green, A Szemer´ edi-type regularity lemma in abelian groups, with applications, Geom. Funct. Anal. 15 (2005), 340–376

    work page 2005

  37. [37]

    Haussler, Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik- Chervonenkis dimension, J

    D. Haussler, Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik- Chervonenkis dimension, J. Combin. Theory Ser. A 69 (1995), 217–232

    work page 1995

  38. [38]

    Hempel, On n-dependent groups and fields, MLQ Math

    N. Hempel, On n-dependent groups and fields, MLQ Math. Log. Q. 62 (2016), 215–224

    work page 2016

  39. [39]

    Hrushovski, Y

    E. Hrushovski, Y. Peterzil, and A. Pillay, Groups, measures, and the NIP, J. Amer. Math. Soc. 21 (2008), 563–596

    work page 2008

  40. [40]

    Huang, H

    X. Huang, H. Liu, M. Rong, and Z. Xu, Interpolating chromatic and homomorphism thresholds,

    work page

  41. [41]

    Janzer and C

    O. Janzer and C. Pohoata, On the Zarankiewicz problem for graphs with bounded VC- dimension, Combinatorica 44 (2024), 839–848

    work page 2024

  42. [42]

    Kohayakawa, B

    Y. Kohayakawa, B. Nagle, V. R¨ odl, and M. Schacht, Weak hypergraph regularity and linear hypergraphs, J. Combin. Theory Ser. B 100 (2010), 151–160

    work page 2010

  43. [43]

    Lov´ asz and B

    L. Lov´ asz and B. Szegedy, Regularity partitions and the topology of graphons, inAn irregular mind, Bolyai Soc. Math. Stud. , vol. 21, J´ anos Bolyai Math. Soc., Budapest, 2010, 415–446

    work page 2010

  44. [44]

    Luczak and S

    T. Luczak and S. Thomass´ e, Coloring dense graphs via VC-dimension, 2010. Preprint available at arXiv:1007.1670

    Pith/arXiv arXiv 2010

  45. [45]

    Malliaris and S

    M. Malliaris and S. Shelah, Regularity lemmas for stable graphs, Trans. Amer. Math. Soc. 366 (2014), 1551–1585

    work page 2014

  46. [46]

    Matouˇ sek,Lectures on discrete geometry, Graduate Texts in Mathematics, vol

    J. Matouˇ sek,Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer- Verlag, New York, 2002

    work page 2002

  47. [47]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A tight bound for hypergraph regularity, Geom. Funct. Anal. 29 (2019), 1531–1578

    work page 2019

  48. [48]

    Nagle, V

    B. Nagle, V. R¨ odl, and M. Schacht, Equivalent regular partitions of three-uniform hypergraphs, Random Structures Algorithms 65 (2024), 703–718

    work page 2024

  49. [49]

    R¨ odl, On universality of graphs with uniformly distributed edges,Discrete Math

    V. R¨ odl, On universality of graphs with uniformly distributed edges,Discrete Math. 59 (1986), 125–134

    work page 1986

  50. [50]

    R¨ odl, B

    V. R¨ odl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa, The hypergraph regularity method and its applications, Proc. Natl. Acad. Sci. USA 102 (2005), 8109–8113

    work page 2005

  51. [51]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Regularity lemmas for graphs, inFete of combinatorics and computer science, Bolyai Soc. Math. Stud. , vol. 20, J´ anos Bolyai Math. Soc., Budapest, 2010, 287–325

    work page 2010

  52. [52]

    Sauer, On the density of families of sets, J

    N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A 13 (1972), 145–147. 39

    work page 1972

  53. [53]

    Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J

    S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), 247–261

    work page 1972

  54. [54]

    Shelah, Strongly dependent theories, Israel J

    S. Shelah, Strongly dependent theories, Israel J. Math. 204 (2014), 1–83

    work page 2014

  55. [55]

    Shelah, Definable groups for dependent and 2-dependent theories, Sarajevo J

    S. Shelah, Definable groups for dependent and 2-dependent theories, Sarajevo J. Math. 13 (2017), 3–25

    work page 2017

  56. [56]

    Szemer´ edi, On sets of integers containing no k elements in arithmetic progression, Acta Arith

    E. Szemer´ edi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245

    work page 1975

  57. [57]

    Szemer´ edi, Regular partitions of graphs, inProbl` emes combinatoires et th´ eorie des graphes (Colloq

    E. Szemer´ edi, Regular partitions of graphs, inProbl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) , Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, 399–401

    work page 1976

  58. [58]

    Terry, V Cℓ-dimension and the jump to the fastest speed of a hereditary L-property, Proc

    C. Terry, V Cℓ-dimension and the jump to the fastest speed of a hereditary L-property, Proc. Amer. Math. Soc. 146 (2018), 3111–3126

    work page 2018

  59. [59]

    Terry, An improved bound for regular decompositions of 3-uniform hypergraphs of bounded VC2-dimension, Model Theory 2 (2023), 325–356

    C. Terry, An improved bound for regular decompositions of 3-uniform hypergraphs of bounded VC2-dimension, Model Theory 2 (2023), 325–356

    work page 2023

  60. [60]

    Terry, Growth of regular partitions 1: Improved bounds for small slicewise VC-dimension,

    C. Terry, Growth of regular partitions 1: Improved bounds for small slicewise VC-dimension,

    work page

  61. [61]

    Growth of regular partitions 2: Weak regularity

    C. Terry, Growth of regular partitions 2: Weak regularity, 2024. Preprint available at arXiv:2404.01293

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  62. [62]

    Growth of regular partitions 3: strong regularity and the vertex partition

    C. Terry, Growth of regular partitions 3: Strong regularity and the vertex partition, 2024. Preprint available at arXiv:2404.02024

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  63. [63]

    Terry, Growth of regular partitions 4: Strong regularity and the pairs partition, 2024

    C. Terry, Growth of regular partitions 4: Strong regularity and the pairs partition, 2024. Preprint available at arXiv:2404.02030

    Pith/arXiv arXiv 2024

  64. [64]

    Terry and J

    C. Terry and J. Wolf, Stable arithmetic regularity in the finite field model, Bull. Lond. Math. Soc. 51 (2019), 70–88

    work page 2019

  65. [65]

    Terry and J

    C. Terry and J. Wolf, Irregular triads in 3-uniform hypergraphs, Mem. Amer. Math. Soc. (2025), to appear. Preprint available at arXiv:2111.01737

    Pith/arXiv arXiv 2025

  66. [66]

    L. G. Valiant, A theory of the learnable, Comm. ACM 27 (1984), 1134–1142

    work page 1984

  67. [67]

    V. N. Vapnik and A. J. ˇCervonenkis, The uniform convergence of frequencies of the appearance of events to their probabilities, Teor. Verojatnost. i Primenen. 16 (1971), 264–279

    work page 1971

  68. [68]

    Wigderson, Ramsey theory—lecture notes, 2024

    Y. Wigderson, Ramsey theory—lecture notes, 2024. Available online at https://n.ethz.ch/ ~ywigderson/math/static/RamseyTheory2024LectureNotes.pdf

    work page 2024

  69. [69]

    Zhao, Graph theory and additive combinatorics—exploring structure and randomness, Cam- bridge University Press, Cambridge, 2023

    Y. Zhao, Graph theory and additive combinatorics—exploring structure and randomness, Cam- bridge University Press, Cambridge, 2023. 40 A Proofs of technical lemmas A.1 Proof of Lemma 3.2 Proof of Lemma 3.2. For Lemma 3.2(a), we first note that the definition (2) of q(PE(G)) is a sum of non-negative numbers, hence is q(PE(G)) is certainly non-negative. For...

    work page 2023

  70. [72]

    This proves Lemma 3.2(b)

    Plugging this inequality into the definition (2), we find that q(PE(G)) = X Z12∈PE (G;Y1×Y2) Z13∈PE (G;Y1×Y3) Z23∈PE (G;Y2×Y3) |∆(Z12 ∪ Z13 ∪ Z23)| |∆(G)| d(H |Z12 ∪ Z13 ∪ Z23)2 ⩽ X Z12∈PE (G;Y1×Y2) Z13∈PE (G;Y1×Y3) Z23∈PE (G;Y2×Y3) |∆(Z12 ∪ Z13 ∪ Z23)| |∆(G)| mX a,b,c=1 |∆(Za 12 ∪ Zb 13 ∪ Zc 23)| |∆(Z12 ∪ Z13 ∪ Z23)| d(H |Za 12 ∪ Zb 13 ∪ Zc 23)2 = X Z12∈...

    work page

  71. [73]

    We conclude that there is a choice of (x1,

    − t2δt2 γt3 > 0. We conclude that there is a choice of (x1, . . . , xt) ∈ X1 × · · · ×Xt satisfying both of these properties. The final observation is that, by our construction of H, these vertices x1, . . . , xt correspond to an induced copy of V in H0. Indeed, since both V and H0 are tripartite, all we need to check is that if xi, xj, xk lie in distinct...

    work page

  72. [2024]

    Preprint available at arXiv:2404.01274

    Pith/arXiv arXiv

  73. [2025]

    Preprint available at arXiv:2502.09576

    Pith/arXiv arXiv

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.