Erdos-Ko-Rado-like theorems for rainbow matchings
Erdos-Ko-Rado-like theorems for rainbow matchings
-
Ron Aharoni, Technion, Haifa
Fine Hall 224
Let $f(n,k,r)$ be the smallest number such that every set of more than $f(n,k,r)$ r-sets in $[n]$ contains a matching of size $k$. The Erdos-Ko-Rado theorem states that $f(n,2,r)=(n-1)(r-1)$. A natural conjecture is that if $F_1, F_2, ...F_k \subseteq {[n]}{r}$ are all of size larger than $f(n,k,r)$ then they possess a rainbow matching, that is, a choice of disjoint edges, one from each $F_i$. This is known for $k=2$ (Matsumoto-Tokushige) and $r=2$ (Meshulam). We consider the analogue of this conjecture in $r$-partite hypergraphs, and prove the cases $r=3$ and $k=2$.Joint work with David Howard.