Umeå University's logo

Given a family B of axis-parallel boxes in R^d, let τ denote its piercing number, and ν its independence number. It is an old question whether τ/ν can be arbitrarily large for given d≥2. Here, for every ν, we construct a family of axis-parallel boxes achieving τ≥Ω_d(ν)⋅(log v/log log v)^d−2. This not only answers the previous question for every d≥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 R^d, whose intersection graph has clique and independence number O_d(n^1/2)⋅(log n/log log n)^−(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 ω satisfying (log n/log log n) ≪ω≪n^1−ε, we construct an intersection graph of n boxes with clique number at most ω, and chromatic number Ω_d,ε(ω)⋅(log n/ log log n)^d−2. This matches the best known upper bound up to a factor of O_d((log⁡ω)(log⁡ log ⁡n)^d−2).