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

יום א', 02/11/2014 - 14:00
Speaker: 
Seminar: 
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.