Melo–Winter's small-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),H−(∞,k)=H(∞,k)∩[2k−1],H(\infty,k)=\bigcup_{n\geq k}H(n,k),\qquad H^-(\infty,k)=H(\infty,k)\cap[2^{k-1}],

where [r]={1,…,r}[r]=\{1,\dots,r\}. Melo–Winter's small-intersection conjecture.

H−(∞,k)=[2k−1].H^-(\infty,k)=[2^{k-1}].

The conjecture asserts that every positive integer at most 2k−12^{k-1} occurs as an intersection size. The paper proves that this conjecture is false, showing that a positive fraction of the small values is missing.

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.