Abstract
An ordered graph is a graph together with a linear order on its vertices. A hereditary property of ordered graphs is a collection of ordered graphs closed under taking order-preserving isomorphisms of the vertex set, and order-preserving induced subgraphs. If P is a hereditary property of ordered graphs, then Pn denotes the collection {G∈P:V(G)=[n]}, and the function n↦|Pn| is called the speed of P.
The possible speeds of a hereditary property of labelled graphs have been extensively studied (see [BBW00] and [Bol98] for example), and more recently hereditary properties of other combinatorial structures, such as oriented graphs ([AS00], [BBM06+c]), posets ([BBM06+a], [BGP99]), words ([BB05], [QZ04]) and permutations ([KK03], [MT04]), have also attracted attention. Properties of ordered graphs generalize properties of both labelled graphs and permutations.
In this paper we determine the possible speeds of a hereditary property of ordered graphs, up to the speed 2n−1. In particular, we prove that there exists a jump from polynomial speed to speed Fn, the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from p(n)Fn,k to Fn,k+1 (where p(n) is a polynomial and Fn,k are the generalized Fibonacci numbers) converging to 2n−1. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations.
The possible speeds of a hereditary property of labelled graphs have been extensively studied (see [BBW00] and [Bol98] for example), and more recently hereditary properties of other combinatorial structures, such as oriented graphs ([AS00], [BBM06+c]), posets ([BBM06+a], [BGP99]), words ([BB05], [QZ04]) and permutations ([KK03], [MT04]), have also attracted attention. Properties of ordered graphs generalize properties of both labelled graphs and permutations.
In this paper we determine the possible speeds of a hereditary property of ordered graphs, up to the speed 2n−1. In particular, we prove that there exists a jump from polynomial speed to speed Fn, the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from p(n)Fn,k to Fn,k+1 (where p(n) is a polynomial and Fn,k are the generalized Fibonacci numbers) converging to 2n−1. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations.
Original language | English (US) |
---|---|
Title of host publication | Topics in discrete mathematics |
Publisher | Springer |
Pages | 179-213 |
Number of pages | 35 |
Volume | 26 |
DOIs | |
State | Published - 2006 |
Publication series
Name | Algorithms Combin. |
---|---|
Publisher | Springer, Berlin |
Keywords
- Ordered graphs
- hereditary property
- speed