Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A note on the Erdős-Hajnal property for stable graphs


Authors: Artem Chernikov and Sergei Starchenko
Journal: Proc. Amer. Math. Soc. 146 (2018), 785-790
MSC (2010): Primary 03C45, 05C35, 05C69
DOI: https://doi.org/10.1090/proc/13626
Published electronically: October 25, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

  • [1] Artem Chernikov and Sergei Starchenko, Regularity lemma for distal structures, Journal of the European Mathematical Society, accepted (arXiv:1507.01482) (2015).
  • [2] Maria Chudnovsky, The Erdös-Hajnal conjecture--a survey, J. Graph Theory 75 (2014), no. 2, 178-190. MR 3150572, https://doi.org/10.1002/jgt.21730
  • [3] P. Erdős and A. Hajnal, Ramsey-type theorems, Discrete Applied Mathematics (1989).
  • [4] Jacob Fox and Benny Sudakov, Induced Ramsey-type theorems, Adv. Math. 219 (2008), no. 6, 1771-1800. MR 2455625, https://doi.org/10.1016/j.aim.2008.07.009
  • [5] Ehud Hrushovski, On pseudo-finite dimensions, Notre Dame J. Form. Log. 54 (2013), no. 3-4, 463-495. MR 3091666, https://doi.org/10.1215/00294527-2143952
  • [6] M. Malliaris and S. Shelah, Regularity lemmas for stable graphs, Trans. Amer. Math. Soc. 366 (2014), no. 3, 1551-1585. MR 3145742, https://doi.org/10.1090/S0002-9947-2013-05820-5
  • [7] 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

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03C45, 05C35, 05C69

Retrieve articles in all journals with MSC (2010): 03C45, 05C35, 05C69


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
Email: Starchenko.1@nd.edu

DOI: https://doi.org/10.1090/proc/13626
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
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society