### Regularity lemmas for stable graphs

by Malliaris and Shelah. [MiSh:978]

Transactions American Math Soc, 2014

Let G be a finite graph with the non- k_*-order
property (essentially, a uniform finite bound on the size of
an induced
sub-half-graph). The main result of the paper applies
model-theoretic arguments to obtain a stronger version of
Szemeredi's regularity lemma for such graphs:
Theorem: Let k_* and therefore k_{**} (a constant <=
2^{k_*+2}) be given. Let G be a graph with the
non- k_*-order property.
Then for any epsilon >0 there exists m=m(epsilon) such
that if G is sufficiently large, there is a partition
< A_i : i<i(*) <= m> of G into at most m
pieces, where:
1. m <= frac {1}{epsilon_0^{4k_{**}}}, for epsilon_0
= {{min}} {epsilon, frac {1}{2^{4k_{**}+1}}}
2. for all i,j<i(*), ||A_i|-|A_j|| <= 1
3. all of the pairs (A_i, A_j) are (epsilon,
epsilon)-uniform, meaning that for some truth value {textbf {t}}=
{textbf {t}}(A_i,A_j) in {0,1}, for all but < epsilon |A_i| of
the elements of |A_i|, for all but < zeta |A_j| of the
elements of A_j, (aRb) equiv ({textbf {t}}(A_i,A_j)=1)
4. all of the pieces A_i are epsilon-excellent
(an indivisibility condition, Definition (6.2) below)
% end {theorem}
We also give several other partition theorems for this class
of graphs, described in the Introduction, and discuss
extensions to graphs without the independence
property. Motivation for this work comes from a coincidence of
model-theoretic and graph-theoretic ideas. Namely, it was
known that the ``irregular pairs'' in the statement of
Szemeredi's regularity lemma cannot be eliminated, due to
the counterexample of half-graphs. The results of this paper
show in what sense this counterexample is the essential
difficulty. The proof is largely model-theoretic: arbitrarily
large half-graphs coincide with model-theoretic instability,
so in their absence, structure theorems and technology from
stability theory apply.

Back to the list of publications