Abstract

A regular partition $\mathcal{𝒫}$ for a $3$-uniform hypergraph $H=(V,E)$ consists of a partition $V=V_1\cup \cdots \cup V_t$ and for each $ij\in \left(\genfrac{}{}{0ex}{}{[t]}{2}\right)$, a partition $K_2[V_i,V_j]=P_{ij}^1\cup \cdots \cup P_{ij}^{\ell }$ such that certain quasirandomness properties hold. The complexity of $\mathcal{𝒫}$ is the pair $(t,\ell )$. In this paper we show that if a $3$-uniform hypergraph $H$ has ${\mathrm{VC}<!--FUNCTION\; APPLICATION-->}_2$-dimension at most $k$, then there is such a regular partition $\mathcal{𝒫}$ for $H$ of complexity $(t,\ell )$, where $\ell$ is bounded by a polynomial in the degree of regularity. This is a vast improvement on the bound arising from the proof of this regularity lemma in general, in which the bound generated for $\ell$ is of Wowzer type. This can be seen as a higher arity analogue of the efficient regularity lemmas for graphs and hypergraphs of bounded VC-dimension due to Alon–Fischer–Newman, Lovász–Szegedy, and Fox–Pach–Suk.

Keywords

Mathematical Subject Classification

Milestones

Authors