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)

Request Permissions   Purchase Content 


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?)

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