On point covers of multiple intervals and axis-parallel rectangles (Q1924491)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On point covers of multiple intervals and axis-parallel rectangles |
scientific article |
Statements
On point covers of multiple intervals and axis-parallel rectangles (English)
0 references
25 June 1997
0 references
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 \).
0 references
hypergraph
0 references
transversal number
0 references
packing number
0 references
rectangle
0 references