  The characteristic sequence of hypergraphs $<P_n : n<\omega>$ 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.
