Irregular Triads in 3-Uniform Hypergraphs

Abstract

Over the past several years, numerous authors have explored model theoretically motivated combinatorial conditions that ensure that a graph has an efficient regular decomposition in the sense of Szemerédi. In this paper we set out a research program that explores a corresponding set of questions for 3-uniform hypergraphs, a setting in which useful notions of regularity are significantly more intricate. The main results in this paper concern certain combinatorial properties which arose as natural higher-order generalizations of the order property in parallel work of the authors in the arithmetic setting. Interpreted in the context of 3-uniform hypergraphs, these are tightly connected to the nature of irregular triads. Specifically, we show that a hereditary property of 3-uniform hypergraphs admits regular decompositions with so-called “linear error” if and only if it does not have the functional order property ( F O P 2 FOP_2 ). Along the way, we show that a hereditary property of 3 3 -uniform hypergraphs is homogeneous (i.e. all regular triads have density near 0 0 or near 1 1 ) if and only it has bounded V C 2 VC_2 -dimension. This provides a quantitative version of a recent result of Chernikov and Towsner. We also address several questions arising from prior work on tame regularity in hypergraphs. In particular, we characterize the hereditary properties of 3 3 -uniform hypergraphs admitting the type of regular partitions appearing in work of Fox et al. as those that have bounded slicewise V C VC -dimension. This is again analogous to a recent non-quantitative result of Chernikov and Towsner.