No label defined (Q4352328)

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].