A rainbow $r$-partite version of the Erdős-Ko-Rado theorem

Abstract

Let $f(n,r,k)$ be the minimal number such that every hypergraph larger than $f(n,r,k)$ contained in $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ 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)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$~~($r\le \frac{n}{2}$) and it is easy to show that $g(n,r,k)=(k-1)n^{r-1}$. The conjecture inspiring this paper is that if $F_1,F_2,\dots ,F_k\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ are of size larger than $f(n,r,k)$ or $F_1,F_2,\dots ,F_k\subseteq [n{]}^r$ are of size larger than $g(n,r,k)$ then there exists a rainbow matching, i.e. a choice of disjoint edges $f_i\in F_i$. In this paper we deal mainly with the second part of the conjecture, and prove it for $r\le 3$. \vspace{.1cm} We also prove that for every $r$ and $k$ there exists $n_0=n_0(r,k)$ such that the $r$-partite version of the conjecture is true for $n>n_0$.