MODNET

Research Training Network in Model Theory

Publications > Preprint server > Preprint Number 2169
Preprint Number 2169
2169. C. Terry An improved bound for regular decompositions of 3-uniform hypergraphs
of bounded VC_2-dimension E-mail: 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: |

Last updated: May 2 2022 11:20 | Please send your corrections to: |