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 language | English (US) |
---|---|
Journal | Electronic Journal of Combinatorics |
Volume | 14 |
Issue number | 1 R |
DOIs | |
State | Published - Aug 20 2007 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics