A (homogeneous) d-interval is a union of d closed intervals in the line. Let H be a finite collection of d-intervals. The transversal number τ (H) of H is the minimum number of points that intersect every member of H. The matching number v(H) of H is the maximum number of pairwise disjoint members of H. Gyárfás and Lehel  proved that τ ≤ O(vd!) and Kaiser  proved that τ ≤ O(d2v). His proof is topological, applies the Borsuk-Ulam theorem, and extends and simplifies a result of Tardos . Here we give a very short, elementary proof of a similar estimate, using the method of .
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics