A note on the Erdős-Hajnal property for stable graphs
HTML articles powered by AMS MathViewer
- by Artem Chernikov and Sergei Starchenko PDF
- Proc. Amer. Math. Soc. 146 (2018), 785-790 Request permission
Abstract:
In this note we give a proof of the Erdős–Hajnal conjecture for families of finite (hyper-)graphs without the $m$-order property. This theorem is in fact implicitly proved by M. Malliaris and S. Shelah (2014), however we use a new technique of independent interest combining local stability and pseudo-finite model theory.References
- Artem Chernikov and Sergei Starchenko, Regularity lemma for distal structures, Journal of the European Mathematical Society, accepted (arXiv:1507.01482) (2015).
- Maria Chudnovsky, The Erdös-Hajnal conjecture—a survey, J. Graph Theory 75 (2014), no. 2, 178–190. MR 3150572, DOI 10.1002/jgt.21730
- P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Applied Mathematics (1989).
- Jacob Fox and Benny Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), no. 6, 1771–1800. MR 2455625, DOI 10.1016/j.aim.2008.07.009
- Ehud Hrushovski, On pseudo-finite dimensions, Notre Dame J. Form. Log. 54 (2013), no. 3-4, 463–495. MR 3091666, DOI 10.1215/00294527-2143952
- M. Malliaris and S. Shelah, Regularity lemmas for stable graphs, Trans. Amer. Math. Soc. 366 (2014), no. 3, 1551–1585. MR 3145742, DOI 10.1090/S0002-9947-2013-05820-5
- 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
Additional Information
- Artem Chernikov
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095-1555
- Email: chernikov@math.ucla.edu
- Sergei Starchenko
- Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556
- MR Author ID: 237161
- Email: Starchenko.1@nd.edu
- Received by editor(s): December 10, 2016
- Published electronically: October 25, 2017
- Additional Notes: The first author was partially supported by ValCoMo (ANR-13-BS01-0006), by the Fondation Sciences Mathematiques de Paris (FSMP) and by the Investissements d’avenir program (ANR-10-LABX-0098)
The second author was partially supported by the NSF Research Grant DMS-1500671 - Communicated by: Mirna Džamonja
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 146 (2018), 785-790
- MSC (2010): Primary 03C45, 05C35, 05C69
- DOI: https://doi.org/10.1090/proc/13626
- MathSciNet review: 3731711