TY - JOUR
T1 - The unlabelled speed of a hereditary graph property
AU - Balogh, József
AU - Bollobás, Béla
AU - Saks, Michael
AU - Sós, Vera T.
N1 - E-mail addresses: [email protected] (J. Balogh), [email protected] (B. Bollobás), [email protected] (M. Saks), [email protected] (V.T. Sós). 1 Research of the author was supported in part by NSF grants DMS 0302804, DMS 0603769 and DMS 0600303, UIUC Campus Research Board 06139 and by OTKA grant 049398. 2 Research of the author was supported in part by NSF grants CCR-0225610, DMS-0505550 and W911NF-06-1-0076. 3 Research of the author was supported in part by NSF grants CCR-9988526 and CCR-0515201. 4 Research of the author was supported in part by OTKA grants T032236, T038210 and T042750.
PY - 2009/1
Y1 - 2009/1
N2 - A property of graphs is a collection P of graphs closed under isomorphism; we call P hereditary if it is closed under taking induced subgraphs. Given a property P, we write Pn for the set of graphs in P with vertex set [n] = {1, ..., n}, and Pn for the isomorphism classes of graphs of order n that are in P. The cardinality | Pn | is the labelled speed of P and | Pn | is the unlabelled speed. In the last decade numerous results have been proved about the labelled speeds of hereditary properties, with emphasis on the striking phenomenon that only certain speeds are possible: there are various pairs of functions (f (n), F (n)), with F (n) much larger than f (n), such that if the labelled speed is infinitely often larger than f (n) then it is also larger than F (n) for all sufficiently large values of n. Putting it concisely: the speed jumps from f (n) to F (n). Recent work on hereditary graph properties has shown that "large" and "small" labelled speeds of hereditary graph properties do jump. The aim of this paper is to study the unlabelled speed of a hereditary property, with emphasis on jumps. Among other results, we shall show that the unlabelled speed of a hereditary graph property is either of polynomial order or at least S (n), the number of ways of partitioning a set with n indistinguishable elements.
AB - A property of graphs is a collection P of graphs closed under isomorphism; we call P hereditary if it is closed under taking induced subgraphs. Given a property P, we write Pn for the set of graphs in P with vertex set [n] = {1, ..., n}, and Pn for the isomorphism classes of graphs of order n that are in P. The cardinality | Pn | is the labelled speed of P and | Pn | is the unlabelled speed. In the last decade numerous results have been proved about the labelled speeds of hereditary properties, with emphasis on the striking phenomenon that only certain speeds are possible: there are various pairs of functions (f (n), F (n)), with F (n) much larger than f (n), such that if the labelled speed is infinitely often larger than f (n) then it is also larger than F (n) for all sufficiently large values of n. Putting it concisely: the speed jumps from f (n) to F (n). Recent work on hereditary graph properties has shown that "large" and "small" labelled speeds of hereditary graph properties do jump. The aim of this paper is to study the unlabelled speed of a hereditary property, with emphasis on jumps. Among other results, we shall show that the unlabelled speed of a hereditary graph property is either of polynomial order or at least S (n), the number of ways of partitioning a set with n indistinguishable elements.
KW - Graph properties
KW - Hereditary
KW - Monotone
KW - Size
KW - Speed
UR - http://www.scopus.com/inward/record.url?scp=56449113981&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=56449113981&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2008.03.004
DO - 10.1016/j.jctb.2008.03.004
M3 - Article
AN - SCOPUS:56449113981
SN - 0095-8956
VL - 99
SP - 9
EP - 19
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 1
ER -