Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654277 | European Journal of Combinatorics | 2010 | 21 Pages |
Abstract
A 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 TT is the function φTφT which counts for each integer nn the number φT(n)φT(n) of tournaments induced by TT on the nn-element subsets of TT, isomorphic tournaments being identified. As a corollary of the result above we deduce that the growth of φTφT is either polynomial, in which case φT(n)≃ankφT(n)≃ank, for some positive real aa, and some non-negative integer kk, or as fast as some exponential.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Youssef Boudabbous, Maurice Pouzet,