The Penultimate Rate of Growth for Graph Properties

Authors: Balogh J.¹; Bollobás B.^{2, 3}; Weinreich D.⁴

Source: European Journal of Combinatorics, Volume 22, Number 3, March 2001 , pp. 277-289(13)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

Given a property P of graphs, write Pⁿfor the set of graphs with vertex set [ n ] having property P. We call | Pⁿ| the speed of P. Recent research has shown that the speed of a monotone or hereditary property P can be a constant, polynomial, or exponential function of n, and the structure of the graphs in P can then be well described. Similarly, | Pⁿ| can be of the form n^{(1 - 1 / k + o(1))n}or 2^{(1 - 1 / k + o(1))n² / 2}for some positive integer k > 1 and the properties can be described and have well-behaved speeds. In this paper, we discuss the behavior of properties with speeds between these latter bounds, i.e., between n^{(1 + o(1))n}and 2^{(1 / 2 + o(1))n² / 2}. Copyright 2001 Academic Press

Language: English

Document Type: Research article

Affiliations: 1: Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, U.S.A. 2: Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, U.S.A. 3: Trinity College, Cambridge, CB2 1TQ, U.K. 4: Department of Mathematics, University of Wisconsin-La Crosse, La Crosse, WI 54601, U.S.A.

Publication date: 2001-03-01