Melo–Winter's large-intersection conjecture for hypercubes

About 8 years old · traced to

Let Hn={0,1}n\mathbb{H}^n=\{0,1\}^n be the vertices of the nn-dimensional hypercube, and let H(n,k)H(n,k) be the set of intersection sizes ∣Hn∩S∣|\mathbb{H}^n\cap S| as SS ranges over the kk-dimensional linear subspaces of Rn\mathbb{R}^n. Define

H+(∞,k)=(⋃n≥kH(n,k))∖{1,…,2k−1}.H^+(\infty,k)=\left(\bigcup_{n\geq k}H(n,k)\right)\setminus\{1,\dots,2^{k-1}\}.

Melo–Winter's large-intersection conjecture.

H+(∞,k)={2k−1+2i:i∈{0,1,…,k−1}}.H^+(\infty,k)=\{2^{k-1}+2^i:i\in\{0,1,\dots,k-1\}\}.

The conjecture predicts that every possible intersection size larger than 2k−12^{k-1} has one of these forms. The paper shows that this is almost true, but identifies an additional possible form, 35⋅2k−635\cdot 2^{k-6}, so the conjecture is refuted.

References

Primary source

Carla Groenland and Tom Johnston, “Intersection sizes of linear subspaces with the hypercube”, arXiv:1810.02729 (2018).

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.