Mathematics – Combinatorics
Scientific paper
2007-02-13
Topics in Discrete Mathematics (special edition for J. Nesetril, eds. M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thom
Mathematics
Combinatorics
39 pgs, 1 figure
Scientific paper
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.
Balogh József
Bollobas Bela
Morris Robert
No associations
LandOfFree
Hereditary properties of ordered graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hereditary properties of ordered graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hereditary properties of ordered graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-409720