Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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.
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
  • MR Author ID: 864805
  • Email:
  • 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:
  • 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:
  • MathSciNet review: 3145742