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)

 
 

 

Proof of a conjecture on induced subgraphs of Ramsey graphs


Authors: Matthew Kwan and Benny Sudakov
Journal: Trans. Amer. Math. Soc.
MSC (2010): Primary 05C55; Secondary 05D10
DOI: https://doi.org/10.1090/tran/7729
Published electronically: December 7, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An $ n$-vertex graph is called $ C$-Ramsey if it has no clique or independent set of size $ C\log n$. All known constructions of Ramsey graphs involve randomness in an essential way, and there is an ongoing line of research toward showing that in fact all Ramsey graphs must obey certain ``richness'' properties characteristic of random graphs. More than 25 years ago, Erdős, Faudree, and Sós conjectured that in any $ C$-Ramsey graph there are $ \Omega (n^{5/2})$ induced subgraphs, no pair of which have the same numbers of vertices and edges. Improving on earlier results of Alon, Balogh, Kostochka, and Samotij, in this paper we prove this conjecture.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C55, 05D10

Retrieve articles in all journals with MSC (2010): 05C55, 05D10


Additional Information

Matthew Kwan
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
Email: mattkwan@stanford.edu

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zürich, Switzerland
Email: benjamin.sudakov@math.ethz.ch

DOI: https://doi.org/10.1090/tran/7729
Received by editor(s): March 9, 2018
Received by editor(s) in revised form: October 9, 2018
Published electronically: December 7, 2018
Additional Notes: This research was done while the first-named author was working at ETH Zurich, and is supported in part by SNSF project 178493.
Research supported in part by SNSF grant 200021-175573
Article copyright: © Copyright 2018 American Mathematical Society