Efficient homogeneous partitions and slicewise VC-dimension

Abstract Previous work of the author and Wolf, and independently Chernikov and Towsner, showed that 3 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mn>3</mml:mn> </mml:math> $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 epsilon <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>ϵ</mml:mi> </mml:math> $\epsilon$ -homogeneous partitions of size at most 2 Superscript 2 Super Superscript epsilon Super Super Superscript negative upper K <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:msup> <mml:mi>ϵ</mml:mi> <mml:mrow> <mml:mo>−</mml:mo> <mml:mi>K</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:msup> </mml:mrow> </mml:msup> </mml:math> $2^{2^{\epsilon ^{-K}}}$ , where upper K <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mi>K</mml:mi> </mml:math> $K$ is a constant depending on the slicewise VC-dimension. This is the first in a series of papers about growth of regular partitions of 3 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mn>3</mml:mn> </mml:math> $3$ -uniform hypergraphs. Our main result is a crucial ingredient in the second and third papers in the series, which investigate the growth of two types of regular partitions in hereditary properties of 3 <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content"> <mml:mn>3</mml:mn> </mml:math> $3$ -uniform hypergraphs, namely the weak type first defined by Chung and Haviland–Thomason, and the stronger type first developed by Gowers, and independently, Frankl and Rödl.