Lower bounds for piercing and coloring boxes

Abstract

Given a family $\mathcal{B}$ of axis-parallel boxes in ${\mathbb{R}}^d$, let $\tau$ denote its piercing number, and $\nu$ its independence number. It is an old question whether $\tau /\nu$ can be arbitrarily large for given $d\ge 2$. Here, for every $\nu$, we construct a family of axis-parallel boxes achieving $$\tau \ge {\Omega }_d(\nu )\cdot {\left(\frac{\log \nu }{\log \log \nu }\right)}^{d-2}.$$ This not only answers the previous question for every $d\ge 3$ positively, but also matches the best known upper bound up to double-logarithmic factors. Our main construction has further implications about the Ramsey and coloring properties of configurations of boxes as well. We show the existence of a family of $n$ boxes in ${\mathbb{R}}^d$, whose intersection graph has clique and independence number $O_d(n^{1/2})\cdot {\left(\frac{\log n}{\log \log n}\right)}^{-(d-2)/2}.$ This is the first improvement over the trivial upper bound $O_d(n^{1/2})$, and matches the best known lower bound up to double-logarithmic factors. Finally, for every $\omega$ satisfying $\frac{\log n}{\log \log n}\ll \omega \ll n^{1-\epsilon }$, we construct an intersection graph of $n$ boxes with clique number at most $\omega$, and chromatic number ${\Omega }_{d,\epsilon }(\omega )\cdot {\left(\frac{\log n}{\log \log n}\right)}^{d-2}.$ This matches the best known upper bound up to a factor of $O_d((\log w)(\log \log n{)}^{d-2})$.

arXiv comment11 pages, improved presentation