2
$\begingroup$

Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle cover" is a set of cycles in $Q_n$ such that each vertex is a member of one and only one cycle.

To fix some notation, like $N=2^n$ and let $C_n$ be the count of the number of vertex cycle covers on $Q_n$.

Note that there are about $(n/e)^N$ Hamiltonian cycles in $Q_n$ (cf Feder and Subi, 2008 for more precise upper and lower bounds), which provides a lower bound on $C_n$. Per a comment of Jon Noel's below, it may be worth mentioning that there are about $\sqrt{(n/e)^N}$ perfect matchings on $Q_n$ (this is also referenced in Feder and Subi's paper).

I am considering $Q_n$ with labelled vertices (i.e., I am counting vertex cycle covers with "no symmetries"), and considering only "proper" cycles, which on $Q_n$ means of length $\geq 4$. So, for example, there is only one vertex cycle cover on $Q_2$, namely the full 4-cycle.

$\endgroup$
  • $\begingroup$ Is the only constraint on the cycle set that it cover? Or is some disjointness or optimality assumed? If not, I can imagine some inclusion exclusion formula which accounts for noncovering cycle sets. In which case I imagine the growth is doubly exponential. Gerhard "I Mean Really Really Big" Paseman, 2017.07.10. $\endgroup$ – Gerhard Paseman Jul 10 '17 at 22:45
  • $\begingroup$ @GerhardPaseman Sorry, by "vertex cycle cover", I meant a set of cycles such that each vertex is in precisely one cycle. I'll update the question to clarify that. (And the lower bound from Hamiltonian cycles shows that the growth is at least doubly exponential in $n$, so that's true!) $\endgroup$ – Bill Bradley Jul 11 '17 at 4:15
  • $\begingroup$ OK. I assume cycles of 2 vertices are not allowed? And what symmetries are you wanting? I can see an answer of 2 for the 8 vertex cube, as well as a larger number if instead the vertices are labeled. Gerhard "What Does Different Mean Here?" Paseman, 2017.07.10. $\endgroup$ – Gerhard Paseman Jul 11 '17 at 5:34
  • $\begingroup$ As an upper bound, you could take the number of perfect matchings squared. Of course this will count cycle covers with many components many times, and will count things which are not cycle covers (i.e. it will treat cycles of length 2 as being cycles, c.f. Gerhard's comment). $\endgroup$ – Jon Noel Jul 11 '17 at 8:36
  • $\begingroup$ @GerhardPaseman Thanks for pointing out another ambiguity-- I meant "labelled nodes" and have modified the question above. $\endgroup$ – Bill Bradley Jul 12 '17 at 6:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.