Hereditary and monotone properties of combinatorial structures
Béla Bollobás · Cambridge University Press eBooks · 2007
A hereditary property of graphs is a collection of (isomorphism classes of) graphs which is closed under taking induced graphs, and contains arbitrarily large structures. Given a family F of graphs, the family P ( F ) of graphs containing no member of F as an induced subgraph is a hereditary property, and every hereditary property of graphs arises in this way. A hereditary property of other combinatorial structures is defined analogously. A property is monotone if it is closed under taking (not necessarily induced) substructures. Given a property P , we write P n for the number of distinct structures with vertices labelled 1, …, n , and call the function n ↦ | P n | the labelled speed of P . Similarly, the unlabelled speed is n ↦ | P n |, where P n is the set of distinct structures with n unlabelled vertices. The study of hereditary properties is on the borderline of extremal, enumerative, and probabilistic combinatorics. Thus, for a family F of graphs, the problem of determining the speed of P ( F ) is a natural extension of the basic question in extremal graph theory concerned with the maximal number of edges in a graph of order n containing no member of F as a subgraph. For many a combinatorial structure (graphs, posets, partitions, words, etc.), there is a surprising phase transition: the speed jumps from one range to a much higher one. Thus the speed of a property is either not much larger than a certain function f ( n ) or is at least as large as a function F which is much larger than f .