Hereditary Properties of Ordered Graphs

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

P

n

denotes the collection

$$ \left\{ {G \in \mathcal{P}:V(G) = [n]} \right\} $$

, and the function

$$ n \mapsto \left| {\mathcal{P}_n } \right| $$

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 2

n

−1

. In particular, we prove that there exists a jump from polynomial speed to speed

F

n

, the Fibonacci numbers, and that there exists an infinite sequence of subsequent jumps, from

p(n)F

n,k

to

F

n,k

+1

(where

p

(

n

) is a polynomial and

F

n,k

are the generalized Fibonacci numbers) converging to 2

n

−1

. Our results generalize a theorem of Kaiser and Klazar [KK03], who proved that the same jumps occur for hereditary properties of permutations.