The three-cover multiplicity conjecture for hypercubes

Let Qn={0,1}nQ^n=\{0,1\}^n be the vertex set of the nn-dimensional hypercube, and let g(n,m,k)g(n,m,k) be the minimum number of vertices covered fewer than kk times by mm affine hyperplanes not passing through 0\vec{0}. For nm1n\geq m\geq 1, the conjecture concerns the range 1mn+31\leq m\leq n+3.

Three-cover multiplicity conjecture.

g(n,m,3)={2n,m=1,2;2n1,m=3;2nm+3,m=4,,n+3.g(n,m,3)= \begin{cases} 2^n, & m=1,2;\\ 2^{n-1}, & m=3;\\ 2^{n-m+3}, & m=4,\ldots,n+3. \end{cases}

The first two cases and the stated lower and upper bounds motivate the conjecture; the paper does not report a proof of the full piecewise formula, so it remains open.

Sources & referencesView supporting material

Primary source

Alexander Clifton and Hao Huang, “On almost k-covers of hypercubes”, arXiv:1904.12885 (2019).

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.