کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654277 1632815 2010 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The morphology of infinite tournaments; application to the growth of their profile
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The morphology of infinite tournaments; application to the growth of their profile
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 31, Issue 2, February 2010, Pages 461–481
نویسندگان
, ,