The Penultimate Rate of Growth for Graph Properties

✍ Scribed by József Balogh; Béla Bollobás; David Weinreich

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 166 KB
• Volume: 22
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2000.0476

✦ Synopsis

Given a property P of graphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | 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 n | can be of the form n (1-1/k+o(1))n or 2 (1-1/k+o(1))n 2 /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 /2 .