TY - JOUR
T1 - The Speed of Hereditary Properties of Graphs
AU - Balogh, József
AU - Bollobás, Béla
AU - Weinreich, David
N1 - Funding Information:
1The work of the first author was partially supported by OTKA Grant FO21271. 2The work of the second author was partially supported by NSF Grant DMS 9971788.
PY - 2000/7
Y1 - 2000/7
N2 - Given a property P of graphs, write Pn for the set of graphs with vertex set [n] having property P. The growth or speed of a property P can be discussed in terms of the values of Pn. For properties with Pnn hereditary properties are surprisingly well determined by their speeds. Sharpening results of E. R. Scheinerman and J. Zito (1994, J. Combin. Theory Ser. B61, 16-39), we prove numerous results about the possible functions Pn and describe in detail the properties exhibiting each type of growth. We also list minimal properties exhibiting each type of growth.
AB - Given a property P of graphs, write Pn for the set of graphs with vertex set [n] having property P. The growth or speed of a property P can be discussed in terms of the values of Pn. For properties with Pnn hereditary properties are surprisingly well determined by their speeds. Sharpening results of E. R. Scheinerman and J. Zito (1994, J. Combin. Theory Ser. B61, 16-39), we prove numerous results about the possible functions Pn and describe in detail the properties exhibiting each type of growth. We also list minimal properties exhibiting each type of growth.
UR - http://www.scopus.com/inward/record.url?scp=0347949106&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347949106&partnerID=8YFLogxK
U2 - 10.1006/jctb.2000.1952
DO - 10.1006/jctb.2000.1952
M3 - Article
AN - SCOPUS:0347949106
SN - 0095-8956
VL - 79
SP - 131
EP - 156
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -