Uniqueness of the extreme cases in theorems of Drisko and Erdős–Ginzburg–Ziv. (January 2018)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Kotlar, Dani; Ziv, Ran
• Is Part Of: European journal of combinatorics. Volume 67(2018)
• Page Start: 222
• Page End: 229
• Publication Date: 2018-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.08.008
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Drisko (1998) proved (essentially) that every family of 2 n − 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 + 2 k + 1 n ⌋ − ( 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 2 n − 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.