کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10118311 | 1632742 | 2019 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the ErdÅs-Hajnal conjecture for six-vertex tournaments
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A celebrated unresolved conjecture of ErdÅs and Hajnal states that for every undirected graph H there exists ϵ(H)>0 such that every undirected graph on n vertices that does not contain H as an induced subgraph contains a clique or stable set of size at least nϵ(H). The conjecture has a directed equivalent version stating that for every tournament H there exists ϵ(H)>0 such that every H-free n-vertex tournament T contains a transitive subtournament of order at least nϵ(H). We say that a tournament is prime if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments (Berger et al., 2014; Choromanski, 2015 [3]) and tournaments constructed according to the so-called substitution procedure (Alon et al., 2001). In particular, recently the conjecture was proved for all five-vertex tournaments (Berger et al. 2014), but the question about the correctness of the conjecture for all six-vertex tournaments remained open. In this paper we prove that all but at most one six-vertex tournament satisfy the ErdÅs-Hajnal conjecture. That reduces the six-vertex case to a single tournament.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 75, January 2019, Pages 113-122
Journal: European Journal of Combinatorics - Volume 75, January 2019, Pages 113-122
نویسندگان
Eli Berger, Krzysztof Choromanski, Maria Chudnovsky,