[seqfan] Re: eulerian orientations of hypercube graphs

[Peter Munn]

Are we creating a new sequence that we can keep an eye on for future
developments? Given this problem has a published history going back
decades, I presume no issue with a keyword:bref sequence starting 1, 2,
2970 pending calculation of the next term.

Peter

On Sun, October 30, 2022 11:49 am, Brendan McKay via SeqFan wrote:
> 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
>>