Regularity for hypergraphs with bounded VC$_2$ dimension

Asaf Shapira; Lior Gishboliner; Yuval Wigderson

REVIEW 2 major objections 5 minor 2 cited by

Regularity for hypergraphs with bounded VC$_2$ dimension

T0 review · 2 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Bounded VC$_2$ dimension shrinks 3-graph regularity partitions from wowzer-type to double-tower size.

desk verdict 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. read the letter →

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

Lior Gishboliner , Asaf Shapira , Yuval Wigderson This is my paper

classification math.CO MSC 05C6505D10

keywords hypergraphregularityVC2dimension3-uniformhypergraphscylinderlemmaAckermannhierarchyinducedcountingquasirandomness

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

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.

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

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

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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, and a circularity audit.

Desk Editor's Note

read the letter

The headline: this is a serious paper with a real result, but it ships with a genuine gap in a load-bearing lemma. The reader's report is slightly too trusting; the stress-test's arithmetic concern about Lemma 4.1 lands, and I confirm it on reading.

The main result, Theorem 2.9, answers the Chernikov–Towsner–Terry question in the expected way: bounded VC2 dimension cuts the generic wowzer bound to double-tower, and Terry's earlier lower bound shows this sits one Ackermann level above the likely truth. The new engine, Theorem 2.13, is a genuinely useful contribution on its own, and the applications — a quasirandom-subset lemma for 3-graphs and a Rödl-type theorem — are sensible. The Haussler-free graph argument and its lift to uniformity 3 are fresh and worth reading. The paper is also honest about its limits: the abstract's 'best possible' is properly qualified in the body, and Conjectures 6.6–6.8 state the remaining gaps clearly.

The soft spot is real and it is exactly where the stress-test put it. In Lemma 4.1, the copy probability from Theorem A.1 is at least (1/2)δ^{t²}γ^{t³}, and the collision bound is t²δ^{t²}γ^{t³}. The claimed positive difference is a false inequality for t ≥ 1; here t is r ≥ 20, so the collision term dominates. As written, the proof of Lemma 4.1 is wrong, and the formal chain to Theorem 2.9 is incomplete. Good news: the fix is cheap. Raise the vertex-size threshold to Cδ^{−t²}γ^{−t³} with C > t² (or shrink ε in the counting-lemma application). The double-tower conclusion survives, so the qualitative theorem is almost certainly correct, but the manuscript should not claim a complete proof until this is patched.

The citation pattern is fine: external tools are used as advertised and the self-citations are not load-bearing. This paper is exactly what should go to peer review — a serious referee will spot the gap and it will be fixed — but it shouldn't pass as-is.

Bottom line: send it to review with a careful referee assigned to Appendix A.2. Once the constant is patched, it's a strong, citable paper.

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)

[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.
[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)

[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.
[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.
[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.
[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.
[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 · score 2.0 of 10

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.

Assumptions & free parameters 0 free parameters · 5 assumptions · 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 γ.

assumptions (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.

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}
}

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 to comment.

Forward citations

Cited by 2 Pith papers

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

On n-distality, n-triviality and hypergraph regularity in NIP theories
math.LO 2026-05 unverdicted novelty 7.0 of 10

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.
Homogeneous hypergraph regularity lemmas via $k$-strong honest definitions
math.LO 2026-07 conditional novelty 6.0 of 10

(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

[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]

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]

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]

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]

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]

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]

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]

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

Show all 73 references

[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

2022
[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

2024 arXiv
[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

2021
[12]

Chernikov, D

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

2019
[13]

Chernikov and S

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

2021
[14]

Chernikov and H

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

2020 arXiv
[15]

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

1991
[16]

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

1989
[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

2022
[18]

Conlon and J

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

2012
[19]

Conlon, J

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

2018
[20]

Conlon, J

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

2022
[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

2012
[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

1995
[23]

Fox and R

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

2020
[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

2017
[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

2017
[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

2016
[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

2019
[28]

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

2021
[29]

Fox and B

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

2008
[30]

Frankl and V

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

2002
[31]

Frieze and R

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

1999
[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

2025
[33]

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

1997
[34]

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

2006
[35]

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

2007
[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

2005
[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

1995
[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

2016
[39]

Hrushovski, Y

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

2008
[40]

Huang, H

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

Janzer and C

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

2024
[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

2010
[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

2010
[44]

Luczak and S

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

2010 arXiv
[45]

Malliaris and S

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

2014
[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

2002
[47]

Moshkovitz and A

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

2019
[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

2024
[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

1986
[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

2005
[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

2010
[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

1972
[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

1972
[54]

Shelah, Strongly dependent theories, Israel J

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

2014
[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

2017
[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

1975
[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

1976
[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

2018
[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

2023
[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,
[61]

Terry, Growth of regular partitions 2: Weak regularity, 2024

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

2024 arXiv
[62]

Terry, Growth of regular partitions 3: Strong regularity and the vertex partition, 2024

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

2024 arXiv
[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

2024 arXiv
[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

2019
[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

2025 arXiv
[66]

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

1984
[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

1971
[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

2024
[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...

2023
[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...
[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 a...
[2024]

Preprint available at arXiv:2404.01274

arXiv
[2025]

Preprint available at arXiv:2502.09576

arXiv

Pith tools

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

[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