Fractional matchings and covers in families of (weighted) d-intervals

Seminar
Speaker
Shira Zerbib (Technion)
Date
02/11/2014 - 14:00Add to Calendar 2014-11-02 14:00:00 2014-11-02 14:00:00 Fractional matchings and covers in families of (weighted) d-intervals A $d$-interval hypergraph consists of edges that are each the union of $d$ closed intervals on the real line. Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by $d^2-d+1$. I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. To this end I will describe a weighted version of Tur\'{a}n's theorem. I will also discuss an extension of the KKM theorem (due to Shapley) and use it to give a straightforward proof to Kaiser's theorem.   Joint work with R. Aharoni and T. Kaiser.  אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

A $d$-interval hypergraph consists of edges that are each the union of $d$ closed intervals on the real line. Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by $d^2-d+1$. I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. To this end I will describe a weighted version of Tur\'{a}n's theorem. I will also discuss an extension of the KKM theorem (due to Shapley) and use it to give a straightforward proof to Kaiser's theorem.

 
Joint work with R. Aharoni and T. Kaiser. 

Last Updated Date : 06/11/2014