Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Transversals of d-Intervals

T. Kaiser1

(1)  Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic kaiser@kam.ms.mff.cuni.cz, CZ
Abstract.    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.

Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)