### 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)
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