On a Ramsey type theorem (Q2553974)

Let \(\bar G\) denote the complement of the graph \(G\), and let \(K_n\) denote the complete graph on \(n\) vertices. The main result of this paper is the following: Theorem 2. Let \(G(n,r)\) be a graph of \(n\) vertices with \(r<{n^2 \over k}\) edges. Then there is a positive constant \(c\) such that for \(s<c{k \over \log k} \log n\), either \(\overline{G(n,r)}\) or \(G(n,r)\) contains \(K_s\) as a subgraph. This result is shown to be best possible as far as the order of magnitude is concerned.