Name
Abstract | ||
|---|---|---|
A hereditary property of combinatorial structures is acollection of structures (e.g., graphs, posets) which is closedunder isomorphism, closed under taking induced substructures (e.g.,induced subgraphs), and contains arbitrarily large structures.Given a property P, we writeP\ for the collection of distinct (i.e.,non-isomorphic) structures in a property P withn vertices, and call the function n ➛|P\| the speed (or unlabeled speed) ofP. Also, we write P\ for thecollection of distinct labeled structures in Pwith vertices labeled 1,...,n, and call the functionn ➛ |P\| the labeled speedof P. The possible labeled speeds of a hereditaryproperty of graphs have been extensively studied, and the aim ofthis article is to investigate the possible speeds of othercombinatorial structures, namely posets and oriented graphs. Moreprecisely, we show that (for sufficiently large n), thelabeled speed of a hereditary property of posets is either 1, orexactly a polynomial, or at least 2n-1. We alsoshow that there is an initial jump in the possible unlabeled speedsof hereditary properties of posets, tournaments, and directedgraphs, from bounded to linear speed, and give a sharp lower boundon the possible linear speeds in each case. © 2007 WileyPeriodicals, Inc. J Graph Theory 56: 311332, 2007The work was done while Robert Morris was at the University ofMemphis. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1002/jgt.v56:4 | Journal of Graph Theory |
Keywords | Field | DocType |
poset,tournament,lower bound,directed graph | Graph theory,Discrete mathematics,Combinatorics,Hereditary property,Vertex (geometry),Directed graph,Isomorphism,Star product,Partially ordered set,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
56 | 4 | 0364-9024 |
Citations | PageRank | References |
4 | 0.49 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| József Balogh | 1 | 862 | 89.91 |
| Béla Bollobás | 2 | 2696 | 474.16 |
| Robert Morris | 3 | 101 | 13.12 |