Hereditary properties of tournaments

József Balogh, Béla Bollobás, Robert Morris

Research output: Contribution to journalArticlepeer-review

Abstract

A collection of unlabelled tournaments P is called a hereditary property if it is closed under isomorphism and under taking induced sub-tournaments. The speed of P is the function n → |Pn|, where Pn = {T ∈ P : |V (T)| = n}. In this paper, we prove that there is a jump in the possible speeds of a hereditary property of tournaments, from polynomial to exponential speed. Moreover, we determine the minimal exponential speed, |P n| = c(1+o(1))n, where c ≃ 1:47 is the largest real root of the polynomial x3 = x2 + 1, and the unique hereditary property with this speed.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume14
Issue number1 R
DOIs
StatePublished - Aug 20 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Hereditary properties of tournaments'. Together they form a unique fingerprint.

Cite this