Ramsey graphs induce subgraphs of many different sizes (Q2416519): Difference between revisions

Given a graph \(G=(V;E)\), let \(v(G)\) and \(e(G)\) denote, respectively, the number of vertices and edges of \(G\). For a positive constant \(C\), a graph \(G\) of order \(n\) is called \(C\)-Ramsey if every clique or independent set of \(G\) has size at most \(C \log n\). Let \(\Phi(G)\) denote the set \(\{e(H) \mid H \text{ is an induced subgraph of }G \}\). The main result of this paper is the following theorem. Let \(C, \varepsilon > 0\) be positive real numbers. If an integer \(n\) is sufficiently large, then \(\vert \Phi(G)\vert \geq n^{2 - \varepsilon}\) for every \(C\)-Ramsey graph \(G\) of order \(n\).\par The ratio \(e(G)/\binom{v(G)}{2}\) is called the edge density of \(G\). A graph of order \(n\) is said to be uniformly \(\varepsilon\)-dense if the edge density of any induced subgraph of order at least \(n^{\varepsilon}\) lies between \(\varepsilon\) and \(1 - \varepsilon\). The authors propose the following stronger statement as a conjecture. For any fixed \(\varepsilon > 0\), if \(G\) is a uniformly \(\varepsilon\)-dense graph of order \(n\), then \(\vert \Phi(G)\vert = n^{2 - o(1)}\).