Dimension-stability conjecture for exact hypercube covering numbers

For B{0,1}kB\subset\{0,1\}^k and an integer nkn\geq k, let ec(B)\operatorname{ec}(B) be the minimum number of hyperplanes whose union intersects the Boolean cube precisely in BB. Dimension-stability conjecture.

ec({0,1}n(B×{0}nk))=nk+ec({0,1}kB).\operatorname{ec}\bigl(\{0,1\}^{n}\setminus(B\times\{0\}^{n-k})\bigr)=n-k+\operatorname{ec}\bigl(\{0,1\}^{k}\setminus B\bigr).

The right-hand side is an immediate upper bound obtained by extending a cover in kk dimensions and adding the nkn-k coordinate hyperplanes. The conjecture asks whether embedding the problem in higher dimensions can ever improve this bound; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Adam Zsolt Wagner, “Constructions in combinatorics via neural networks”, arXiv:2104.14516 (2021).

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.