1
$\begingroup$

Let $k\leq n$ be positive integers with $n\geq 2$, and let $[n]=\{1,\ldots,n\}$. Let $V_n=\{0,1\}^{[n]}$ be the set of all functions $f:[n]\to\{0,1\}$, and let $$E_{k,n} =\big\{\{f,g\}: f,g\in V_n\text{ and } |\{m\in [n]:f(m)\neq g(m)\}|=k\big\}.$$ We call $G_{k,n} = (V_n,E_{k,n})$ the $(k,n)$-binary graph. It is easy to see that if $k,n$ have common divisors, then $G_{k,n}$ is not connected (there is no path from the constant $0$-function to the function $g:[n]\to\{0,1\}$ where $g(1)=1$ and $g(m) = 0$ for $m\in[n]\setminus \{1\}$).

Question. If $k, n$ are relatively prime, is $G_{k,n}$ connected? If yes, what is the length of the longest path?

(Will accept the first correct answer that addresses the first question, but will also upvote useful answers on the second question.)

$\endgroup$
2
  • $\begingroup$ I suspect this is a Gray code in disguise, and that you can get an answer which is one or two less than N, the number of all vertices for longest path, or at least N - O(log N). Gerhard "Should Try Some Small Examples" Paseman, 2018.10.02. $\endgroup$ Oct 2, 2018 at 15:43
  • $\begingroup$ Also, for the (3,6) graph, I see a path, contrary to your claim. I suspect the graph is disconnected iff k is even (by an easy coloring argument), and that it has at most two connected components. Gerhard "Taking A Big Leap Here" Paseman, 2018.10.02. $\endgroup$ Oct 2, 2018 at 15:47

1 Answer 1

1
$\begingroup$

No, the coprimality of $k$ and $n$ does not imply that $G_{k,n}$ is connected. For a counterexample we consider the case $(k,n)=(2,3)$.

Represent a function $f\in V_3$ by the sequence $(f(1),f(2),f(3))$. Then $V_{2,3}$ is the disjoint union of two complete graphs with $4$ vertices each. The first one has vertices $(0,0,0)$, $(1,1,0)$, $(1,0,1)$, and $(0,1,1)$; the second one has vertices $(1,1,1)$, $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$.

More generally, if $k$ is even, then the parity of the sum of the entries remains invariant when passing along an edge. Hence $G_{k,n}$ is not connected.

$\endgroup$
4
  • $\begingroup$ Can you confirm my conjecture above about even k? Gerhard "Almost Sure It Is Obvious" Paseman, 2018.10.02. $\endgroup$ Oct 2, 2018 at 16:00
  • $\begingroup$ Never mind. Let F be the subset with an even number of zeros and G a component with an odd number of zeros. F and G are connected components, and F is connected to G iff k is odd. I think the longest path can be found by an appropriate traversal of F and G. Gerhard "Coffee Not Working Fast Today" Paseman, 2018.10.02. $\endgroup$ Oct 2, 2018 at 16:06
  • $\begingroup$ @GerhardPaseman Sorry, when writing the answer I had not really noticed your second comment that an easy parity argument works for all even $k$. So I have made the answer CW and added the remark about even $k$. $\endgroup$ Oct 2, 2018 at 16:14
  • $\begingroup$ No biggie. You might observe that F and G have Hamiltonian cycles (sort of) which I think lead to a quick proof of longest path, or at least a good lower bound. Gerhard "Prefers Easy Arguments This Morning" Paseman, 2018.10.02. $\endgroup$ Oct 2, 2018 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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