Growth of regular partitions 1: Improved bounds for small slicewise VC-dimension

2024/04/01 by Terry, C. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2404.01274

Abstract

This is Part 1 in a series of papers about sizes of regular partitions of 3-uniform hypergraphs. Previous work of the author and Wolf, and independently Chernikov and Towsner, showed that 3-uniform hypergraphs of small slicewise VC-dimension admit homogeneous partitions. The results of Chernikov and Towsner did not produce explicit bounds, while the work of the author and Wolf relied on a strong version of hypergraph regularity, and consequently produced a Wowzer type bound on the size of the partition. This paper gives a new proof of this result, yielding \e-homogeneous partitions of size at most 2^2^ε^-K, where K is a constant depending on the slicewise VC-dimension. This result is a crucial ingredient in Part 2 of the series, which investigates the growth of weak regular partitions in hereditary properties of 3-uniform hypergraphs.

Cited by

• Regularity for hypergraphs with bounded VC₂ dimension

Related

• Efficient homogeneous partitions and slicewise VC-dimension
• Growth of regular partitions 4: strong regularity and the pairs partition
• Growth of regular partitions 2: Weak regularity
• Growth of regular partitions 3: strong regularity and the vertex partition
• Irregular triads in 3-uniform hypergraphs