## Regularity lemmas for stable graphs

HTML articles powered by AMS MathViewer

- by M. Malliaris and S. Shelah PDF
- Trans. Amer. Math. Soc.
**366**(2014), 1551-1585 Request permission

## Abstract:

We develop a framework in which Szemerédi’s celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In one direction, we address a problem from the classical Szemerédi theory. 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 (i.e., the order property, corresponding to model-theoretic instability). We show that half-graphs are the*only*essential difficulty, by giving a much stronger version of Szemerédi’s Regularity Lemma for models of stable theories of graphs (i.e. graphs with the non-$k_*$-order property), in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. In the other direction, we take a more model-theoretic approach, and give several new Szemerédi-type partition theorems for models of stable theories of graphs. The first theorem gives a partition of any such graph into indiscernible components, meaning here that each component is either a complete or an empty graph, whose interaction is strongly uniform. This relies on a finitary version of the classic model-theoretic fact that stable theories admit large sets of indiscernibles, by showing that in models of stable theories of graphs one can extract much larger indiscernible sets than expected by Ramsey’s theorem. The second and third theorems allow for a much smaller number of components at the cost of weakening the “indivisibility” condition on the components. We also discuss some extensions to graphs without the independence property. All graphs are finite and all partitions are equitable, i.e. the sizes of the components differ by at most 1. In the last three theorems, the number of components depends on the size of the graph; in the first theorem quoted, this number is a function of $\epsilon$ only as in the usual Szemerédi Regularity Lemma.

## References

- N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster,
*The algorithmic aspects of the regularity lemma*, J. Algorithms**16**(1994), no. 1, 80–109. MR**1251840**, DOI 10.1006/jagm.1994.1005 - Paul Erdős and Alfréd Rényi,
*On the central limit theorem for samples from a finite population*, Magyar Tud. Akad. Mat. Kutató Int. Közl.**4**(1959), 49–61 (English, with Russian and Hungarian summaries). MR**107294** - William Feller,
*An introduction to probability theory and its applications. Vol. I*, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0228020** - W. T. Gowers,
*Lower bounds of tower type for Szemerédi’s uniformity lemma*, Geom. Funct. Anal.**7**(1997), no. 2, 322–337. MR**1445389**, DOI 10.1007/PL00001621 - Ehud Hrushovski, Ya’acov Peterzil, and Anand Pillay,
*Groups, measures, and the NIP*, J. Amer. Math. Soc.**21**(2008), no. 2, 563–596. MR**2373360**, DOI 10.1090/S0894-0347-07-00558-9 - Wilfrid Hodges,
*Model theory*, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR**1221741**, DOI 10.1017/CBO9780511551574 - I. Kaplan and S. Shelah, “Examples in dependent theories.” arXiv:1009.5420v1 (2010)
- J. Komlós and M. Simonovits,
*Szemerédi’s regularity lemma and its applications in graph theory*, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR**1395865** - László Lovász and Balázs Szegedy,
*Regularity partitions and the topology of graphons*, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 415–446. MR**2815610**, DOI 10.1007/978-3-642-14444-8_{1}2 - Michael C. Laskowski,
*Vapnik-Chervonenkis classes of definable sets*, J. London Math. Soc. (2)**45**(1992), no. 2, 377–384. MR**1171563**, DOI 10.1112/jlms/s2-45.2.377 - M. E. Malliaris,
*The characteristic sequence of a first-order formula*, J. Symbolic Logic**75**(2010), no. 4, 1415–1440. MR**2767977**, DOI 10.2178/jsl/1286198155 - M. E. Malliaris,
*Edge distribution and density in the characteristic sequence*, Ann. Pure Appl. Logic**162**(2010), no. 1, 1–19. MR**2720656**, DOI 10.1016/j.apal.2010.06.009 - M. E. Malliaris,
*Hypergraph sequences as a tool for saturation of ultrapowers*, J. Symbolic Logic**77**(2012), no. 1, 195–223. MR**2951637**, DOI 10.2178/jsl/1327068699 - W. L. Nicholson,
*On the normal approximation to the hypergeometric distribution*, Ann. Math. Statist.**27**(1956), 471–483. MR**87246**, DOI 10.1214/aoms/1177728270 - S. Shelah,
*Classification theory and the number of nonisomorphic models*, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR**1083551** - S. Shelah, “A dependent dream and recounting types.” (2009) http://shelah.logic.at, Paper 950
- Saharon Shelah,
*Classification theory for elementary classes with the dependence property—a modest beginning*, Sci. Math. Jpn.**59**(2004), no. 2, 265–316. Special issue on set theory and algebraic model theory. MR**2062198** - Saharon Shelah,
*Classification theory for abstract elementary classes. Vol. 2*, Studies in Logic (London), vol. 20, College Publications, London, 2009. Mathematical Logic and Foundations. MR**2649290** - E. Szemerédi,
*On sets of integers containing no $k$ elements in arithmetic progression*, Acta Arith.**27**(1975), 199–245. MR**369312**, DOI 10.4064/aa-27-1-199-245 - V. Vapnik and A. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities.” Theory of Probability and its Applications, vol. XVI, no. 2 (1971) 264-280.

## Additional Information

**M. Malliaris**- Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637
- MR Author ID: 864805
- Email: mem@math.uchicago.edu
**S. Shelah**- Affiliation: Einstein Institute of Mathematics, Edmond J. Safra Campus, Givat Ram, The Hebrew University of Jerusalem, Jerusalem, 91904, Israel – and – Department of Mathematics, Hill Center - Busch Campus, Rutgers, The State University of New Jersey, 110 Frelinghuysen Road, Piscataway, New Jersey 08854-8019
- MR Author ID: 160185
- ORCID: 0000-0003-0462-3152
- Email: shelah@math.huji.ac.il
- Received by editor(s): April 28, 2011
- Received by editor(s) in revised form: March 2, 2012
- Published electronically: August 29, 2013
- Additional Notes: The first author thanks the NSF for partial support of this research via grant DMS-1001666, and for partial support of her visit to Rutgers in 2010 via the second author’s grant DMS-0600940

The second author thanks the Israel Science Foundation for partial support of this research via grant 710/07. This is paper 978 in his list of publications. - © Copyright 2013 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**366**(2014), 1551-1585 - MSC (2010): Primary 05C75, 03C45, 03C98
- DOI: https://doi.org/10.1090/S0002-9947-2013-05820-5
- MathSciNet review: 3145742