The number of graphs without forbidden subgraphs (Q1826950): Difference between revisions
From MaRDI portal
Latest revision as of 18:46, 6 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of graphs without forbidden subgraphs |
scientific article |
Statements
The number of graphs without forbidden subgraphs (English)
0 references
6 August 2004
0 references
\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.
0 references
extremal graphs
0 references
speed function
0 references
Szemerédi's regularity lemma
0 references
0 references