Algorithms, Combinatorics and Optimization Seminar Ron Aharoni
Technion
Title: Beyond Hall's Theorem

Abstract: The talk revolves around the topic of matchings in hypergraphs. A main notion is that of "rainbow matching", which is a choice of disjoint edges f_i from given sets F_i of edges. I will describe a rainbow matching version of the Erdos-Ko-Rado theorem (whose spirit is "if F_i are big relative to the ground set then there is a rainbow matching".) The rest of the talk will be devoted to a topological tool developed for the study of rainbow independent sets (a generalization of rainbow matchings), that extends Hall's theorem, and its applications.

Date: Tuesday, August 28, 2012
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Loh