For any $n$, and any $1 \leq k \leq 2^n$, and any $1 \leq q \leq n-1$, we want $k$ binary vectors of length $n$, organized in a matrix $M$ with $k$ rows and $n$ columns, that will minimize $p(M,q)$ over all binary matrices $M$ on $k$ distinct rows and $n$ columns, where $p(M,q)$ is the sum, over all $n \choose q$ choices of $q$ columns, of the number of vectors in the projection of those columns. For example, for $M$ being
\begin{bmatrix}
0 & 0 & 0\\
1 & 1 & 0\\
1 & 1 & 1\\
\end{bmatrix}
we get $p(M,2)=8$ since choosing the first two columns we have 2 distinct rows in the projection, whereas the other two choices of two columns gives 3 distinct rows each.
When $q=n-1$ this minimization question is equivalent to asking for the induced subgraph on $k$ vertices of the hypercube of dimension $n$ having the maximum number of edges, since $p(M,n-1)$ is $k$ times $n$ minus the number of edges in the subgraph induced by the nodes corresponding to the rows of $M$ (as the dimension this edge crosses, when that column is left out, we get two identical rows). This has been shown (Sergiu Hart, A note on the edges of the hypercube, Discrete Math. 1976) to be achieved by the $k$ vectors corresponding to the binary representation of the k numbers from 0 to $k-1$, with leading 0s to give them length $n$. His result implies that the matrix $M$ with these vectors as rows will achieve the minimum value of $p(M,q)$ for any $q$ between $\lceil \log_2 k\rceil-1$ and $n-1$, and it is easy to show that it also achieves the minimum value of $p(M,1)$.
But what about $q=2$, or any other $q$ smaller than $\log_2 k -1$?
Do we know that the same set of vectors will again achieve the minimum, over all binary $M$ on $k$ distinct rows and $n$ columns? Or maybe simpler, do we know it if $k$ is a power of 2?
2026-03-26 22:58:42.1774565922