Ramsey graphs induce subgraphs of quadratically many sizes
arXiv:1711.02937
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 Erdős and McKay, recently Narayanan, Sahasrabudhe and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey graph induces subgraphs of different sizes. In this paper we prove this conjecture.
arXiv commentCorrected an oversight in the proof, drawn to our attention by Mantas Baksys and Xuanang Chen