Persistence and regularity in unstable model theory

The starting point is a question about the structure of Keisler's order, a preorder on theories which compares the difficulty of producing saturated regular ultrapowers. In Chapter 1 we show that Keisler's order reduces to the analysis of types in a finite language, i.e. that the combinatorial barriers to saturation are contained in the parameter spaces of the formulas of T. In Chapter 2 we define the characteristic sequence of hypergraphs ⟨ Pn : n < o⟩ associated to a formula which describe the relevant incidence relations, and develop a general framework for analyzing the complexity of a formula in terms of the complexity of its characteristic sequence.;Specifically, we are interested in analyzing consistent partial types, which correspond to sets A such that An ⊂ Pn for all n. The key issues studied in Chapter 2 are localization and persistence, which describe the difficulty of separating some fixed complex configuration from a complete graph under analysis by progressive restrictions of the base set. We characterize stability and simplicity of ϕ in terms of persistence in the characteristic sequence.;Chapter 3 restricts attention to the behavior of the graph P 2 in the characteristic sequence of a given formula. We ask how subsets of the parameter space can generically interrelate by asking what densities can occur between sufficiently large &egr;-regular pairs A, B ⊂ P1, in the sense of Szemeredi. When the formula is stable, after localization the density must always be 1. In a class including simple theories, after localization the density must approach either 0 or 1. In the absence of strict order, we characterize the property that P1 contains large disjoint &egr;-regular sets of any reasonable density delta in terms of instability of P2.;Chapter 4 observes and explicates a discrepancy between the model-theoretic notion of an infinite random k-partite graph and the finitary version given by Szemeredi regularity, showing that a class of infinite k-partite random graphs which do not admit reasonable finite approximations must have the strong order property SOP3.;Chapters 2-4 take place in a general setting. Chapter 5 describes how the formalism of characteristic sequences may be applied to the analysis of types in ultrapowers.