Maximal neighbour-full partition of $\{0,1\}^n$

Question

What is the largest complete minor of the $n$-dimensional hypercube? (which we call $k(n)$)

Alternatively, what is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements?

We say sets $A$ and $B$ are neighbors if their minimum Hamming distance is $d_H(a,b) = 1$ for some $a \in A, b \in B$. Equivalently, if $\min\limits_{\substack{\forall a \in A\\ \forall b \in B}} ||a \oplus b|| = 1$.

We say $A$ is connected if every non-null subset $B \subset A$ is neighbor to it's complement $\overline{B} = A \setminus B$ or if $|A| = 1$.

For example, if $n=1$, then $k(1)=2$ by the trivial partition $\{\{0\},\{1\}\}$. If $n=2$, then we have the valid partition $\{\{(0,0),(0,1)\},\{(1,0)\},\{(1,1)\}\}$, so $k(2)=3$. I could show $k(3)=4$.

What is an expression for $k(n)$?

An illustration is a computer memory that does not corrupt if powered off while being written, provided each bit in a word $w \in \{0,1\}^n$ of size $n$ is changed sequentially. So one asks what is the maximum efficiency of this memory, given by $\eta=\log_2{\frac{k(n)}{2^n}}$.

I can show constructively that $k(n)$ is at least:

$2,3,4,6,8,12,16,...$ (Sequence A164090)

That is, $k(n) \ge a(n)$, with $a(n) = 2 \times a(n-2)$ for $n > 2$, $a(1)=2$ and $a(2)=3$.

But I don't know how to show it's optimal. Is it possible to do better?

Note: a very simple construction actually shows $k(n) \in \Omega(2^{n/2})$. Take any $b$-sized word $w$, repeat it (making it a $2b$ sized word), and add a reliability bit, which will be $0$ if the first part is reliable and $1$ if the second part is (so $2b+1$ bits in total). Then for each word $w$ we construct a pair of sets: the first with each $2b+1$ sized element being $(w,a,0) \forall a \in \{0,1\}^b$ and the second set analogously $(a,w,1) \forall a \in \{0,1\}^b$. Then uniting each pair we have connected sets (since $(w,w,0)$ and $(w,w,1)$ are neighbors) satisfying the desired property. It follows that $k(2b+1) \ge 2^b$.

Answer 1

If I understand correctly I think the question can be re-phrased as follows, what is the largest complete minor of the $n$-dimensional hypercube?

To see this we note that any partition into $k$-sets as in the question gives a collection of branch sets for a $K_k$ minor, since each vertex class is connected, and each pair contains neighbouring vertices.

Conversely, if we have a collection of branch sets for a $K_k$ minor we can just extend some of them naively to get a partition of the vertex set, since the hypercube is connected.

The size of the largest complete minor in a graph $G$ is sometimes referred to as the Hadwiger number of $G$ in the literature, after Hadwiger's conjecture, and I found the following bound in "On the Hadwiger’s conjecture for graph products" by Chandrana and Sivadasan that (in your notation)

$$2^{\lfloor \frac{(n-1)}{2}\rfloor} \leq k(n) \leq \sqrt{n} 2^{\frac{n}{2}} +1. $$

I don't know of a better upper bound.