An optimal generalization of Alon and Füredi's covering result
share
Given an n-cube 𝒬^n := {0,1}^n in ℝ^n, the k-th layer 𝒬^n_k of 𝒬^n denotes the set of all points in 𝒬^n whose coordinates contain exactly k many ones. In this short note, we consider the following problem: what is the minimum number of hyperplanes in ℝ^n required to cover every point in 𝒬^n∖𝒬^n_k at least t times and the points in 𝒬^n_k exactly (t-1) times? We prove that the answer to the above question is max{ k, n-k}+2t-2. Note that by putting k = 0 and t=1, we recover the much celebrated combinatorial geometry result of Alon and Füredi (European Journal of Combinatorics 1993) where they proved that the minimum number of hyperplanes required to cover every point of n-cube except the origin is n. We also study a new interesting variant of restricted sumset problem motivated from the ideas behind the proof of the above result.
READ FULL TEXT