For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows. The vertices are the binary strings of length $n$. Two vertices are adjacent if they differ in exactly $m$ consecutive bits. The indices of the $m$ consecutive positions where $x$ and $y$ differ from each other are considered modulo $n$. Just to clarify, if $n=6$ and $m=4$ we consider that $x=100101$ and $y=010110$ are adjacent since they differ from each other in positions 5, 6, 1 and 2.

The resulting graph has $2^n$ vertices and $n\cdot 2^{n-1}$ edges. Clearly, for $m=1$ one obtains the regular $n$-dimensional hypercube. What is the number of connected components of this graph for general $m$ and $n$?

The problem arose during a discussion in the graph theory class I am teaching this semester. I believe the problem has been considered before, but I was unable to locate any reference.

  • 1
    $\begingroup$ This is equivalent to finding the size of the kernel of a circulant matrix over $\mathbb{Z}/2$ whose rows have $m$ consecutive $1$s. $\endgroup$ – Douglas Zare Mar 16 '14 at 14:25

Let $d$ be the GCD $(m,n)$. If $m/d$ is even, then the number of connected components is $2^d$. If $m/d$ is odd, there are $2^{d-1}$ connected components.

Consider $C$, the circulant matrix over $\mathbb{Z}/2$ whose first row is $(1,1,...,1,0,0,...,0)$. The range of $C$ is the set of points connected to $\vec 0$, so the size of the kernel counts the connected components. To have image $\vec 0$ or $\vec 1$, that is, so that for all $i$ the $i$th coordinate of the image equals the $i+1$st, a vector must satisfy only that $a_i = a_{i+d}$. If $m/d$ is even, all such vectors are in the kernel, and none have image $\vec{1}$. If $m/d$ is odd, then there is an additional condition that an even number of the first $d$ coordinates are $1$ so that the image is $\vec 0$ instead of $\vec 1$.

  • $\begingroup$ Thank you Douglas, that helps a lot. Just to make sure although this may very well be quite obvious: all connected components have the same cardinality, correct? $\endgroup$ – Dan Ismailescu Mar 16 '14 at 16:13
  • $\begingroup$ @Dan Ismailescu: Yes, all connected components have the same cardinality. They are all translates of the range of $C$. $\endgroup$ – Douglas Zare Mar 16 '14 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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