Combinatorics Seminar

When: Sunday, December 4, 10am Where: Schreiber 309 Speaker: David Howard, Technion Title: Extensions of the Erdos-Ko-Rado Theorem

Abstract:

A rainbow matching of a system (F_1,...,F_k) of hypergraphs is a choice of disjoint edges, one from each F_i. The results I will describe are motivated by the following conjecture:

Conjecture: Let A be a number such that every subset of ([n] choose r) of size at least A contains a matching of size k. If F_i is a subset of ([n] choose r), for i=1,2,...k, and |F_i|>= A then (F_1,F_2,...,F_k) have a rainbow matching.

This is known for r=2 (Meshulam) and for k=2 (Matsumoto and Tokushige). For general k and r we do not even know a formula for the number A above. We make a similar conjecture for r-partite hypergraphs, in which the lower bound is easy to find. We then prove the conjecture for r=2,3 and for k=2.

This is joint work with Ron Aharoni.