An improved bound for regular decompositions of $3$-uniform hypergraphs of bounded $V{C}_2$-dimension

Abstract

A regular partition $\mathcal{P}$ for a $3$-uniform hypergraph $H=(V,E)$ consists of a partition $V=V_1\cup \dots \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 \dots \cup P_{ij}^{\ell }$, such that certain quasirandomness properties hold. The complexity of $\mathcal{P}$ is the pair $(t,\ell )$. In this paper we show that if a $3$-uniform hypergraph $H$ has $V{C}_2$-dimension at most $k$, then there is a regular partition $\mathcal{P}$ 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.

References in corpus (1)

• On n-dependent groups and fields II