2016/05/22 by Aharoni, Ron, Howard, David · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1605.06752
Let f(n,r,k) be the minimal number such that every hypergraph larger than f(n,r,k) contained in \binom[n]r contains a matching of size k, and let g(n,r,k) be the minimal number such that every hypergraph larger than g(n,r,k) contained in the r-partite r-graph [n]r contains a matching of size k. The Erdős-Ko-Rado theorem states that f(n,r,2)=\binomn-1r-1~~(r ≤ (n)/(2)) and it is easy to show that g(n,r,k)=(k-1)nr-1. The conjecture inspiring this paper is that if F1,F2,…,Fk⊆ \binom[n]r are of size larger than f(n,r,k) or F1,F2,…,Fk⊆ [n]r are of size larger than g(n,r,k) then there exists a rainbow matching, i.e. a choice of disjoint edges fi ∈ Fi. In this paper we deal mainly with the second part of the conjecture, and prove it for r≤ 3. \vspace.1cm We also prove that for every r and k there exists n0=n0(r,k) such that the r-partite version of the conjecture is true for n>n0.