The morphology of infinite tournaments. Application to the growth of their profile

Abstract

A tournament is \emph{acyclically indecomposable} if no acyclic autonomous set of vertices has more than one element. We identify twelve infinite acyclically indecomposable tournaments and prove that every infinite acyclically indecomposable tournament contains a subtournament isomorphic to one of these tournaments. The {\it profile} of a tournament $T$ is the function ${\varphi }_T$ which counts for each integer $n$ the number ${\varphi }_T(n)$ of tournaments induced by $T$ on the $n$-element subsets of $T$, isomorphic tournaments being identified. As a corollary of the result above we deduce that the growth of ${\varphi }_T$ is either polynomial, in which case ${\varphi }_T(n)\simeq a{n}^k$, for some positive real $a$, some non-negative integer $k$, or as fast as some exponential.

25 pages, presented at CGCS 2007(Luminy, France, May 2-4 2007) in honor of Michel Deza

Cited by in corpus (1)

• The Profile of relations