G\'abor 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 {\it 
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. Gy\'arf\'as 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)\le2\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.