Clifton–Huang conjecture on hyperplane covers of the hypercube

Let f(n,k)f(n,k) be the minimum size of an almost kk-cover of Qn=0,1nQ^n={0,1}^n, meaning a set of hyperplanes that avoids the origin and covers every other point at least kk times.

Clifton–Huang conjecture. For k2k \ge 2 and nn sufficiently large,

f(n,k)=n+(k2).f(n,k) = n + \binom{k}{2}.

The conjecture concerns the large-dimension, fixed-multiplicity regime. The paper notes that Sauermann and Wigderson's algebraic lower bounds are smaller than this conjectured value, so the claim remains open.

Sources & referencesView supporting material

Primary source

Shagnik Das, Valjakas Djaljapayan, Yen-chi Roger Lin and Wei-Hsuan Yu, “Stability for hyperplane covers”, arXiv:2306.07574 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.