Transversals of d-intervals
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.
- scientific article; zbMATH DE number 1195536
- Lower bounds on the transversal numbers of \(d\)-intervals
- Transversals of 2-intervals, a topological approach
- Spaces of transitive interval maps
- scientific article; zbMATH DE number 4196307
- scientific article; zbMATH DE number 16247
- A continuous generalization of the transversal property
- Transversal sets
- About a generalization of transversals
- Transversal spaces and fixed point theorems
- Transversals for ordinal intervals
- The (p, q) property in families of d-intervals and d-trees
- Transversals of 2-intervals, a topological approach
- Piercing numbers in approval voting
- The maximum clique problem in multiple interval graphs
- Recent techniques and results on the Erdős-Pósa property
- Edge-covers in \(d\)-interval hypergraphs
- Intersection reverse sequences and geometric applications.
- A bijection between the \(d\)-dimensional simplices with distances in \(\{1,2\}\) and the partitions of \(d+1\)
- Red-blue clique partitions and (1-1)-transversals
- Identifying codes in hereditary classes of graphs and VC-dimension
- scientific article; zbMATH DE number 1195536 (Why is no real title available?)
- Using Brouwer’s Fixed Point Theorem
- Gallai-type results for multiple boxes and forests
- Lower bounds on the transversal numbers of \(d\)-intervals
- Bounds on piercing and line-piercing numbers in families of convex sets in the plane
- A sparse colorful polytopal KKM theorem
- Piercing translates and homothets of a convex body
- Fractional covers and matchings in families of weighted \(d\)-intervals
- Fractionally balanced hypergraphs and rainbow KKM theorems
- Existence of partial transversals
This page was built for publication: Transversals of \(d\)-intervals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1364141)
