[seqfan] Re: eulerian orientations of hypercube graphs

[hv at crypt.org]

Ah, that certainly suggests brute force won't get far even with d=6.

Since all directions look alike to the first vertex, we can choose any
arrangement of the 6 edges and multiply the results by 20.

Now the three dimensions we choose for "out" edges from that vertex
are indistinguishable, as are the other three, which ought to reduce
the problem another 36-fold - but I don't see how to take advantage
of that, and it would still leave at least 4 x 10^22 to count.

Maybe if the 2970 solutions for d=4 could be classified it might
yield some insight.

Hugo

Zach DeStefano <zachdestefano at gmail.com> wrote:
:I found some bounds for this problem.
:
:According to "Bounds on the Number of Eulerian Orientations" by A.
:Schrijver (1983), the number of Eulerian orientations of a 2k-regular graph
on n vertices is between (2^-k (2k choose k))^n and sqrt((2k choose k)^n).
:
:>From this we have that the value for d = 6 is between 2.9 x 10^25 and 4.3 x
:10^41 and the value for d = 8 is between 1.2 x 10^164 and 1.5 x 10^236.
:
:- Zach
:
:On Fri, Oct 28, 2022 at 12:51 PM Hans Havermann <gladhobo at bell.net> wrote:
:
:> Is it only a coincidence that A054759(4) is also 2970?
:>
:> http://oeis.org/A054759
:>
:> > On Oct 28, 2022, at 10:27 AM, hv at crypt.org wrote:
:> >
:> > I can confirm d=4 gives 2970.
:>
:>
:> --
:> Seqfan Mailing list - http://list.seqfan.eu/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/