Distality to and from combinatorics

In this thesis, we demonstrate the intimate connection between the model-theoretic notion of distality and concepts from combinatorics: developments in distality both lead to and come from those in combinatorics.

Chapter 3 demonstrates the from direction. We prove that expansions of Presburger arithmetic by a predicate R ⊆ ℕ are distal when R satisfies certain arithmetic combinatorial properties. We do so by constructing distal decompositions (or strong honest definitions), a form of cell decomposition with desirable combinatorial properties.

Chapter 4 demonstrates the to direction. We prove that relations definable in a distal structure have better bounds for the Zarankiewicz problem, a classical problem in extremal combinatorics. In fact, we prove that these bounds are enjoyed by any relation satisfying an improved version of Szemerédi regularity lemma, a classical theorem in extremal combinatorics. Thus, motivated by distality, we discover an interaction between two areas of extremal combinatorics.

Chapter 5 demonstrates both the to and the from directions. We show that the developments of higher-arity distality and higher-arity (hypergraph) regularity lemmas inform one another. The centrepiece of the chapter is a homogeneous hypergraph regularity lemma that we derive for structures satisfying higher-arity distality. In the quest for this, we develop strong honest definitions for higher-arity distality, whose efficacy is supported by the regularity lemma.