Transversals of 2-intervals,a topological approach

Fix two distinct parallel linese andf. A 2-interval is the union of an interval one and an interval onf. We study thetransversal number τ (ℋ) of families of 2-intervals ℋ. This is the cardinality of the smallest set which intersects every 2-interval in ℋ. A Gyárfás and J. Lehel [6] proved that τ(ℋ)=O(υ(ℋ)²) where ν(ℋ) is the maximum number of disjoint 2-intervals in ℋ. In the present paper we prove the tight bond τ(ℋ)≤2v(ℋ). Our result has applications in the estimation of the transversal number of other types of set systems. The method we use is topological. We associate a simplicial complexK with our system of 2-intervals and prove that a given subcomplex is contractible inK unless the required transversal exists. Then we construct a cocycle of (another subcomplex of)K to prove that the subcomplex is not contractible inK. We hope that this approach will be applicable to a wider variety of combinatorial optimization problems. Supported by the NSF grant No. CCR-92-00788 and the (Hungarian) National Scientific Research Fund (OTKA) grant No. T4271. The author was visiting the Computation and Automation Institute of the Hungarian Academy of Sciences while part of this research was done.