کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777458 1632918 2018 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Chromatic number of random Kneser hypergraphs
ترجمه فارسی عنوان
تعداد کروماتوگرافی تصادفی کینزر
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Recently, Kupavskii (2016) [20] investigated the chromatic number of random Kneser graphs KGn,k(ρ) and proved that, in many cases, the chromatic number of the random Kneser graph KGn,k(ρ) and the Kneser graph KGn,k are almost surely closed. He also marked the studying of the chromatic number of random Kneser hypergraphs KGn,kr(ρ) as a very interesting problem. With the help of Zp-Tucker lemma, a combinatorial generalization of the Borsuk-Ulam theorem, we generalize Kupavskii's result to random general Kneser hypergraphs by introducing an almost surely lower bound for the chromatic number of them. Roughly speaking, as a special case of our result, we show that the chromatic numbers of the random Kneser hypergraph KGn,kr(ρ) and the Kneser hypergraph KGn,kr are almost surely closed in many cases. Moreover, restricting to the Kneser and Schrijver graphs, we present a purely combinatorial proof for an improvement of Kupavskii's result.Also, for any hypergraph H, we present a lower bound for the minimum number of colors required in a coloring of KGr(H) with no monochromatic Kt,…,tr subhypergraph, where Kt,…,tr is the complete r-uniform r-partite hypergraph with tr vertices such that each of its parts has t vertices. This result generalizes the lower bound for the chromatic number of KGr(H) found by Alishahi and Hajiabolhassan (2015) [3].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 154, February 2018, Pages 1-20
نویسندگان
, ,