Julia Wolf University of Cambridge
Szemerédi’s celebrated regularity lemma states, roughly speaking, that the vertex set of any large graph can be partitioned into a bounded number of sets in such a way that all but a small proportion of pairs of sets from this partition induce a ~regular~ graph. The example of the half-graph shows that the existence of irregular pairs cannot be ruled out in general. Recognising the half-graph as an instance of the so-called ‘order property’ from model theory, Malliaris and Shelah proved in 2014 that if one assumes that the large graph contains no half-graphs of a fixed size (as induced bipartite subgraphs), then it is possible to obtain a regularity partition with no irregular pairs. In addition, the number of parts of the partition is polynomial in the regularity parameter, and the density of each regular pair is either close to zero or close to 1. This beautiful result exemplifies a long-standing theme in model theory, namely that so-called stable structures (which are characterised by an absence of large instances of the order property), are extremely well-behaved. In this talk I will present recent joint work with Caroline Terry (OSU), in which we define a higher-arity generalisation of the order property and prove that its absence characterises those large 3-uniform hypergraphs whose regularity decompositions allow for particularly good control of the irregular triads.