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