[seqfan] Re: eulerian orientations of hypercube graphs

[Brendan McKay]

Incidentally, the general formula for 2*N vertices and degree 2*K is
     exp(-1/2)  (2 K)!^(2 N)  (K N)!^2 / ( K!^(4 N)  (2 K N)! ).
For Q4 (N=8, K=2) this gives 2847, a bit less than the actual
value 2970 but not far off.  This adds confidence that the actual
count for Q6 is close to 3 x 10^26.

Brendan.

On 30/10/2022 10:49 pm, 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
>>
>> 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/
>
>
> -- 
> Seqfan Mailing list - http://list.seqfan.eu/