Combinatorics: Ron Holzman (Technion) "Edge-covers in d-interval hypergraphs"

Mon, 02/01/201711:00-13:00
Rothberg B220 (CS)
Speaker: Ron Holzman, Technion
Title: Edge-covers in d-interval hypergraphs
Abstract: An interval hypergraph H is a finite family of closed subintervals of [0,1]. It is well known that if for every n+1 points there is an interval in H covering two of them, then there are n (or fewer) intervals in H that cover [0,1]. We prove a suitable analog for d-interval hypergraphs. Here the ground set consists of d copies of [0,1], and every edge is the union of d closed subintervals, one of each copy. The main tool in the proof is a topological theorem due to Bezalel Peleg (who introduced it in the context of cooperative game theory). This is joint work with Ron Aharoni and Shira Zerbib.