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 . Erdős, Faudree and Sós conjectured that every c -Ramsey graph with n vertices contains Ω( n 5/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 Ω( n 5/2 ). We prove an Ω( n 2.3693 ) lower bound.
No takes yet. Share an insight, caveat, or question.
Alon et al. (2009) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: