Uniqueness of the extreme cases in theorems of Drisko and ErdH{o}s-Ginzburg-Ziv
read the original abstract
Drisko \cite{drisko} 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 \cite{bgs} this was generalized as follows: Any $\lfloor \frac{k+2}{k+1} n \rfloor -(k+1)$ matchings of size $n$ in a bipartite graph have a rainbow matching of size $n-k$. We extend this latter result to matchings of not necessarily equal cardinalities. Settling a conjecture of Drisko, we characterize those families of $2n-2$ matchings of size $n$ in a bipartite graph that do not possess a rainbow matching of size $n$. 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\H{o}s-Ginzburg-Ziv in additive number theory.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.