Edge distribution and density in the characteristic sequence

Details Edge distribution and density in the characteristic sequence Edge distribution and density in the characteristic sequence

2009-09-14

arxiv.org/abs/0909.2467v1

Annals of Pure and Applied Logic, Volume 162, Issue 1, October 2010, Pages 1-19

Mathematics

Logic

Scientific paper

10.1016/j.apal.2010.06.009

The characteristic sequence of hypergraphs $$ associated to a formula $\phi(x;y)$, introduced in [arXiv:0908.4111], is defined by $P_n(y_1,... y_n) = (\exists x) \bigwedge_{i\leq n} \phi(x;y_i)$. This paper continues the study of characteristic sequences, showing that graph-theoretic techniques, notably Szemer\'edi'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 $\phi$ and of the $P_n$ (considered as formulas) to density between components in Szemer\'edi-regular decompositions of graphs in the characteristic sequence. In addition, we use Szemer\'edi 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 $SOP_3$; this sheds light on the interplay of independence and order in unstable theories.

Affiliated with

Also associated with

No associations

Rating

Edge distribution and density in the characteristic sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Edge distribution and density in the characteristic sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge distribution and density in the characteristic sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564264