کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646780 | 1342313 | 2016 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colorings of hypergraphs with large number of colors
ترجمه فارسی عنوان
رنگ آمیزی پرتره با تعداد زیادی رنگ
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The paper deals with the well-known problem of Erdős and Hajnal concerning colorings of uniform hypergraphs and some related questions. Let m(n,r)m(n,r) denote the minimum possible number of edges in an nn-uniform non-rr-colorable hypergraph. We show that for r>nr>n, c1nlnn⩽m(n,r)rn⩽C1n3lnn, where c1,C1>0c1,C1>0 are some absolute constants. Moreover, we obtain similar bounds for d(n,r)d(n,r), which is equal to the minimum possible value of the maximum edge degree in an nn-uniform non-rr-colorable hypergraph. If r>nr>n, then c2nlnn⩽d(n,r)rn−1⩽C2n3lnn, where c2,C2>0c2,C2>0 are some other absolute constants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 12, 6 December 2016, Pages 3020–3031
Journal: Discrete Mathematics - Volume 339, Issue 12, 6 December 2016, Pages 3020–3031
نویسندگان
Ilia Akolzin, Dmitry Shabanov,