### 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 Berlin |

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

## Fingerprint Dive into the research topics of 'Hereditary properties of ordered graphs'. Together they form a unique fingerprint.

## Cite this

Balogh, J., Bollobás, B., & Morris, R. (2006). Hereditary properties of ordered graphs. In

*Topics in discrete mathematics*(Vol. 26, pp. 179-213). (Algorithms Combin.). Springer Berlin. https://doi.org/10.1007/3-540-33700-8_12