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