History

Please fill in your query. A complete syntax description you will find on the General Help page.
Hereditary properties of ordered graphs. (English)
Klazar, Martin (ed.) et al., Topics in discrete mathematics. Dedicated to Jarik Nešetřil on the occasion of his 60th birthday. Berlin: Springer (ISBN 3-540-33698-2/hbk). Algorithms and Combinatorics 26, 179-213 (2006).
From the summary: 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 ${\cal P}$ is a hereditary property of ordered graphs, then ${\cal P}_n$ denotes the collection $\{G\in{\cal P}: V(G)=[n]\}$, and the function $n\mapsto\vert{\cal P}_n|$ is called the speed of ${\cal 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 {\it T. Kaiser} and {\it M. Klazar} [Electron. J. Comb. 9, Research paepr R10 (2002‒2003; Zbl 1015.05002); printed version J. Comb. 9, No. 2, R10 (2002‒2003)] who proved that the same jumps occur for hereditary properties of permutations.