Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department |
Algorithms, Combinatorics and Optimization Seminar
For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...) 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 8220 Submitted by: Loh |