Transversals of 2-intervals, a topological approach
Transversals of 2-intervals, a topological approach
G. Tardos:
Transversals of 2-intervals, a topological approach
Fix two distinct parallel lines e and f. A 2-interval is
the union
of an interval on e and an interval on f. We study the
transversal number \tau(H) of families of 2-intervals H.
This is
the cardinality of the smallest set which intersects every 2-interval
in H. A. Gyarfas and J. Lehel [6] proved that \tau(H)=
O(\nu(H)^2) where \nu(H) is the maximum number of
disjoint 2-intervals in H. In the present paper we prove the tight
bound \tau(H)< 2\nu(H).
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 complex K
with our system of 2-intervals and prove that a given subcomplex is
contractible in K unless the required transversal exists. Then we
construct a cocycle of (another subcomplex of) K to prove that the
subcomplex is not contractible in K. We hope that this approach will
be applicable to a wider variety of combinatorial optimization problems.