Erdos-Ko-Rado-like theorems for rainbow matchings

Thursday, September 22, 2011 -
2:15pm to 4:15pm
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.
Ron Aharoni
Technion, Haifa
Event Location: 
Fine Hall 224