Hereditary properties of tournaments

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

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

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.

Détail

DOI : 10.37236/978

Classification : 05C20, 05A99
Mots-clés : hereditary properties of tournaments, induced subtournaments, polynomial speed, minimal exponential speed, jump