Hereditary properties of ordered graphs
| dc.creator | Balogh, József | |
| dc.creator | Bollobás, Béla | |
| dc.creator | Morris, Robert | |
| dc.date | 2007-02-13 | |
| dc.date.accessioned | 2026-07-07T07:46:39Z | |
| dc.date.available | 2026-07-07T07:46:39Z | |
| dc.description | 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 induced ordered subgraphs. If P is a property of ordered graphs, then the function which counts the number of ordered graphs in P with exactly n vertices is called the speed of P. 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, who proved that the same jumps occur for hereditary properties of permutations. | |
| dc.description | 39 pgs, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/0702352 | |
| dc.identifier | http://arxiv.org/abs/math/0702352 | |
| dc.identifier | Topics in Discrete Mathematics (special edition for J. Nesetril, eds. M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr), Springer, 26 (2006), 179-213 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/123899 | |
| dc.subject | Combinatorics | |
| dc.title | Hereditary properties of ordered graphs | |
| dc.type | text |