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
