pith. sign in

arxiv: 1511.05775 · v1 · pith:Q3WLDGURnew · submitted 2015-11-18 · 🧮 math.CO

Uniqueness of the extreme cases in theorems of Drisko and ErdH{o}s-Ginzburg-Ziv

classification 🧮 math.CO
keywords sizedriskomatchingsbipartitecitegraphmatchingrainbow
0
0 comments X
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.