کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777648 | 1632971 | 2017 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On sets not belonging to algebras and rainbow matchings in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Motivated by a question of Grinblat, we study the minimal number v(n) that satisfies the following. If A1,â¦,An are equivalence relations on a set X such that for every iâ[n] there are at least v(n) elements whose equivalence classes with respect to Ai are nontrivial, then A1,â¦,An contain a rainbow matching, i.e. there exist 2n distinct elements x1,y1,â¦,xn,ynâX with xiâ¼Aiyi for each iâ[n]. Grinblat asked whether v(n)=3nâ2 for every nâ¥4. The best-known upper bound was v(n)â¤16n/5+O(1) due to Nivasch and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that v(n)=3n+o(n).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 109-120
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 109-120
نویسندگان
Dennis Clemens, Julia Ehrenmüller, Alexey Pokrovskiy,