pith. sign in

arxiv: 1904.12885 · v2 · pith:S4FET7Y6new · submitted 2019-04-29 · 🧮 math.CO

On almost k-covers of hypercubes

classification 🧮 math.CO
keywords affinehyperplanesminimumcombinatorialnullstellensatzproblemversionalmost
0
0 comments X
read the original abstract

In this paper, we consider the following problem: what is the minimum number of affine hyperplanes in $\mathbb{R}^n$, such that all the vertices of $\{0, 1\}^n \setminus \{\vec{0}\}$ are covered at least $k$ times, and $\vec{0}$ is uncovered? The $k=1$ case is the well-known Alon-F\"uredi theorem which says a minimum of $n$ affine hyperplanes is required, proved by the Combinatorial Nullstellensatz. We develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and completely solve the fractional version of this problem, which also provides an asymptotic answer to the integral version for fixed $n$ and $k \rightarrow \infty$. We also use a Punctured Combinatorial Nullstellensatz developed by Ball and Serra, to show that a minimum of $n+3$ affine hyperplanes is needed for $k=3$, and pose a conjecture for arbitrary $k$ and large $n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.