Melo–Winter's small-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),H(,k)=H(,k)[2k1],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)=[2k1].H^-(\infty,k)=[2^{k-1}].

The conjecture asserts that every positive integer at most 2k12^{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.

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.