Seminar Event Detail


Combinatorics

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.

Files:


Speaker:  Shira Zerbib
Institution:  U. Michigan

Event Organizer:     

 

Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact math-webmaster@umich.edu

Back to previous page
Back to UM Math seminars/events page.