Number of graphs with a forbidden subgraph

A conjecture on enumerating graphs with a forbidden subgraph
(proposed by Erdös, Kleitman and Rothschild [1])

Let \(t(n,H)\) denote the Turán number of \(H\), that is the largest integer \(m\) such that there is a graph \(G\) on \(n\) vertices and \(m\) edges which does not contain \(H\) as a subgraph. Denote by \(f_n(H)\) the number of (labelled) graphs on $n$ vertices which do not contain \(H\) as a subgraph. Then \[ f_n(H) \leq 2^{(1+o(1)) t(n,H)}.\]

In [1], this was proved for the case that \( H\) is a complete graph. In general, if \( H\) is not bipartite, this conjecture was proved by Erdös, Frankl and Rödl \( ^{[2]}\). For the bipartite case, it is open even for \( H=C_4\). It is well known that \( t(n,C_4) = (1/2+o(1)) n^{3/2}\). On the other hand, Kleitman and Winston \( ^{[3]}\) proved

\(\displaystyle f_n(C_4) \leq 2 ^{cn^{3/2}}. \)

Kleitman and Wilson \( ^{[4]}\) proved that \( f_n(C_{2k}) < 2^{c n^{1+1/k}} \) for \( k=3,4,5\) and Kreuter \( ^{[5]}\) showed that the number of graphs on \( n\) vertices which do not contain \( C_{2j}\) for \( j=2,\dots,k\) is at most \( 2^{(c_k+o(1)) n^{1+1/k}}\) where \( c_k = .54 k +3/2\).


Bibliography
1 P. Erdös, D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of \( K_n\)-free graphs (Italian summary), Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, 19-27, Accad. Naz. Lincei, Rome, 1976.

2 P. Erdös, P. Frankl and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), 113-121.

3 D. J. Kleitman and K. J. Winston, On the number of graphs without \( 4\)-cycles, Discrete Math. 41 (1982) 167-172.

4 D. J. Kleitman and D. B. Wilson, On the number of graphs which lack small cycles, preprint.

5 B. Kreuter, Extremale und Asymptotische Graphentheorie für verbotene bipartite Untergraphen, Diplomarbeit, Forschungsinstitut für Diskrete Mathematik, Universität Bonn, January, 1994.