3
$\begingroup$

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$.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's exactly the question. I'm engineering undergrad so I didn't know the technical graph theory terms. It seems my construction is sightly better than the shown lower bound; is this significant, should I email this to the author? With some effort I'm convinced now you could show $k(n)=a(n)$. $\endgroup$ – Real Jun 16 '15 at 1:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.