کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777343 | 1632750 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Uniqueness of the extreme cases in theorems of Drisko and ErdÅs-Ginzburg-Ziv
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Drisko (1998) proved (essentially) that every family of 2nâ1 matchings of size n in a bipartite graph possesses a partial rainbow matching of size n. In Barát et al. (2017) this was generalized as follows: Any âk+2k+1nââ(k+1) matchings of size n in a bipartite graph have a rainbow matching of size nâk. The paper has a twofold aim: (i) to extend these results to matchings of not necessarily equal cardinalities, and (ii) to prove a conjecture of Drisko, on the characterization of those families of 2nâ2 matchings of size n in a bipartite graph that do not possess a rainbow matching of size n. Combining the latter with an idea of Alon (2011), we re-prove a characterization of the extreme case in a well-known theorem of ErdÅs-Ginzburg-Ziv in additive number theory.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 67, January 2018, Pages 222-229
Journal: European Journal of Combinatorics - Volume 67, January 2018, Pages 222-229
نویسندگان
Ron Aharoni, Dani Kotlar, Ran Ziv,