The unlabelled speed of a hereditary graph property

József Balogh, Béla Bollobás, Michael Saks, Vera T. Sós

Research output: Contribution to journalArticlepeer-review

Abstract

A property of graphs is a collection P of graphs closed under isomorphism; we call P hereditary if it is closed under taking induced subgraphs. Given a property P, we write Pn for the set of graphs in P with vertex set [n] = {1, ..., n}, and Pn for the isomorphism classes of graphs of order n that are in P. The cardinality | Pn | is the labelled speed of P and | Pn | is the unlabelled speed. In the last decade numerous results have been proved about the labelled speeds of hereditary properties, with emphasis on the striking phenomenon that only certain speeds are possible: there are various pairs of functions (f (n), F (n)), with F (n) much larger than f (n), such that if the labelled speed is infinitely often larger than f (n) then it is also larger than F (n) for all sufficiently large values of n. Putting it concisely: the speed jumps from f (n) to F (n). Recent work on hereditary graph properties has shown that "large" and "small" labelled speeds of hereditary graph properties do jump. The aim of this paper is to study the unlabelled speed of a hereditary property, with emphasis on jumps. Among other results, we shall show that the unlabelled speed of a hereditary graph property is either of polynomial order or at least S (n), the number of ways of partitioning a set with n indistinguishable elements.

Original languageEnglish (US)
Pages (from-to)9-19
Number of pages11
JournalJournal of Combinatorial Theory. Series B
Volume99
Issue number1
DOIs
StatePublished - Jan 2009

Keywords

  • Graph properties
  • Hereditary
  • Monotone
  • Size
  • Speed

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'The unlabelled speed of a hereditary graph property'. Together they form a unique fingerprint.

Cite this