The Penultimate Rate of Growth for Graph Properties

József Balogh, Béla Bollobás, David Weinreich

Research output: Contribution to journalArticlepeer-review

Abstract

Given a property sript P sign of graphs, write sript P signn for the set of graphs with vertex set [n] having property sript P sign. We call \sript P signn| the speed of sript P sign. Recent research has shown that the speed of a monotone or hereditary property sript P sign can be a constant, polynomial, or exponential function of n, and the structure of the graphs in sript P sign can then be well described. Similarly, \sript P signn\ can be of the form n(1-1/k+o(1))n or 2(1-1/k+o(1))n2/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))n2/2.

Original languageEnglish (US)
Pages (from-to)277-289
Number of pages13
JournalEuropean Journal of Combinatorics
Volume22
Issue number3
DOIs
StatePublished - Mar 2001
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'The Penultimate Rate of Growth for Graph Properties'. Together they form a unique fingerprint.

Cite this