TY - JOUR
T1 - Ramsey Graphs Induce Subgraphs of Many Different Sizes
AU - Narayanan, Bhargav
AU - Sahasrabudhe, Julian
AU - Tomon, István
N1 - Publisher Copyright:
© 2018, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.
PY - 2019/2/1
Y1 - 2019/2/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85041573454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85041573454&partnerID=8YFLogxK
U2 - 10.1007/s00493-017-3755-0
DO - 10.1007/s00493-017-3755-0
M3 - Article
AN - SCOPUS:85041573454
SN - 0209-9683
VL - 39
SP - 215
EP - 237
JO - Combinatorica
JF - Combinatorica
IS - 1
ER -