On the size of hereditary classes of graphs (Q1328380)

For a hereditary property \(\mathcal P\) (closed under taking induced subgraphs), let \({\mathcal P}_ n\) denote the \(\mathcal P\) graphs on \(n\) labelled vertices. The growth of \(| {\mathcal P}_ n |\) is studied, and it is shown that certain growth rates are not possible. For example it is shown that if \(\mathcal P\) is a hereditary property such that \(| {\mathcal P}_ n |\) is bounded, then in fact \(| {\mathcal P}_ n | = 0\), 1 or 2. More generally, it is shown that either \(| {\mathcal P}_ n |\) is a constant, \(| {\mathcal P}_ n |\) grows polynomially \((p_ 1(n) \leq | {\mathcal P}_ n| \leq p_ 2(n))\), \(| {\mathcal P}_ n |\) grows exponentially \((c^ n_ 1 \leq | {\mathcal P}_ n | \leq c^ n_ 2\) for \(1 < c_ 1 \leq c_ 2\) and for \(n\) sufficiently large), \(| {\mathcal P}_ n|\) grows factorially \((n^{c_ 1 n} \leq | {\mathcal P}_ n | \leq n^{c_ 2 n}\) for \(0 < c_ 1 \leq c_ 2\) and for \(n\) sufficiently large), or \(| {\mathcal P}_ n|\) grows superfactorially.