3
$\begingroup$

Questions:

is the following true?

  • for $n\in\mathbb{N}$ every Hamilton cycle in an $n$-dimensional hypercube $Q_n$ there exist $2^{n-1}$ edges that are mutually parallel
  • $Q_2$ is the only case in which every Hamilton cycle contains two such sets of edges, in all other cases the set of edges is unique.
Improve this question
$\endgroup$
3
  • $\begingroup$ yes to the first question (I'm not sure I get the statement of the second one). imagine $Q_n$ as having vertex set $\{0,1\}^n$. if I take an edge that flips the $i$-th bit, I must have another edge flipping this bit to close the cycle. so you can pair up the edges so that each pair "flips the same bit" (i.e., they are parallel). $\endgroup$
    – Zach Hunter
    Commented Jun 20 at 17:07
  • $\begingroup$ or maybe more evocative is to imagine $Q_n$ as the Cayley graph of $\mathbb{F}_2^n$ generated by the basis vectors $e_1,\dots,e_n$. if $l_1,\dots,l_{2^n}$ are the labels of the edges in a cycle, we must have $\sum_i l_i = 0_{\mathbb{F}_2^n}$ (since you return to the start), whence each label is used an even number of times. $\endgroup$
    – Zach Hunter
    Commented Jun 20 at 17:10
  • $\begingroup$ @ZachHunter: I think the question asks for one set of $2^{n-1}$ edges all of which are parallel, whereas your argument gives $2^{n-1}$ sets of 2 edges each. $\endgroup$
    – Florian Lehner
    Commented Jun 20 at 19:50

1 Answer 1

Reset to default
7
$\begingroup$

If there is a set of $2^{n-1}$ mutually parallel edges, then it is unique by the pigeonhole principle: a Hamilton cycle has $2^n$ edges, and contains at least one edge in each "direction".

However, for $n\geq 4$ it is possible that there is no such set. Below is a sketch for $n=4$ which is easy to generalise (I did not include all edges in the matching between the two 3-cubes so the drawing wouldn't get too messy).

Q_4

Improve this answer
$\endgroup$
2

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.