On point covers of multiple intervals and axis-parallel rectangles
Let \(H\) be a hypergraph on an underlying set \(X\). A set \(S \subset X\) is said to cover an edge \(E\) of \(H\) if it intersects \(E\). The transversal number \(\tau(H)\) is the minimum size of sets which cover all edges of \(H\). The packing number \(\nu(H)\) is the maximum number of sets of pairwise disjoint edges of \(H\). A hypergrah \(H\) on \(X\) is said to be rectangular if \(X\) can be placed in the plane so that every edge of \(H\) is of the form \(X \cap R\), where \(R\) is a suitable rectangle with sides parallel to the coordinate axes. The main result of the paper is the following: For any rectangular hypergraph \(H\), \(\tau(H) \leq 4 \nu(H)(\lfloor \log \nu(H) \rfloor +1)^2 \).
scientific article; zbMATH DE number 936872