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](https://oeis.org/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$.



Maximal neighbour-full partition of $\{0,1\}^n$
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.


