Number of graphs with a forbidden subgraph
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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.
|