Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Douglas Zare Mar 16 at 14:25

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
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? –  Dan Ismailescu Mar 16 at 16:13
    
@Dan Ismailescu: Yes, all connected components have the same cardinality. They are all translates of the range of $C$. –  Douglas Zare Mar 16 at 17:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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