Book contents
- Frontmatter
- Contents
- Preface
- 1 Hereditary and monotone properties of combinatorial structures
- 2 Ordering classes of matrices of 0's and 1's
- 3 Cycle decompositions of complete graphs
- 4 Excluding induced subgraphs
- 5 Designs and topology
- 6 The number of points on an algebraic curve over a finite field
- 7 On the efficient approximability of constraint satisfaction problems
- 8 The combinatorics of cryptographic key establishment
- 9 Bandwidth of graphic matroids
1 - Hereditary and monotone properties of combinatorial structures
Published online by Cambridge University Press: 16 March 2010
- Frontmatter
- Contents
- Preface
- 1 Hereditary and monotone properties of combinatorial structures
- 2 Ordering classes of matrices of 0's and 1's
- 3 Cycle decompositions of complete graphs
- 4 Excluding induced subgraphs
- 5 Designs and topology
- 6 The number of points on an algebraic curve over a finite field
- 7 On the efficient approximability of constraint satisfaction problems
- 8 The combinatorics of cryptographic key establishment
- 9 Bandwidth of graphic matroids
Summary
Abstract
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 Pn for the number of distinct structures with vertices labelled 1, …, n, and call the function n ↦ |Pn| the labelled speed of P. Similarly, the unlabelled speed is n ↦ |Pn|, where Pn 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.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2007 , pp. 1 - 40Publisher: Cambridge University PressPrint publication year: 2007
- 6
- Cited by