Melo–Winter's large-intersection conjecture for hypercubes

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 HnS|\mathbb{H}^n\cap S| as SS ranges over the kk-dimensional linear subspaces of Rn\mathbb{R}^n. Define

H+(,k)=(nkH(n,k)){1,,2k1}.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)={2k1+2i:i{0,1,,k1}}.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 2k12^{k-1} has one of these forms. The paper shows that this is almost true, but identifies an additional possible form, 352k635\cdot 2^{k-6}, so the conjecture is refuted.

Sources & referencesView supporting material

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.