The penultimate rate of growth for graph properties (Q5937420)

A hereditary graph property is an infinite family of (labelled) graphs closed under isomorphism and induced subgraphs. The growth rate of such properties, that is the numbers of graphs with \(n\) vertices belonging to a fixed property, has been object of considerable study; it is known that not all growth rates can occur, and that some growth rates imply structure theorems for the properties. The subject of this paper are hereditary graph properties with growth rate near the top: in the range \(n^{(1+o(1))n}\) to \(2^{({1\over 2} +o(1))n^2}\). The authors show some restrictions for the growth rates in these intervals: especially for monotone properties (closed under arbitrary subgraphs) they show that if the growth rate is \(2^{o(n^2)}\), then it is \(2^{n^{2-(1/k)+o(1)}}\) for some \(k\), which they conjecture to hold for all hereditary properties. Then they construct hereditary graph properties whose growth rate oscillates almost across that whole interval, giving a counterexample to the existence of some limits conjectured by \textit{E. R. Scheinerman} and \textit{J. Zito} [J. Comb. Theory, Ser. B 61, No. 1, 16-39 (1994; Zbl 0811.05048)].