Ramsey Graphs Induce Subgraphs of Many Different Sizes

Bhargav Narayanan, Julian Sahasrabudhe, István Tomon

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A graph on n vertices is said to be C-Ramsey if every clique or independent set of the graph has size at most C logn. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed C > 0, every C-Ramsey graph on n vertices induces subgraphs of at least n 2-o(1) distinct sizes. This near-optimal result is closely related to two unresolved conjectures, the first due to Erdős and McKay and the second due to Erdős, Faudree and Sós, both from 1992.

Original languageEnglish (US)
Pages (from-to)215-237
Number of pages23
JournalCombinatorica
Volume39
Issue number1
DOIs
StatePublished - Feb 1 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Ramsey Graphs Induce Subgraphs of Many Different Sizes'. Together they form a unique fingerprint.

Cite this