Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv

preprint2015arXivOpen access

Abstract

Drisko \cite{drisko} proved (essentially) that every family of 2n−12n-1 matchings of size nn in a bipartite graph possesses a partial rainbow matching of size nn. In \cite{bgs} this was generalized as follows: Any ⌊k+2k+1n⌋−(k+1)\lfloor \frac{k+2}{k+1} n \rfloor -(k+1) matchings of size nn in a bipartite graph have a rainbow matching of size n−kn-k. We extend this latter result to matchings of not necessarily equal cardinalities. Settling a conjecture of Drisko, we characterize those families of 2n−22n-2 matchings of size nn in a bipartite graph that do not possess a rainbow matching of size nn. Combining this with an idea of Alon \cite{alon}, we re-prove a characterization of the extreme case in a well-known theorem of Erdős-Ginzburg-Ziv in additive number theory.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.