Hereditary Properties of Tournaments

Abstract

A collection of unlabelled tournaments ${\cal P}$ is called a hereditary property if it is closed under isomorphism and under taking induced sub-tournaments. The speed of ${\cal P}$ is the function $n \mapsto |{\cal P}_n|$, where ${\cal P}_n = \{T \in {\cal 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, $|{\cal P}_n| = c^{(1+o(1))n}$, where $c \simeq 1.47$ is the largest real root of the polynomial $x^3 = x^2 + 1$, and the unique hereditary property with this speed.