[seqfan] Re: eulerian orientations of hypercube graphs

[Neil Sloane]

Peter M. said
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.

Me:  sounds like an excellent idea - please create the entry and post the
A-number here!

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Tue, Nov 1, 2022 at 11:25 AM Peter Munn <techsubs at pearceneptune.co.uk>
wrote:

> 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
> >>
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>