A regular partition 𝒫 of a 3-uniform hypergraph H=(V,E) consists of a partition V=V1 ∪ … ∪ Vt and for each ij ∈ [t] choose 2, a partition Vi × Vj = Pij1 ∪ … ∪ Pij𝓁 so that certain quasirandomness properties hold. The complexity of 𝒫 is the pair (t,𝓁). In this talk, we present results which show that if a 3-uniform hypergraph H has VC2-dimension at most k, then there is a regular partition for H of complexity (t,𝓁), where 𝓁 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 𝓁 is of Wowzer type. This result 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.
This video was produced by the Simons Institute, and forms part of the workshop Structural Results.
