Combinatorics Seminar -- (Almost) k-covering with affine hyperplanes

Time and Location:

We discuss several questions involving covering a structured set of points with affine hyperplanes, while possibly avoiding other points. Covering all points of the $d$-dimensional hypercube $\{0,1\}^d$ requires just two hyperplanes, but Alon and F\"{u}redi showed that covering all but one point requires $d$ hyperplanes. We extend this question to ask for the minimum number of affine hyperplanes needed to cover each point of $\{0,1\}^d\setminus\{\vec{0}\}$ at least $k$ times while leaving $\vec{0}$ uncovered. For $k=3$, we determine this minimum exactly and further determine how close to full coverage we can get when using fewer hyperplanes.

We also consider a $k$-covering problem where the set to be covered is the entire triangular grid $T_d(n):=\{(x_1,\dots,x_d)\in\mathbb{Z}_{\ge 0}^d\mid x_1+\dots+x_d\le n-1\}$. For $d\ge k-2$, we asymptotically determine (in terms of $n$) the minimum number of hyperplanes needed.

In the process, we make use of Combinatorial Nullstellensatz, linear programming, and various combinatorial arguments.

Based on joint works with Hao Huang and with Abdul Basit and Paul Horn.