The Penultimate Rate of Growth for Graph Properties

AbstractGiven a property P of graphs, write Pnfor the set of graphs with vertex set [ n ] having property P. We call | Pn| the speed of P. Recent research has shown that the speed of a monotone or hereditary property P can be a constant, polynomial, or exponential function of n, and the structure of the graphs in P can then be well described. Similarly, | Pn| can be of the form n(1−1/k+o(1))nor 2(1−1/k+o(1))n2/2for some positive integer k> 1 and the properties can be described and have well-behaved speeds. In this paper, we discuss the behavior of properties with speeds between these latter bounds, i.e., between n(1+o(1))nand 2(1/2+o(1))n2/2