کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777343 1632750 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv
چکیده انگلیسی
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
نویسندگان
, , ,