[seqfan] Re: eulerian orientations of hypercube graphs

[hv at crypt.org]

I can confirm d=4 gives 2970. (Takes less than 0.01s.)

I can also confirm d=6 will be a serious challenge: I stopped my naive
implementation after 10s, and again after 60s, to see what was the
highest up the stack it had managed to recurse. (Very) crude extrapolation
suggests it would take 2^37 minutes to complete, or about 260,000 years.

I'm intrigued to see how far that can be reduced: it is entirely
possible that further optimization could bring it down to a sane time.

Since we are symmetric in all dimensions, we can pick any valid set
of the 6 edges from the first vertex, and multiply the result by 6C3.
(I already assume this in the extrapolated time above.)

The trick beyond that, I suspect, is to find the most constrained edge
to try next (recursively) in an efficient manner.

Hugo

Brendan McKay via SeqFan <seqfan at list.seqfan.eu> wrote:
:I'm wondering if anyone has information on the sequence of the title or 
:would like to work on it.
:
:I can't find anything in OEIS.
:
:Some definitions.  A hypercube graph is the skeleton (vertices and 
:edges) of a hypercube.
:So for dimension 2, it is a square, and for dimension 3 it is the 
:familiar graph with 8 vertices
:and 12 edges.  In dimension d, there are 2^d vertices and each vertex 
:has degree d.
:Another description is that the vertices are the binary vectors of 
:length d and edges
:join vectors at Hamming distance 1.
:
:When a graph has each vertex of even degree, it is possible to orient 
:the edges so that
:each vertex has equal numbers of incoming and outgoing edges. That's 
:called an
:eulerian orientation.  These orientations are of importance in 
:statistical physics, though
:I don't know of an application for the hypercube case.
:
:For the d-dimensional hypercube to have eulerian orientations, d must be 
:even.
:For d=2, there are two eulerian orientations (the cyclic ones).  If my 
:little program
:isn't buggy, for d=4 there are 2970 eulerian orientations (can someone 
:check?).
:According to A307334 <https://oeis.org/A307334> this is also the number 
:of proper 3-colourings - coincidence?
:
:Doing d=4 was a sub-second task but d=6 may be  a serious challenge.
:
:Cheers, Brendan.
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/