Open Collections

Covering cubes by hyperplanes

Banff International Research Station for Mathematical Innovation and Discovery

Note that the vertices of the $n$-dimensional cube $\{0, 1\}^n$ can be covered by two affine hyperplanes $x_1=1$ and $x_1=0$. However if we leave one vertex uncovered, then suddenly at least $n$ affine hyperplanes are needed. This was a classical result of Alon and F\"uredi, followed from the Combinatorial Nullstellensatz. In this talk, we consider the following natural generalization of the Alon-F\"uredi theorem: what is the minimum number of affine hyperplanes such that the vertices in $\{0, 1\}^n \setminus \{\vec{0}\}$ are covered at least $k$ times, and $\vec{0}$ is uncovered We answer the problem for $k \le 3$ and show that a minimum of $n+3$ affine hyperplanes is needed for $k=3$, using a punctured version of the Combinatorial Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and solve the problem asymptotically for fixed $n$ and $k \rightarrow \infty$, and pose a conjecture for fixed $k$ and large $n$. Joint work with Alexander Clifton (Emory University).

Mathematics; Combinatorics; Probability theory and stochastic processes

video/mp4

Author affiliation: Emory university

2020-03-03

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73666

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/