|Date: Friday, November 06, 2015
Location: 4088 East Hall (3:10 PM to 4:00 PM)
Title: Fractional covers and matchings in families of weighted d-intervals
Abstract: A d-interval hypergraph consists of edges that are each the union of d closed intervals on the real line. Tardos and Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by d^2?d+1.
In this talk I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. I will discuss both a topological method (using an extension, due to Shapley, of the KKM theorem), and a generalization of an approach of Alon. For the use of the latter, we prove a weighted version of Turan's theorem. I will also describe a proof of Kaiser's theorem that is more direct than the original proof.
Joint work with R. Aharoni and T. Kaiser.
Speaker: Shira Zerbib
Institution: U. Michigan