[seqfan] Re: eulerian orientations of hypercube graphs

[Brendan McKay]

That's a good find, Zach.  It shows that a pure search is infeasible even
if it can be reduced by the full automorphism group size of 46080.

I'm guessing that the actual count might be about 10 times higher
than Schrijver's lower bound.

The hypercube is bipartite. Colour it black and white.  Now, given
an orientation, colour the edges of the (undirected) hypercube
green if they go black->white in the orientation and red if they
go white->black.

The green edges form a spanning cubic subgraph of the cube. This
process is clearly reversible. So:
   Unoriginal Theorem:
          The number of eulerian orientations of a 6-regular bipartite
           graph equals the number of spanning cubic subgraphs.

If we consider random 6-regular bipartite graphs with 2*N vertices,
the average number of spanning cubic subgraphs is asymptotically
    exp(-1/2) * (3*N)!^2 * 400^N / (6*N)! .
This follows from my paper at https://arxiv.org/abs/2206.12793 .
For N=32, this value is 3 x 10^26.  Of course the hypercube is far
from a random 6-regular graph, but I can't think of why it should
have many more or many less orientations than the average.

Brendan.

On 29/10/2022 4:05 am, Zach DeStefano 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/