# Enumerating all Hamiltonian Cycles in a Bipartite Vertex Transitive Graph

Hi everyone!

This is my first post, apologies if I made any mistakes anywhere.

Here goes the question: Consider all length 7 binary sequences. Let $X$ be the set of sequences with hamming weight 3 and let $Y$ be the set of sequences with hamming weight 4. For each vertex in $X$, connect an edge to each element in $Y$ if they differ by only 1 bit. For example, 4 edges will be connected from $0000111$ to $1000111, 0100111, 0010111$ and $0001111$.

This will result in a Bipartite Vertex Transitive graph. To be precise, the resulting graph will be 4 regular.

How can I enumerate all Hamiltonian Cycles in this graph?

Now I am aware that a straight forward bruteforce of the 70 vertices will take forever and the generic dynamic programming approach of TSP is still quite unreachable due to the complexity being in the range of $O(2^{70})$.

The closest reference I come across is Finding and Enumerating Hamilton Cycles in 4-Regular Graphs, where the complexity is $O(1.783^{70})$, but still nowhere close to being solvable. I am now wondering if the additional conditions of the graph being vertex-transitive and bipartite might help be bring down the complexity. Also, there is quite a bit of "special knowledge" about the graph that we can deduce. For example, there cannot be a cycle of length 4.

Please note that this is related to Middle Layers Conjecture. I am interested to know all the Hamiltonian cycles for $k=4$ and $k=5$ (9 and 11 bit binary sequences).

I played around with the idea of using permutations to classify several paths into 1 so that only one representative needs to be checked: Let starting vertex be $0000111$ and suppose I found all Hamiltonian cycles of the form: $R-0001111-0000111-0010111-S$. It appears to me that I can extend this result by applying, say a permutation of bit 1 and 4 to all elements in the cycle to get a new class: $R-1000111-0000111-0010111-S$. Since this is a bijective function between the 2 classes, I would have effectively found all cycles in the new class too. I can use this technique to reduce 6 types of cycles of the forms:

$-0001111-0000111-0010111-$

$-0001111-0000111-0100111-$

$-0001111-0000111-1000111-$

$-0010111-0000111-0100111-$

$-0010111-0000111-1000111-$

$-0100111-0000111-1000111-$

into just one case. However, I cannot find a way to generalize this approach too far down to compress more paths. I am interested to know how everyone thinks of this question. Does it seem to be solvable in practical time?

Finally, my pleasure to meet all of you!

EDIT: Preliminary results 2

I had written better pruning codes and I realized that it takes only at most a couple of weeks to finish the running. However, based on extrapolation of the initial few branches I had completed, I will need some whooping 5+ TB of hard disk space just to store the results. Comparing with just measly 24 Hamiltonian cycles for $n=5$, it seems pretty clear that even if I can find all cycles for $n=9$ there is no way I can store all of them. Sad =(

-
Thanks for the helpful comment. I did not realize that I failed to put down a clear question at the start. –  Ng Yong Hao Nov 16 '11 at 18:14
I deleted my comment as soon as I saw you addressed it, figuring no one else need bother to read it. –  Barry Cipra Nov 16 '11 at 18:18
$n=7$ seems plausible and $n=9$ seems impossible if you want to actually look at all the cycles. –  Brendan McKay Nov 16 '11 at 22:54
I feel that $n=7$ seems possible too. Although if its possible it looks like it will require some non trivial effort. –  Ng Yong Hao Nov 18 '11 at 2:29
For those interested: It appears that there are > $2^{36}$ cycles and the search can easily be completed within 2 weeks. The main question happens to be shortage of storage space. – Ng Yong Hao 0 secs ago –  Ng Yong Hao Dec 27 '11 at 1:49

The case n=7 is pretty similar to counting the Hamiltonian cycles in the 6-cube (which has 64 vertices but more edges). That problem has been open for a long time, but was recently settled by Harri Haanpaa and myself. The approach is general and we just submitted a paper with the title "A Dynamic Programming Approach to Counting Hamiltonian Cycles in Bipartite Graphs".

Our approach can be applied to the current problem as well (Brendan is right, as usual, n=7 can be done but n=9 is hopeless). I ran a program that I have which does not take the automorphism group into account, but it became clear that one really has to utilize the symmetries. This would require some instance-specific programming, which I had neither time nor motivation to do. I can send you a preprint of the paper if you are interested.

And what is the number of Hamiltonian cycles in the 6-cube? 35 838 213 722 570 883 870 720

-
Many thanks for the information! From my experiments fixing 30/70 vertices reduces the brute force to instantaneous. With a number of symmetries I felt that $n=7$ should be doable. Nothing better than a confirmation though. Like what you mentioned, I found a lot of symmetries each only applicable to specific sequences. I am planning the pseudocode at the moment, actual program will probably take a while. Do you think the effort, mainly on the exploration of the symmetries, will be meaningful enough to be put into a paper? (seeing this is a rather specific case) –  Ng Yong Hao Nov 25 '11 at 13:46
Also, I noticed that there is another paper on [Hamiltonian cycles in 6-cube][1] It appears that their result of 14754666508334433250560 Hamiltonian cycles (directed) is recorded in [OEIS A066037][2] It seems to me that this is the also the question that your paper is addressing. Perhaps there are some miscalculations for their values? My apologies if I made any mistakes here. [1]: arxiv.org/abs/1003.4391 [2]: oeis.org/A066037/internal –  Ng Yong Hao Nov 26 '11 at 8:29
The mentioned arxiv paper (which is actually not a paper but rather an announcement of a couple of numbers) is in error. Actually, it is a nice little problem for students in a combinatorics class to show how one can deduce the incorrectness based on the few tiny bits of information provided in the paper/announcement. I have informed OEIS about our new results. –  Patric Ostergard Nov 27 '11 at 18:32
Interesting. I guess I will try to find the error when I have the time then. As for the preprint, I am fine to wait for the actual paper to be available online. After all, I am quite interested to play around with the problem to see how far I can go. Thanks for your assistance again! –  Ng Yong Hao Nov 29 '11 at 17:55

This is a list of suggestions, some of which may help.

First try smaller cases. For n=3 there is 1 cycle; for n=5 I don't know but I suspect it is a small multiple of 120. The nice thing is that from a given edge, there are only 4 ways to continue towards a Hamiltonian cycle, and each way gives lots of restrictions. (It might even be related to Hamilton's original problem on a dodecahedron; I am doing this all in my head and so any such statements I makeI are suspect.) Based on this scant bit of information, I expect there to be a not so small multiple of 5040 as the number you seek, perhaps as large as 5040^3.

Where possible, take advantage of the edges that can't be part of the cycle. For n=7, there are 9 ways to extend an edge to a sequence of three edges as part of a cycle; each such way affects 4 other vertices and limits their choices. If you do a small breadth first search, you might be able to exploit symmetries as in your post and reduce hundreds of cases to five or six basic cases.

If you can, figure out the automorphism group of the graph. I suspect it has order 10080. This should serve as a check on your results.

You can try some Monte Carlo simulations to guess at the number: suppose you choose 10 vertices on one side of the bipartite graph, and 20 edges coming from these vertices; how many Hamiltonian cycles can you build using those 20 edges as a base. If the number is 0 or small then you might have a feasible enumeration; if it is large then you might try estimating the logarithm of your number instead.