Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Regularity lemmas for stable graphs

Authors: M. Malliaris and S. Shelah
Journal: Trans. Amer. Math. Soc. 366 (2014), 1551-1585
MSC (2010): Primary 05C75, 03C45, 03C98
Published electronically: August 29, 2013
MathSciNet review: 3145742
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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 (94j:05112),
  • [2] 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 Hungarian and Russian summaries). MR 0107294 (21 #6019)
  • [3] William Feller, An introduction to probability theory and its applications. Vol. I, Third edition, John Wiley & Sons Inc., New York, 1968. MR 0228020 (37 #3604)
  • [4] 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 (98a:11015),
  • [5] 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 (2008k:03078),
  • [6] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • [7] I. Kaplan and S. Shelah, ``Examples in dependent theories.'' arXiv:1009.5420v1 (2010)
  • [8] 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 (97d:05172)
  • [9] 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 (2012k:05356),
  • [10] Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377-384. MR 1171563 (93d:03039),
  • [11] M. E. Malliaris, The characteristic sequence of a first-order formula, J. Symbolic Logic 75 (2010), no. 4, 1415-1440. MR 2767977 (2012b:03095),
  • [12] M. E. Malliaris, Edge distribution and density in the characteristic sequence, Ann. Pure Appl. Logic 162 (2010), no. 1, 1-19. MR 2720656 (2012d:03074),
  • [13] M. E. Malliaris, Hypergraph sequences as a tool for saturation of ultrapowers, J. Symbolic Logic 77 (2012), no. 1, 195-223. MR 2951637,
  • [14] W. L. Nicholson, On the normal approximation to the hypergeometric distribution, Ann. Math. Statist. 27 (1956), 471-483. MR 0087246 (19,326c)
  • [15] 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 (91k:03085)
  • [16] S. Shelah, ``A dependent dream and recounting types.'' (2009), Paper 950
  • [17] 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 (2005m:03063)
  • [18] 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 (2012a:03002)
  • [19] E. Szemerédi, On sets of integers containing no $ k$ elements in arithmetic progression, Acta Arith. 27 (1975), 199-245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312 (51 #5547)
  • [20] 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.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C75, 03C45, 03C98

Retrieve articles in all journals with MSC (2010): 05C75, 03C45, 03C98

Additional Information

M. Malliaris
Affiliation: Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, Illinois 60637

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

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.
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society