Premium
Hereditary properties of combinatorial structures: Posets and oriented graphs
Author(s) -
Balogh József,
Bollobás Béla,
Morris Robert
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20266
Subject(s) - combinatorics , mathematics , bounded function , isomorphism (crystallography) , graph , star product , function (biology) , discrete mathematics , crystallography , chemistry , mathematical analysis , crystal structure , evolutionary biology , biology
A hereditary property of combinatorial structures is a collection of structures (e.g., graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g., induced subgraphs), and contains arbitrarily large structures. Given a property $\cal {P}$ , we write $\cal {P}_{n}$ for the collection of distinct (i.e., non‐isomorphic) structures in a property $\cal {P}$ with n vertices, and call the function ${n} \mapsto |\cal {P}_{n}|$ the speed (or unlabeled speed) of $\cal {P}$ . Also, we write $\cal {P}^{n}$ for the collection of distinct labeled structures in $\cal {P}$ with vertices labeled $1,\ldots,{n}$ , and call the function ${n} \mapsto |\cal {P}^{n}|$ the labeled speed of $\cal {P}$ . The possible labeled speeds of a hereditary property of graphs have been extensively studied, and the aim of this article is to investigate the possible speeds of other combinatorial structures, namely posets and oriented graphs. More precisely, we show that (for sufficiently large n ), the labeled speed of a hereditary property of posets is either 1, or exactly a polynomial, or at least $2^{n}-{1}$ . We also show that there is an initial jump in the possible unlabeled speeds of hereditary properties of posets, tournaments, and directed graphs, from bounded to linear speed, and give a sharp lower bound on the possible linear speeds in each case. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 311–332, 2007