Covering half-grids with lines and planes

Abstract

We study hyperplane covering problems for finite grid-like structures in ${\mathbb{R}}^d$. We call a set $\mathcal{C}$ of points in ${\mathbb{R}}^2$ a conical grid if the line $y=a_i$ intersects $\mathcal{C}$ in exactly $i$ points, for some $a_1>\cdots >a_n\in \mathbb{R}$. We prove that the number of lines required to cover every point of such a grid at least $k$ times is at least $nk\left(1-\frac{1}{e}-O(\frac{1}{n})\right)$. If the grid $\mathcal{C}$ is obtained by cutting an $m\times n$ grid of points in half along one of the diagonals, then we prove the lower bound of $mk\left(1-e^{-\frac{n}{m}}-O(\frac{n}{m^2})\right)$. In general, we call a grid obtained by cutting a grid in ${\mathbb{R}}^d$ along one of the diagonals a half-grid. Motivated by the Alon-Füredi theorem on hyperplane coverings of grids that miss a point and its multiplicity variations, we study the problem of finding the minimum number of hyperplanes required to cover every point of an $n\times \cdots \times n$ half-grid in ${\mathbb{R}}^d$ at least $k$ times while missing a point $P$. For almost all such half-grids, with $P$ being the corner point, we prove asymptotically sharp upper and lower bounds for the covering number in dimensions $2$ and $3$. For $k=1$, $d=2$, and an arbitrary $P$, we determine this number exactly by using the polynomial method bound for grids.

14 pages; major revisions based on referee comments