Piercing boxes and products of trees

Abstract

We give a new upper bound on the piercing number $\tau (\mathcal{F})$ of a finite family $\mathcal{F}$ of axis-parallel rectangles in the plane when every $p$ members contain an intersecting pair. Namely, we prove $\tau (\mathcal{F})=O(p(\log \log p)(\log \log \log p))$, improving the factor $(\log \log p{)}^2$ in the best previously known bound to $(\log \log p)(\log \log \log p)$. For each $d>2$, when $\mathcal{F}$ is a finite family of axis-parallel boxes in ${\mathbb{R}}^d$, this yields $\tau (\mathcal{F})=O(p(\log p{)}^{d-2}(\log \log p)(\log \log \log p))$. We also study an analogous problem replacing ${\mathbb{R}}^d=\mathbb{R}\times \cdots \times \mathbb{R}$ with the Cartesian product $T_1\square \cdots \square T_d$ of trees $T_1,\dots ,T_d$, and boxes with objects of the form $S_1\square \cdots \square S_d$ where $S_i$ is a subtree of $T_i$. For a finite family of such objects under the same intersection assumption as above, we establish an upper bound $\tau (\mathcal{F})=O(p(\log p{)}^{d-1})$ for each $d$. We also construct examples showing that this upper bound cannot be improved in order of magnitude.

arXiv comment11 pages