2021/11/02 by C. Terry, Jason B. Wolf, Terry, C. +1 · 7 citations
Computer Science · Mathematics · #03C45 #03C98 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Logic (math.LO) #Primary 05C65 #Secondary 11B30
paper · pdf · doi:10.48550/arxiv.2111.01737
openalex publication_date 2021/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Along the way, we show that a hereditary property of 3-uniform hypergraphs is homogeneous (i.e. all regular triads have density near 0 or near 1) if and only it has bounded \textrmVC2-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-uniform hypergraphs admitting the type of regular partitions appearing in work of Fox et al. as those that have bounded slicewise \textrmVC-dimension. This is again analogous to a recent non-quantitative result of Chernikov and Towsner.