Article ID Journal Published Year Pages File Type
4654277 European Journal of Combinatorics 2010 21 Pages PDF
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
, ,