pith. sign in

arxiv: 1907.07639 · v1 · pith:57L5G6QWnew · submitted 2019-07-17 · 🧮 math.CO

A Tight Bound for Hyperaph Regularity

Guy Moshkovitz , Asaf Shapira This is my paper

Pith reviewed 2026-05-24 20:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph regularity lemmaAckermann functionlower boundsSzemerédi regularityk-uniform hypergraphscombinatorial partitions
0
0 comments X

The pith

Ackermann-type bounds are unavoidable for hypergraph regularity partitions at every uniformity k ≥ 2.

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

The hypergraph regularity lemma extends Szemerédi's theorem to k-uniform hypergraphs and produces partitions whose order is bounded by the k-th Ackermann function. The paper constructs, for each k ≥ 2, explicit k-uniform hypergraphs such that any partition satisfying the regularity condition must have at least this Ackermann-type order. This matches the upper bounds obtained in all known proofs and confirms Tao's prediction that the quantitative dependence cannot be improved. A reader cares because it shows the existing proofs are optimal in their size guarantees and rules out any substantially smaller regular partitions for these hypergraphs.

Core claim

For every k ≥ 2 there exist k-uniform hypergraphs such that every ε-regular partition has order at least the k-th Ackermann function (for suitable ε depending on k). The construction works uniformly across all k and extends Gowers' graph lower bound to the hypergraph setting.

What carries the argument

An explicit family of k-uniform hypergraphs forcing every regular partition to have Ackermann-type order.

If this is right

  • No proof of the hypergraph regularity lemma can produce partitions of tower-type or smaller order for all hypergraphs.
  • The proofs of Gowers, Nagle-Rödl-Schacht-Skokan and Tao are quantitatively tight for every k.
  • Lower bounds of Ackermann type hold for the same notion of regularity used in the upper-bound proofs.
  • The result rules out any regularity lemma whose partition size grows only exponentially or doubly-exponentially in 1/ε.

Where Pith is reading between the lines

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

  • Similar lower-bound constructions may apply to other partition notions such as equitable or induced regularity.
  • One could check whether the same hypergraphs force large partitions even under weaker regularity definitions used in some applications.
  • The result suggests that quantitative improvements in hypergraph regularity would require an entirely different proof technique rather than refining existing ones.

Load-bearing premise

The explicit construction produces k-uniform hypergraphs where every regular partition truly requires Ackermann-type size and does so uniformly for all k ≥ 2.

What would settle it

Exhibit, for some fixed k ≥ 2 and sufficiently small ε, a k-uniform hypergraph together with an ε-regular partition whose order is smaller than the k-th Ackermann function evaluated at 1/ε.

read the original abstract

The hypergraph regularity lemma -- the extension of Szemer\'edi's graph regularity lemma to the setting of $k$-uniform hypergraphs -- is one of the most celebrated combinatorial results obtained in the past decade. By now there are several (very different) proofs of this lemma, obtained by Gowers, by Nagle-R\"odl-Schacht-Skokan and by Tao. Unfortunately, what all these proofs have in common is that they yield regular partitions whose order is given by the $k$-th Ackermann function. We show that such Ackermann-type bounds are unavoidable for every $k \ge 2$, thus confirming a prediction of Tao. Prior to our work, the only result of this type was Gowers' famous lower bound for graph regularity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for every k ≥ 2 there exist k-uniform hypergraphs such that every regular partition has order at least the k-th Ackermann function. This supplies an explicit lower-bound construction that matches the upper bounds from existing proofs of the hypergraph regularity lemma (Gowers, Nagle-Rödl-Schacht-Skokan, Tao) and thereby confirms Tao's prediction; the argument extends Gowers' k=2 case and treats all k uniformly.

Significance. If the construction and its analysis are correct, the result is a major contribution to extremal combinatorics. It establishes that Ackermann-type bounds are unavoidable, completing the quantitative picture of hypergraph regularity. The independence of the lower-bound construction from the upper-bound proofs and the uniform treatment across k ≥ 2 are particular strengths.

minor comments (2)
  1. [§2] The definition of the Ackermann hierarchy in §2 could be stated with an explicit recurrence to avoid any ambiguity in the indexing for different k.
  2. [Figure 1] Figure 1 (the schematic of the construction) would benefit from an additional label clarifying the role of the auxiliary parameters.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central contribution is an explicit lower-bound construction of k-uniform hypergraphs (for every k ≥ 2) forcing Ackermann-type regular partitions; this construction is presented as independent of the matching upper-bound proofs (Gowers, Nagle-Rödl-Schacht-Skokan, Tao) and extends the k=2 case without any self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations. The derivation chain relies on the validity of the construction itself rather than reducing to prior results by the same authors or by ansatz smuggling, making the result self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no information on free parameters, axioms, or invented entities used in the proof.

pith-pipeline@v0.9.0 · 5652 in / 874 out tokens · 19906 ms · 2026-05-24T20:20:28.433463+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 1 internal anchor

  1. [1]

    Chung, R

    F. Chung, R. Graham and R. Wilson, Quasi-random graphs, C ombinatorica 9 (1989), 345–362. 1

    work page 1989

  2. [2]

    Conlon and J

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

    work page 2012

  3. [3]

    Conlon and J

    D. Conlon and J. Fox, Graph removal lemmas, Surveys in Com binatorics (2013), 1–50. 1

    work page 2013

  4. [4]

    Elek and B

    G. Elek and B. Szegedy, A measure-theoretic approach to t he theory of dense hypergraphs, Adv. Math. 231 (2012), 1731–1772. 2

    work page 2012

  5. [5]

    Erd˝ os, P

    P. Erd˝ os, P. Frankl and V. R¨ odl, The asymptotic number o f graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, G raphs Combin. 2 (1986), 113–

    work page 1986

  6. [6]

    Fox, A new proof of the graph removal lemma, Ann

    J. Fox, A new proof of the graph removal lemma, Ann. of Math . 174 (2011), 561–579. 1.1

    work page 2011

  7. [7]

    Fox and L.M

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

    work page 2017

  8. [8]

    Frankl and V

    P. Frankl and V. R¨ odl, Extremal problems on set systems, Random Struct. Alg. 20 (2002), 131–164. 1, 1, 4, 1.1, 5

    work page 2002

  9. [9]

    Furstenberg and Y

    H. Furstenberg and Y. Katznelson, An ergodic Szemer´ edi theorem for commuting transforma- tions, J. Anal. Math. 34 (1978), 275-291. 1

    work page 1978

  10. [10]

    Gowers, Lower bounds of tower type for Szemer´ edi’s uniformity lemma, Geom

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

    work page 1997

  11. [11]

    Gowers, A new proof of Szemer´ edi’s theorem, Geom

    T. Gowers, A new proof of Szemer´ edi’s theorem, Geom. Fu nct. Anal. 11 (2001), 465–588. 1

    work page 2001

  12. [12]

    Gowers, Quasirandomness, counting and regularity f or 3-uniform hypergraphs, Combin

    T. Gowers, Quasirandomness, counting and regularity f or 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), 143–184. 1, 1, 4, 5

    work page 2006

  13. [13]

    Gowers, Hypergraph regularity and the multidimensi onal Szemer´ edi theorem, Ann

    T. Gowers, Hypergraph regularity and the multidimensi onal Szemer´ edi theorem, Ann. of Math. 166 (2007), 897–946. 1, 1.1

    work page 2007

  14. [14]

    Hoeffding, Probability inequalities for sums of bound ed random variables, J

    W. Hoeffding, Probability inequalities for sums of bound ed random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. 4.2, 11

    work page 1963

  15. [15]

    Janson, T

    S. Janson, T. /suppress Luczak and A. Ruci´ nski,Random Graphs , Wiley, 2011. 4.2

    work page 2011

  16. [16]

    Kalyanasundaram and A

    S. Kalyanasundaram and A. Shapira, A wowzer-type lower bound for the strong regularity lemma, Proc. Lond. Math. Soc. 106 (2013), 621–649. 1, 6

    work page 2013

  17. [17]

    Koml´ os, A

    J. Koml´ os, A. Shokoufandeh, M. Simonovits and E. Szeme r´ edi, The regularity lemma and its applications in graph theory, In: Theoretical Aspects of Computer Science: Advanced Lectures , Springer Berlin Heidelberg (2002), 84–112. 1

    work page 2002

  18. [18]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A short proof of Gowers’ lo wer bound for the regularity lemma, Combinatorica, 36 (2016), 187–194. 1, 1.1, 4.3, 4.9

    work page 2016

  19. [19]

    Moshkovitz and A

    G. Moshkovitz and A. Shapira, A sparse regular approxim ation lemma, Trans. Amer. Math. Soc., to appear. 1, 1.1, 1.1 36

    work page

  20. [20]

    A Tight Bound for Hypergraph Regularity I

    G. Moshkovitz and A. Shapira, A tight bound for hypergra ph regularity I, arXiv 1804.05511. 4, 1.1, 5

    work page internal anchor Pith review Pith/arXiv arXiv

  21. [21]

    Nagle, A

    B. Nagle, A. Poerschke, V. R¨ odl and M. Schacht, Hypergraph regularity and quasi-randomness, Proceedings of the Twentieth Annual ACM-SIAM Symposium on D iscrete Algorithms (2009), 227–235. 1

    work page 2009

  22. [22]

    Nagle, V

    B. Nagle, V. R¨ odl and M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Struct. Alg. 28 (2006), 113–179. 1

    work page 2006

  23. [23]

    R¨ odl, Quasi-randomness and the regularity method i n hypergraphs, Proceedings of the International Congress of Mathematicians (ICM) 1 (2015), 571–599

    V. R¨ odl, Quasi-randomness and the regularity method i n hypergraphs, Proceedings of the International Congress of Mathematicians (ICM) 1 (2015), 571–599. 1

    work page 2015

  24. [24]

    Reiher, V

    C. Reiher, V. R¨ odl and M. Schacht, Embedding tetrahedr a into quasirandom hypergraphs, J. Combin. Theory Ser. B 121 (2016), 229–247. 7

    work page 2016

  25. [25]

    R¨ odl, B

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

    work page 2005

  26. [26]

    R¨ odl, E

    V. R¨ odl, E. Tengan, M. Schacht and N. Tokushige, Density theorems and extremal hypergraph problems, Israel J. Math. 152 (2006), 371–380. 1

    work page 2006

  27. [27]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Regular partitions of hypergra phs: regularity lemmas, Combin. Probab. Comput. 16 (2007), 833–885. 1, 1, 2, 1, 4, 1.1, 6, 5, 5.1, 5.1

    work page 2007

  28. [28]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Regular partitions of hypergraphs: counting lemmas, Combin. Probab. Comput. 16 (2007), 887–901. 1, 5.1, A.1, A.1, 16, 17

    work page 2007

  29. [29]

    R¨ odl and M

    V. R¨ odl and M. Schacht, Regularity lemmas for graphs, F ete of Combinatorics and Computer Science, Bolyai Soc. Math. Stud., 20 (2010), 287–325. 1

    work page 2010

  30. [30]

    R¨ odl and J

    V. R¨ odl and J. Skokan, Regularity lemma for uniform hyp ergraphs, Random Struct. Alg. 25 (2004), 1–42. 1

    work page 2004

  31. [31]

    Roth, On certain sets of integers (II), J

    K.F. Roth, On certain sets of integers (II), J. Lond. Mat h. Soc. 29 (1954), 20–26. 1

    work page 1954

  32. [32]

    Ruzsa and E

    I.Z. Ruzsa and E. Szemer´ edi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolya i 18, Volume II, 939-945. 1

    work page 1976

  33. [33]

    Shelah, Primitive recursive bounds for van der Waerd en numbers, J

    S. Shelah, Primitive recursive bounds for van der Waerd en numbers, J. Amer. Math. Soc. 1 (1989), 683–697. 1

    work page 1989

  34. [34]

    Solymosi, A note on a question of Erd˝ os and Graham, Co mbin

    J. Solymosi, A note on a question of Erd˝ os and Graham, Co mbin. Probab. Comput. 13 (2004), 263–267. 1

    work page 2004

  35. [35]

    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. 1 37

    work page 1975

  36. [36]

    Szemer´ edi, Regular partitions of graphs, In: Proc

    E. Szemer´ edi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS , 1978, 399–401. 1

    work page 1978

  37. [37]

    Tao, A variant of the hypergraph removal lemma, J

    T. Tao, A variant of the hypergraph removal lemma, J. Com bin. Theory Ser. A 113 (2006), 1257–1280. 1

    work page 2006

  38. [38]

    Tao, Szemer´ edi’s regularity lemma revisited, Contrib

    T. Tao, Szemer´ edi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), 8–28. 1

    work page 2006

  39. [39]

    Towsner, σ -algebras for quasirandom hypergraphs, Random Struct

    H. Towsner, σ -algebras for quasirandom hypergraphs, Random Struct. Alg . 50 (2017), 114–

    work page 2017

  40. [40]

    moreover

    7 A Proof of Claim 5.4 A.1 Basic facts In order to prove Claim 5.4 we will need several auxiliary results and definitions. We be gin with the notion of complexes. Henceforth, the rank of a (not necessarily uniform) hypergraph P is maxe∈ P |e|. For r ≥ 2 we denote P (r) = { e ∈ P ⏐ ⏐ |e|= r } and P (1) = V (P ). Definition A.1 (complex). A k-complex ( k ≥ 2)...

    work page