What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$)
We say $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 illustrative application is a computer memory that does not corrupt when being powered off while being written, if 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}}$. If a machine were to also encode it's state in such a non-volatile memory, it would be insensitive to shutdown.
I can show 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?