کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656993 1343706 2011 33 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An approximate version of Sumnerʼs universal tournament conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
An approximate version of Sumnerʼs universal tournament conjecture
چکیده انگلیسی

Sumnerʼs universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 101, Issue 6, November 2011, Pages 415-447