Submission date: 18 April 2022

Abstract:

A regular partition P for a 3-uniform hypergraph H=(V,E) consists of a partition V=V_1 ∪ ... ∪ V_t and for each ij in {[t]\choose 2}, a partition K_2[V_i,V_j]=P_{ij}^1 ∪ ... ∪ P_{ij}^{l}, such that certain quasirandomness properties hold. The complexity of P is the pair (t,l). In this paper we show that if a 3-uniform hypergraph H has VC_2-dimension at most k, then there is a regular partition P for H of complexity (t,l), where l 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 l 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.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2204.08537: pdf, ps.