Erdős and Rényi conjecture (Q1268624)

A conjecture of Erdős and Rényi is confirmed. It is shown that for any positive real number \(c_1 > 0\) there is a \(c_2 > 0\) such that if a graph \(G\) of order \(n\) does not contain a complete graph or an independent set with \(c_1 \log n\) vertices, then \(G\) contains at least \(2^{c_2n}\) nonisomorphic induced subgraphs.