scientific article; zbMATH DE number 1054780
Let \(P\) be a set of finitely many cells in the square grid. The rectangle covering number \(\theta(P)\) is the minimum number of rectangles, each of them contained in \(P\), that together cover \(P\). The antirectangle number \(\alpha(P)\) is the maximum cardinality of a subset of cells of \(P\) such that no rectangle that is totally contained in \(P\) can cover two of the cells of the subset. Obviously \(\theta(P) \geq \alpha(P)\), and examples are known in which \(\theta(P) > \alpha(P)\). Erdős conjectured that \(\theta(P) \leq c\alpha(P)\) for some \(c>0\). In this paper, the author shows that \(\theta(P) \leq c \alpha(P) \log(\alpha(P))\) for some \(c>0\). For the entire collection see [Zbl 0868.00054].
- Covering simply connected regions by rectangles
- On point covers of parallel rectangles
- A new approach to the results of Kövari, Sós, and Turán concerning rectangle-free subsets of the grid
- It’s Hard to Color Antirectangles
- scientific article; zbMATH DE number 5291457 (Why is no real title available?)
- A minimax theorem on intervals
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4352328)
