Edge distribution and density in the characteristic sequence

Abstract

The characteristic sequence of hypergraphs $<P_n:n<\omega >$ associated to a formula $\varphi (x;y)$, introduced in [arXiv:0908.4111], is defined by $P_n(y_1,...y_n)=(\exists x){\bigwedge }_{i\le n}\varphi (x;y_i)$. This paper continues the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemerédi's celebrated regularity lemma, can be naturally applied to the study of model-theoretic complexity via the characteristic sequence. Specifically, we relate classification-theoretic properties of $\varphi$ and of the $P_n$ (considered as formulas) to density between components in Szemerédi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemerédi regularity to calibrate model-theoretic notions of independence by describing the depth of independence of a constellation of sets and showing that certain failures of depth imply Shelah's strong order property $SO{P}_3$; this sheds light on the interplay of independence and order in unstable theories.

References in corpus (2)

• Limits of Hypergraphs, Removal and Regularity Lemmas. A Non-standard Approach
• Persistence and NIP in the characteristic sequence

Cited by in corpus (5)

• A new look at interpretability and saturation
• Notes on the stable regularity lemma
• Properties of independence in ${\mathrm{NSOP}}_3$ theories
• Model theory and ultraproducts
• Regularity lemmas for stable graphs