# Hereditary properties of ordered graphs

József Balogh, Béla Bollobás, Robert Morris

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

## 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.
Original language English (US) Topics in discrete mathematics Springer 179-213 35 26 https://doi.org/10.1007/3-540-33700-8_12 Published - 2006

### Publication series

Name Algorithms Combin. 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.