Sizes of induced subgraphs of Ramsey graphs

Noga Alon, József Balogh, Alexandr Kostochka, Wojciech Samotij

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdo″s, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

Original languageEnglish (US)
Pages (from-to)459-476
Number of pages18
JournalCombinatorics Probability and Computing
Volume18
Issue number4
DOIs
StatePublished - Jul 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Sizes of induced subgraphs of Ramsey graphs'. Together they form a unique fingerprint.

  • Cite this