Colorful two-piercing theorem for boxes

Abstract

We prove a colorful extension of a Helly-type theorem by Danzer and Grünbaum (Combinatorica, 1982) concerning two-piercing families of axis-parallel boxes in ${\mathbb{R}}^d$. We also show that our result is tight by constructing extremal families that achieve the bound. Related work includes a graph-theoretic proof of the original theorem by Pendavingh, Puite, and Woeginger (Discrete Applied Mathematics, 2008), and a two-piercing result for lower-dimensional boxes by Baños and Oliveros (Acta Mathematica Hungarica, 2018).

Major revision. Large parts of the paper have been rewritten to improve clarity and presentation. The two-piercing result is retained, while the material on three-piercing has been removed. This paper will appear in Discrete Applied Mathematics