Aug 28, 3:30pm, Wean 8220

Ron Aharoni, Technion

Beyond Hall's Theorem

Ron Aharoni, Technion

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.