New Helly-type results for discrete boxes: Quantitative colorful and $(p,q)$-variants

Abstract

In 2008, Halman showed that for any finite set $P\subset {\mathbb{R}}^d$ and any finite family $\mathcal{B}$ of axis-parallel boxes in ${\mathbb{R}}^d$, if the intersection of $P$ and any subfamily ${\mathcal{B}}^{\prime }\subseteq \mathcal{B}$ of size at most $2d$ is non-empty, then the intersection of $P$ and $\mathcal{B}$ is also non-empty. Very recently Edwards and Soberón initiated the study of quantitative colorful version for $2d$ families, $(p,q)$-type variation for $p\ge q\ge d+1$, and other extensions of this Helly-type result by Halman. In this paper, we study the quantitative colorful Halman problem for $2d-1$ families as well its $(p,q)$-type variation for $p\ge q\ge 2$. Specifically, our main result asserts that for any finite set $P$ and finite families of boxes ${\mathcal{B}}_1,\dots ,{\mathcal{B}}_{2d-1}$ in ${\mathbb{R}}^d$, where $d\ge 2$, if every transversal $\mathcal{B}$ for the families has an intersection $\bigcap \mathcal{B}$ containing at least $n$ points of $P$, then there exist $j\in [2d-1]$ and a subset of $P$ of size at most \[ 2n+\Big\lfloor \frac{n-1}{d \cdot 2^{d-1}} \Big\rfloor, \] such that each box of ${\mathcal{B}}_j$ contains at least $n$ points of this subset.