Transversals of \(d\)-intervals (Q1364141): Difference between revisions

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.