Piercing d-Intervals

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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 [3] proved that τ ≤ O(vd!) and Kaiser [4] proved that τ ≤ O(d2v). His proof is topological, applies the Borsuk-Ulam theorem, and extends and simplifies a result of Tardos [5]. Here we give a very short, elementary proof of a similar estimate, using the method of [2].

Original languageEnglish (US)
Pages (from-to)333-334
Number of pages2
JournalDiscrete and Computational Geometry
Volume19
Issue number3
DOIs
StatePublished - Apr 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Piercing d-Intervals'. Together they form a unique fingerprint.

Cite this