***********************************
* Princeton Discrete Math Seminar *
***********************************
Date: Thursday 2nd March, 3:00 in Fine Hall 224.
Speaker: Shira Zerbib (U. Michigan)
Title: Matchings and covers in families of d-intervals and their duals.
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.
Next week: Michael Tait
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)