I am wondering if the following is true, and if yes how to prove it:
Construct a graph where the vertices are binary numbers of length $n$ and have a hamming weight (i.e. digit sum) between $a$ and $b$:
$$V = \{ a \leq i \leq b \mid i \text{ is binary number of length } n\}$$
Edges are given by appending a $0$ or $1$ from the right to the binary number, e.g. (0001) $\overset{1}{\longrightarrow}$ (0011) and (0001) $\overset{0}{\longrightarrow}$ (0010).
Is this graph strongly connected, for $a < b$? If yes, how to prove it?
I know that for $a=b$ it is not true in general. But from some examples I think that for $a<b$ it is true. Any hints are welcome.
Best Answer
Let us focus on a particular example, say $n=5$, $a=2$, and $b=3$. The same logic will apply to the general case, to show that whenever $a<b$, the graph is strongly connected.
Start with some particular string, say $11000$. Consider the following sequence of $n=5$ moves. $$ 11000\stackrel1\to 10001\stackrel1\to 00011\stackrel0\to 00110\stackrel{\color{red}1}\to 0110\color{red}1\stackrel0\to 110\color{red}10 $$ As we make moves, the positions of the numbers shift, but since we made exactly $n$ moves, the numbers when all the way around and returned to their original spots. Furthermore, for most of these moves, the bit we appended to the left was the same as the bit we removed from the right. Only for the red move did I remove the opposite digit. The net result is that we have almost the same string, except a single zero was replaced with a $1$ (marked in red).
Using a similar strategy, you can insert a one or zero at any spot, as long as this does not bring the Hamming weight below $a$, or above $b$. This allows you to move the ones around arbitrarily; to move a one from position $i$ to position $j$, you either first place a zero at $i$, then a one at $j$, or the other way around (whichever is allowed by that $a$ and $b$). Since you can arbitrarily move the digits around, you can get from any string to any other, so the graph is strongly connected.