Open access
Date
2020-03Type
- Journal Article
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 towards showing that in fact all Ramsey graphs must obey certain “richness” properties characteristic of random graphs. Motivated by an old problem of Erdos and McKay, recently Narayanan, Sahasrabudhe, ˝ and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of Θ(n2) different sizes. In this paper we prove this conjecture. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000352764Publication status
publishedExternal links
Journal / series
International Mathematics Research NoticesVolume
Pages / Article No.
Publisher
Oxford University PressOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.More
Show all metadata