Mathematics – Combinatorics
Scientific paper
2007-02-13
Mathematics
Combinatorics
26 pgs, no figures
Scientific paper
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 P, we write P_n for the collection of distinct (i.e., non-isomorphic) structures in a property P with n vertices, and call the function n -> |P_n| the speed (or unlabelled speed) of P. Also, we write P^n for the collection of distinct labelled structures in P with vertices labelled 1,...,n, and call the function n -> |P^n| the labelled speed of P. The possible labelled speeds of a hereditary property of graphs have been extensively studied, and the aim of this paper 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 labelled 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 unlabelled 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.
Balogh József
Bollobas Bela
Morris Robert
No associations
LandOfFree
Hereditary properties of combinatorial structures: posets and oriented 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 combinatorial structures: posets and oriented graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hereditary properties of combinatorial structures: posets and oriented graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-409712