Transversals of d-Intervals

We present a method which reduces a family of problems in combinatorial geometry (concerning multiple intervals) to purely combinatorial questions about hypergraphs. The main tool is the Borsuk—Ulam theorem together with one of its extensions. For a positive integer d, a homogeneous d-interval is a union of at most d closed intervals on a fixed line ℓ. Let be a system of homogeneous d-intervals such that no k + 1 of its members are pairwise disjoint. It has been known that its transversal number can then be bounded in terms of k and d. Tardos [9] proved that for d = 2, one has . In particular, the bound is linear in k. We show that the latter holds for any d, and prove the tight bound for d = 2. We obtain similar results in the case of nonhomogeneous d-intervals whose definition appears below. Received June 10, 1995, and in revised form June 13, 1996.