Sh:978

• Malliaris, M., & Shelah, S. (2014). Regularity lemmas for stable graphs. Trans. Amer. Math. Soc., 366(3), 1551–1585. arXiv: 1102.3904 DOI: 10.1090/S0002-9947-2013-05820-5 MR: 3145742
• Abstract:
  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 Szemerédi’s regularity lemma for such graphs:

  Theorem: Let k_* and therefore k_{**} (a constant \leq 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 \langle A_i : i<i(*)\leq m\rangle of G into at most m pieces, where:

  1. m \leq \frac{1}{\epsilon_0^{4k_{**}}}, for \epsilon_0 = {\rm{min}}\{\epsilon, \frac{1}{2^{4k_{**}+1}}\} 2. for all i,j<i(*), ||A_i|-|A_j||\leq 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 Szemerédi’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.

• Version 2012-03-02_11 (31p) published version (35p)

@article{Sh:978,
 author = {Malliaris, Maryanthe and Shelah, Saharon},
 title = {{Regularity lemmas for stable graphs}},
 journal = {Trans. Amer. Math. Soc.},
 fjournal = {Transactions of the American Mathematical Society},
 volume = {366},
 number = {3},
 year = {2014},
 pages = {1551--1585},
 issn = {0002-9947},
 mrnumber = {3145742},
 mrclass = {05C75 (03C45 03C98)},
 doi = {10.1090/S0002-9947-2013-05820-5},
 note = {\href{https://arxiv.org/abs/1102.3904}{arXiv: 1102.3904}},
 arxiv_number = {1102.3904}
}