Geodesic
Cooperative conditions for the existence of rainbow matchings
Ron Aharoni1 ; Joseph Briggs2 ; Minho Cho3 ; Jinha Kim4
1Technion - Israel Institute of Technology
2Auburn University
3KAIST
4Institute for Basic Science
The electronic journal of combinatorics, Tome 29 (2022) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $k>1$, and let $\mathcal{F}$ be a family of $2n+k-3$ non-empty sets of edges in a bipartite graph. If the union of every $k$ members of $\mathcal{F}$ contains a matching of size $n$, then there exists an $\mathcal{F}$-rainbow matching of size $n$. Replacing $2n+k-3$ by $2n+k-2$, the result is true also for $k=1$, and it can be proved (for all $k$) both topologically and by a relatively simple combinatorial argument. The main effort is in gaining the last $1$, which makes the result sharp.
DOI : 10.37236/9448
Classification : 05C70, 05C35, 05D15, 52A35
Mots-clés : S-rainbow set, Kalai-Meshulam theorem

Ron Aharoni  1   ; Joseph Briggs  2   ; Minho Cho  3   ; Jinha Kim  4

1 Technion - Israel Institute of Technology
2 Auburn University
3 KAIST
4 Institute for Basic Science 
@article{10_37236_9448,
     author = {Ron Aharoni and Joseph Briggs and Minho Cho and Jinha Kim},
     title = {Cooperative conditions for the existence of rainbow matchings},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {1},
     doi = {10.37236/9448},
     zbl = {1481.05123},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9448/}
}
TY  - JOUR
AU  - Ron Aharoni
AU  - Joseph Briggs
AU  - Minho Cho
AU  - Jinha Kim
TI  - Cooperative conditions for the existence of rainbow matchings
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9448/
DO  - 10.37236/9448
ID  - 10_37236_9448
ER  - 
%0 Journal Article
%A Ron Aharoni
%A Joseph Briggs
%A Minho Cho
%A Jinha Kim
%T Cooperative conditions for the existence of rainbow matchings
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9448/
%R 10.37236/9448
%F 10_37236_9448
Ron Aharoni; Joseph Briggs; Minho Cho; Jinha Kim. Cooperative conditions for the existence of rainbow matchings. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/9448

Cité par Sources :