[seqfan] Re: eulerian orientations of hypercube graphs

[hv at crypt.org]

Ah, I see at least how to take advantage of the indistinguishability.

For d=4, for example, pick an initial square face ABCD. Let "AB"
represent the edge going out from A, and in to B.

We pick A as out first vertex, and assign AB, AC as its two out-edges,
with EA, IA as its two in-edges. AB, AC now represent a pair of
indistinguishable dimensions, as do AE, AI, and we will multiply
the results by 4C2 = 6.

For the first pair, we can now try setting a) BD and CD, b) BD and DC,
and c) DB and DC: we now count a + 2b + c, since (BD + DC) is
symmetric with (DB + CD). For each combination, we similarly set
3 selections of EM, IM for the second pair. In this case we end up
testing 9 sets out of 16; the same strategy for d=6 tests 16 sets
out of 64 (so not the 36x improvement I had hoped for).

That suggests to me that the insight from d=4 might come by classifying
the structures of the cube faces.

Hugo

I wrote:
: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/