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 languageEnglish (US)
Title of host publicationTopics in discrete mathematics
PublisherSpringer Berlin
Pages179-213
Number of pages35
Volume26
DOIs
StatePublished - 2006

Publication series

NameAlgorithms Combin.
PublisherSpringer, 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