Clifton–Huang conjecture on hyperplane covers of the hypercube

About 3 years old · traced to

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 k≥2k \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.

References

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.