TY - JOUR

T1 - Hereditary properties of combinatorial structures

T2 - posets and oriented graphs

AU - Balogh, József

AU - Bollobás, Béla

AU - Morris, Robert

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2007/12

Y1 - 2007/12

N2 - 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 □P1 we write Pn for the collection of distinct (i.e., non-isomorphic) structures in a property V with n vertices, and call the function n > □ |Pn| the speed (or unlabeled speed) of P. Also, we write Pn for the collection of distinct labeled structures in V with vertices labeled 1, . . . , n, and call the function ni □ |Pn| the labeled speed of V. 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 2n - 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.

AB - 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 □P1 we write Pn for the collection of distinct (i.e., non-isomorphic) structures in a property V with n vertices, and call the function n > □ |Pn| the speed (or unlabeled speed) of P. Also, we write Pn for the collection of distinct labeled structures in V with vertices labeled 1, . . . , n, and call the function ni □ |Pn| the labeled speed of V. 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 2n - 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.

KW - Hereditary property

KW - Poset

KW - Tournament

UR - http://www.scopus.com/inward/record.url?scp=37149000525&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=37149000525&partnerID=8YFLogxK

U2 - 10.1002/jgt.20266

DO - 10.1002/jgt.20266

M3 - Article

AN - SCOPUS:37149000525

VL - 56

SP - 311

EP - 332

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 4

ER -