کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656833 1632984 2014 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tournaments with near-linear transitive subsets
ترجمه فارسی عنوان
مسابقات با زیر مجموعه های پیوندی نزدیک
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let H be a tournament, and let ϵ≥0 be a real number. We call ϵ an “Erdős-Hajnal coefficient” for H if there exists c>0 such that in every tournament G not containing H as a subtournament, there is a transitive subset of cardinality at least c|V(G)|ϵ. The Erdős-Hajnal conjecture asserts, in one form, that every tournament H has a positive Erdős-Hajnal coefficient. This remains open, but recently the tournaments with Erdős-Hajnal coefficient 1 were completely characterized. In this paper we provide an analogous theorem for tournaments that have an Erdős-Hajnal coefficient larger than 5/6; we give a construction for them all, and we prove that for any such tournament H there are numbers c,d such that, if a tournament G with |V(G)|>1 does not contain H as a subtournament, then V(G) can be partitioned into at most c(log⁡(|V(G)|))d transitive subsets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 109, November 2014, Pages 228-249
نویسندگان
, , ,