Persistence and NIP in the characteristic sequence.

Authors: M. E. Malliaris
Subjects: Logic
link: http://arxiv.org/abs/0908.4111
Abstract

For a first-order formula $\phi(x;y)$ we introduce and study the
characteristic sequence $<P_n : n < \omega>$ of hypergraphs defined by
$P_n(y_1,...,y_n) := (\exists x) \bigwedge_{i \leq n} \phi(x;y_i)$. We show
that combinatorial and classification theoretic properties of the
characteristic sequence reflect classification theoretic properties of
$\varphi$ and vice versa. Specifically, we show that some tree properties are
detected by the presence of certain combinatorial configurations in the
characteristic sequence while other properties such as instability and the
independence property manifest themselves in the persistence of complicated
configurations under localization.