کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648517 | 1342415 | 2012 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On rr-chromatic hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
This work deals with a classical combinatorial problem of P. Erdős and A. Hajnal concerning colorings of uniform hypergraphs. Let m(n,r)m(n,r) denote the minimum number of edges in an nn-uniform non-rr-colorable hypergraph. We prove that for all n≥3n≥3 and r≥3r≥3, the following inequality holds m(n,r)≥12n1/2rn−1. This bound improves all the previously known bounds for r=3r=3 and lnlnn≪r≪lnnlnlnn. We also obtain some results concerning colorings of simple and ll-simple hypergraphs. These results are based on our new lower bound for the maximum edge degree in an nn-uniform non-rr-colorable hypergraph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 2, 28 January 2012, Pages 441–458
Journal: Discrete Mathematics - Volume 312, Issue 2, 28 January 2012, Pages 441–458
نویسندگان
Dmitry A. Shabanov,