The morphology of infinite tournaments; application to the growth of their profile.

21ppInternational audienceA tournament is 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 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 an^k$, for some positive real a, some non-negative integer k, or as fast as some exponential. \end{abstract