Dimension-stability conjecture for exact hypercube covering numbers

About 5 years old · traced to

For B⊂{0,1}kB\subset\{0,1\}^k and an integer n≥kn\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}n−k))=n−k+ec⁡({0,1}k∖B).\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 n−kn-k coordinate hyperplanes. The conjecture asks whether embedding the problem in higher dimensions can ever improve this bound; the source gives no resolution.

References

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.