Matchings and covers in families of d-intervals and their duals
Matchings and covers in families of d-intervals and their duals
-
Shira Zerbib , University of Michigan
Fine Hall 224
A classical theorem of Gallai is that in any family of closed intervals in the real line, the maximal number of disjoint intervals is equal to the minimal number of points piercing all intervals. Tardos and Kaiser extended this result (appropriately modified) to families of ``d-intervals'', that is, hypergraphs in which each edge is the union of d intervals. We prove an analogous result for dual d-interval hypergraphs, in which the roles of the points and the edges are reversed. The proof is topological. We also discuss a recent Helly-type result for families of d-intervals.