Covering triangular grids with multiplicity

Abstract

Motivated by classical work of Alon and Füredi, we introduce and address the following problem: determine the minimum number of affine hyperplanes in ${\mathbb{R}}^d$ needed to cover every point of the triangular grid $T_d(n):=\{(x_1,\dots ,x_d)\in {\mathbb{Z}}_{\ge 0}^d\mid x_1+\cdots +x_d\le n-1\}$ at least $k$ times. For $d=2$, we solve the problem exactly for $k\le 4$, and obtain a partial solution for $k>4$. We also obtain an asymptotic formula (in $n$) for all $d\ge k-2$. The proofs rely on combinatorial arguments and linear programming.

23 pages, 3 figures