Transversals of \(d\)-intervals
type: Item
instance of: scholarly article
title: Transversals of \(d\)-intervals
zbMATH Open document ID: 0883.05124
DOI: 10.1007/PL00009315
published in: Discrete \& Computational Geometry
publication date: 1998-02-23T00:00:00Z
review text: A homogeneous \(d\)-interval is a nonempty union of at most \(d\) closed intervals on a fixed line. A nonhomogeneous \(d\)-interval \(J\) is a nonvoid subset of the union of \(d\) distinct lines \(l_1,\ldots ,l_d\) in the plane, such that each \(J\cap l_i\) is either a closed segment or the empty set. This paper treats generalizations to (homogeneous or nonhomogeneous) \(d\)-intervals of the following theorem of Gallai: if \(H\) is a family of closed intervals on a line such that no \(k+1\) of its members are pairwise disjoint, then there is a set \(T\) of \(k\) points of the line that intersects all intervals from \(H\). The set \(T\) is then called a transversal of \(H\). Obviously, the number \(k\) may be replaced by the packing number (or matching number) \(\nu (H)\), which is defined to be the maximum number of pairwise disjoint elements of \(H\). Here are the two main results of the paper: (1) Every system \(H\) of homogeneous \(d\)-intervals has a transversal of size \((d^2-d+1) \nu (H)\). This bound improves to \((d^2-d) \nu (H)\) if \(d\geq 3\) and there is no projective plane of order \(d-1\). (2) Every system \(H\) of nonhomogeneous \(d\)-intervals has a transversal of size \((d^2-d) \nu (H)\). These theorems improve a previous result by \textit{G. Tardos} on \(2\)-intervals [see Combinatorica 15, No. 1, 123-134 (1995; Zbl 0823.05022)]. A main tool of the proof is the Borsuk-Ulam theorem, which says that every continuous antipodal map \(S^n\rightarrow \mathbb{R}^n\) has a zero. Furthermore, two results of Lovász and Füredi are used, which give upper bounds of the fractional matching number \(\nu ^{*}(H)\) in terms of \(\nu (H)\). However, the author remarks that the latter results are not necessary if one wants to prove only the slightly weaker bound \(d^2\nu (H)\) on the minimum size of a transversal.
Mathematics Subject Classification ID: 05D15
Mathematics Subject Classification ID: 05B40
zbMATH DE Number: 1051248
zbMATH Keywords: transversal number
zbMATH Keywords: packing number
zbMATH Keywords: matching number
zbMATH Keywords: multiple intervals
zbMATH Keywords: theorem of Gallai
zbMATH Keywords: intervals
zbMATH Keywords: transversal
author: Tomáš Kaiser
reviewed by: Johann Linhart
MaRDI profile type: Publication
full work available at URL: pl00009315
OpenAlex ID: W1971007914
Recommended article: Q4208249
Recommended article: Lower bounds on the transversal numbers of \(d\)-intervals
Recommended article: Transversals of 2-intervals, a topological approach
Recommended article: Spaces of transitive interval maps
Recommended article: Q5203262
Recommended article: Q3972900
Recommended article: A continuous generalization of the transversal property
Recommended article: Q4907225
Recommended article: About a generalization of transversals
Recommended article: Transversal spaces and fixed point theorems
description: scientific article; zbMATH DE number 1051248