A jump to the bell number for hereditary graph properties

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

Research output: Contribution to journalArticlepeer-review

Abstract

A hereditary graph property is a collection of labeled graphs, closed under isomorphism and also under the taking of induced subgraphs. Its speed is the number of graphs in the property as a function of the number of vertices in the graph. Earlier research has characterized the speeds for hereditary graph properties up to n(1+o(1))n, and described the properties that have those smaller speeds. The present work provides the minimal speed possible above that range, and gives a structural characterization for properties which exhibit such speeds. More precisely, this paper sheds lights on the jump from n(1+o(1))n to the range that includes n(1+o(1))n. A measure jumps when there are two functions with positive distance such that the measure can take no values between those functions. A clean jump occurs when the bounding functions are well-defined and occur as possible values of the measure. It has been known for some time that the density of a graph jumps; recent work on hereditary graph properties has shown that speeds jump for properties with "large" or "small" speeds. The current work shows that there is a clean jump for properties with speed in a middle range. In particular, we show that when the speed of a hereditary graph property has speed greater than ncn for all c < 1, the speed is at least Bn, the nth Bell number. Equality occurs only for the property containing all disjoint unions of cliques or its complement.

Original languageEnglish (US)
Pages (from-to)29-48
Number of pages20
JournalJournal of Combinatorial Theory. Series B
Volume95
Issue number1
DOIs
StatePublished - Sep 2005
Externally publishedYes

Keywords

  • Dilworth's Theorem
  • Graph properties
  • Hereditary
  • Monotone
  • Posets
  • Ramsey Theory
  • Size
  • Speed

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A jump to the bell number for hereditary graph properties'. Together they form a unique fingerprint.

Cite this