0
$\begingroup$

I've been tasked with this question but I have no idea how to answer it.

What is the maximum possible hamming distance between two points from level i in a n-cube?

  • 0
    "node from level i"2011-09-28

1 Answers 1

4

The only definition of level that I’ve seen in this context is the following one, which I’ll assume for this answer:

Level $i$ of the $n$-cube is the set of vertices that have $i$ coordinates equal to $1$ and $n-i$ coordinates equal to $0$.

If $i\le n/2$, you can change all $i$ of the $1$’s to $0$’s and $i$ of the $0$’s to $1$’s to get two nodes in level $i$ at Hamming distance $2i$, and it’s pretty clear that you can’t do better than this. If $i>n/2$, any two sets of $i$ coordinates must have an overlap of at least $2i-n$ places. The node $(1,1,\dots,1,0,\dots,0)$ with $i$ $1$’s followed by $n-i$ $0$’s and its reversal are then members of level $i$ at Hamming distance whose middle $2i-n$ coordinates are identical, so the Hamming distance between these nodes is $n-(2i-n) = 2n-2i$; again it’s pretty clear that this is the best you can do. (In this case you’re changing all $n-i$ of the $0$’s of each node to $1$’s and $n-i$ of the $1$’s to $0$’s.)

The two results can be combined: the maximum Hamming distance between two nodes on level $i$ is $2 \min\{i,n-i\}$.

  • 0
    An equivalent definition of a node at level $i$ is that one traverses $i$ edges (climbs $i$ levels) of the $n$-dimensional hypercube with vertices $\{0,1\}^n$ in moving from the origin $(0,0,\ldots, 0)$ to a node at level $i$.2011-09-28