[seqfan] Re: eulerian orientations of hypercube graphs

[Brendan McKay]

The number of eulerian orientations of the 6-dimensional cube Q6 is
        351135773356461511142023680

Probably the fastest way is to split Q6 into 4 copies of Q4, but
putting the pieces together is rather messy so I opted for a
slower but more straightforward approach.

We can identify the vertices of Q6 with binary strings abcdef where
a,b,c,d,e,f are in {0,1}.  The edges are pairs of binary strings at
Hamming distance 1, such as abcdef-axcdef where x = 1-b.

Note that an eulerian orientation corresponds to a spanning cubic
subgraph H, and that's how we will think about it.

Q6 can be split into two copies of Q5: {0bcdef} and {1bcdef}. Call
those parts H0 and H1, and let G0,G1 be the parts of G that lie
in the two parts. H0 and H1 are joined by 32 edges of the form
0bcdef--1bcdef. Since this is a matching, G0 and G1 have the same
degree sequence consisting only of 2 and 3.

Under the automorphism group Aut(Q5), there are 1,228,158 distinct
ways to label the vertices of Q5 with 2 or 3. This can be reduced
by noting that Q5 is bipartite, so the sum of the degrees of G0
is the same on each side of the bipartition. This gives 171,349
distinct labellings of Q5 with 2 and 3.

Next, we use a basic backtrack program to count the number of
subgraphs G0 corresponding to each degree sequence. This is the
most expensive part, averaging 1 minute each.  For labelling L,
let N(L) be the number of subgraphs.  The value of N(L) ranges
from 8,820,900 to 2,907,019,740, with average about 731 million.

So far we considered only equivalence classes of labellings of Q5.
The size of the equivalence class of labelling L is
     K(L) = |Aut(Q5)| / |Aut(Q5(L))|,
where Q5(L) is Q5 labelled according to L. This is easy to compute
using nauty in less than 1 second altogether. The equivalence class
sizes and the number of times they occur are thus:

     1       2
    10       2
    16       6
    20       2
    40      10
    60       4
    80      31
   120      11
   160      53
   192       8
   240      73
   320     141
   384       4
   480     458
   640     257
   960    2877
  1920   23437
  3840  143973

Once G0 and G1 are chosen, there is exactly one way to add edges
between them to make a spanning cubic subgraph of Q6. Therefore,
the total number of eulerian orientations is the sum over all
equivalence classes of  K(L) N(L)^2.

Checking: Clearly the result should be divisible by binom(6,3)=20,
but this is not much of a check since an error in N(L) will go
unnoticed if K(L) is divisible by 20, which is almost always.

A better check is this: If L is a labelling (of 2s and 3s), call
conv(L) what you get by changing all 2s into 3s and vice-versa.
Since the subgraphs counted by N(L) are the complements of those
counted by N(conv(L)), the counts should be the same. We checked
this for all L. (This idea could be used to cut the running time in
half at the expense of losing this check.)

Of the 171,349 equivalence clases of labelling L and conv(L) are
actually equivalent in 1857 cases. It is plausible that the counting
program could follow the same path, encountering the same bug,
for both L and conv(L). So in these cases we also ran the counting
program with H0 and H1 interchanged.

Cheers, Brendan.