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

Improve this question
$\endgroup$
6
  • $\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
    Commented Jul 10, 2017 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
    Commented Jul 11, 2017 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
    Commented Jul 11, 2017 at 5:34
  • 1
    $\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
    Commented Jul 11, 2017 at 8:36
  • $\begingroup$ @GerhardPaseman Thanks for pointing out another ambiguity-- I meant "labelled nodes" and have modified the question above. $\endgroup$
    – Bill Bradley
    Commented Jul 12, 2017 at 6:39

1 Answer 1

Reset to default
3
$\begingroup$

The question doesn't ask for exact values in small cases. But it also doesn't NOT ask for them. I wonder about exact values as far as possible, given as nicely as possible, which certainly isn't very far. Below is the answer for $n=3$ and a partial answer for $n=4.$ The number of Hamiltonian cycles is given by A066037 which only goes to $n=6$, which is no surprise. For $Q_3$ there are $6$ Hamiltonian cycles and $9$ cycle covers since there are also $3$ ways to cover with a pair of $4$-cycles. For $Q_4$ there are $1344=2^6\cdot 3 \cdot 7$ Hamiltonian cycles. By my calculation, the number of cycle covers for $Q_4$ is $2970=2\cdot3^3\cdot 5 \cdot 11$.

The sequence $1,9,2970$ is not currently in the OEIS. The number of Hamilton cycles for $Q_5$ is $2^5 \cdot3 \cdot 5 \cdot 617 \cdot 3061.$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, thank you for doing that! $\endgroup$
    – Bill Bradley
    Commented Apr 22 at 12:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .