The number of graphs without forbidden subgraphs (Q1826950): Difference between revisions

\textit{P. Erdős, P. Frankl} and \textit{V. Rödl} [Graphs Comb. 2, 113--121 (1986; Zbl 0593.05038)] proved that for a family \({\mathcal L}\) of graphs the number of labeled graphs of order \(n\) that do not contain a graph in \({\mathcal L}\) as a subgraph is \(2^{\frac{1}{2}\left(1-\frac{1}{p}\right)n^2+o(n^2)}\) where \(p=\min_{L\in {\mathcal L}}\chi(L)-1\). In the present paper the authors study how much the error term \(o(n^2)\) in the exponent of the above expression can be improved and they establish as their main result that \(o(n^2)\) can be replaced by \(O(n^{2-\gamma})\) for some \(\gamma=\gamma({\mathcal L})>0\). Their result is essentially best-possible and their proof relies on Szemerédi's regularity lemma and the stability theorem of Erdős and Simonovits.