Problems in extremal and probabilistic combinatorics: cubes, squares and permutations - Johnston, T (2021)
We begin by studying the possible intersection sizes of a $k$-dimensional linear subspace with the hypercube $\{0,1\}^n$. For a fixed $k$, the largest intersection size is $2^k$ and it was shown by Melo and Winter that the second largest intersection size is $2^{k-1} + 2^{k-2}$. We show that all intersections sizes larger than $2^{k-1}$ are of the form $2^{k-1} + 2^{i}$ or $35 · 2^{k-6}$, completely determining the ``large'' intersection sizes and disproving a conjecture of Melo and Winter. We also show that the only possible intersection size in the interval $( 15 · 2^{k-5}, 2^{k-1} )$ is $63 · 2^{k-7}$, disproving a second conjecture of Melo and Winter that all of the ``small'' values are present.