The unlabelled speed of a hereditary graph property

A property of graphs is a collection P of graphs closed under isomorphism; we call P hereditary if it is closed under taking induced subgraphs. Given a property P, we write Pn for the set of graphs in P with vertex set [n] = {1, ..., n}, and Pn for the isomorphism classes of graphs of order n that are in P. The cardinality | Pn | is the labelled speed of P and | Pn | is the unlabelled speed. In the last decade numerous results have been proved about the labelled speeds of hereditary properties, with emphasis on the striking phenomenon that only certain speeds are possible: there are various pairs of functions (f (n), F (n)), with F (n) much larger than f (n), such that if the labelled speed is infinitely often larger than f (n) then it is also larger than F (n) for all sufficiently large values of n. Putting it concisely: the speed jumps from f (n) to F (n). Recent work on hereditary graph properties has shown that large and small labelled speeds of hereditary graph properties do jump. The aim of this paper is to study the unlabelled speed of a hereditary property, with emphasis on jumps. Among other results, we shall show that the unlabelled speed of a hereditary graph property is either of polynomial order or at least S (n), the number of ways of partitioning a set with n indistinguishable elements. © 2008 Elsevier Inc. All rights reserved