2006 | OriginalPaper | Chapter
Hereditary Properties of Ordered Graphs
Authors : József Balogh, Béla Bollobás, Robert Morris
Published in: Topics in Discrete Mathematics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
P
n
denotes the collection
$$ \left\{ {G \in \mathcal{P}:V(G) = [n]} \right\} $$
, and the function
$$ n \mapsto \left| {\mathcal{P}_n } \right| $$
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 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 [KK03], who proved that the same jumps occur for hereditary properties of permutations.