Induced subgraphs of Ramsey graphs with many distinct degrees (Q885296)

It is shown that if \(G\) is a graph of order \(n\) such that \(\max\{\alpha(G), \omega(G)\} \leq C \log n\) for some constant \(C\), then \(G\) contains an induced subgraph of order \(\alpha n\) with \(\beta \sqrt{n}\) vertices of different degrees, where \(\alpha\) and \(\beta\) depend only on \(C\). This proves a conjecture of Erdős, Faudree, and Sós appearing in several of the survey papers of Erdős. It is also shown under the same conditions that there exists \(\Omega(n{3/2})\) induced subgraphs \(H\) of \(G\) with distinct pairs \((| V(H)| , | E(H)| )\). An outline of a proof of a corresponding result for tournaments is also given. If \(T\) is a tournament with trans\((T) \leq C\log n\) (where trans\((T)\) is the order of the largest transitive subtournament of \(T\)), then \(T\) contains an induced subtournament of order \(\alpha n\) with \(\beta \sqrt{n}\) vertices of different degrees, where \(\alpha\) and \(\beta\) depend only on \(C\).