Tower-growth conjecture for hereditary 3-uniform hypergraph properties

About 2 years old · traced to

Let H\mathcal{H} be a hereditary property of 33-uniform hypergraphs with infinite VC⁡2\operatorname{VC}_2-dimension. Let LH(ϵ1,ϵ2)L_{\mathcal{H}}(\epsilon_1,\epsilon_2) denote the associated regularity growth function, and let TwTw denote the tower function. Tower-growth conjecture. There exist a function ϵ2:N→(0,1]\epsilon_2:\mathbb{N}\rightarrow (0,1] and a constant C>0C>0 such that

LH(ϵ1,ϵ2)≥Tw(ϵ1−C).L_{\mathcal{H}}(\epsilon_1,\epsilon_2)\geq Tw(\epsilon_1^{-C}).

This conjecture proposes that the lower bound in the unbounded-VC⁡2\operatorname{VC}_2 range can be improved from exponential to at least tower growth; the paper suggests that techniques from its proof combined with bipartite lower-bound constructions for graph regularity may establish it. The source does not give evidence of a resolution.

References

Primary source

C. Terry, “Growth of regular partitions 4: strong regularity and the pairs partition”, arXiv:2404.02030 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.