[seqfan] Re: eulerian orientations of hypercube graphs

[hv at crypt.org]

Oh, that's very nice.

I had in mind for d=2n to classify the {n+1}-cube arrangements, and then
look for ways to fit those together. But your approach sounds much more
promising.

Hugo

Zach DeStefano <zachdestefano at gmail.com> wrote:
:Hugo,
:
:Your indistinguishability comment gave me an idea to potentially make this
:problem tractable (for d = 6).
:
:The hypercube G of dimension d can be decomposed into a pair of
:hypercubes H1 and H2, each of dimension d - 1. The absolute difference
:between the in-degree and out-degree of a vertex in one of these smaller
:hypercubes must be 1.
:
:By a parity argument you can show that exactly 1/2 of these vertices need
:to have a higher in-degree than out-degree and vice versa. There are
:nCr(2^(d - 1), 2^(d - 2)) ways to choose these vertices.
:
:For any choice of 2^(d - 2) vertices from H1 to have higher in-degree than
:out-degree, this constrains the remaining vertices in H1, the edges going
:from H1 to H2, and the in-degree - out-degree of all vertices in H2.
:
:If, instead of classifying cube faces, we have a nice way to count the
:number of ways to select edges to satisfy in-degree/out-degree constraints
:(there are only nCr(2^(d - 1),2^(d - 2)) / 2 unique classes to consider
:here), then we have a nice tractable way of counting total Eulerian
:orientations.
:
:For each choice of 2^(d - 2) vertices from H1 (I suspect we can reduce the
:number of cases to consider here using symmetry), we know exactly how many
:ways there are to choose edges to satisfy H1 and thus how many ways there
:are to satisfy H2 (the number of ways to pick edges to satisfy H1 is the
:same as the number of ways to pick edges to satisfy H2).
:
:Ignoring symmetries, the computation just needs to be:
:
:sum = 0
:for all subsets of 2^(d - 2) from H1:
:  sum += (number of ways to choose edges so our degree constraints are
:met)^2
:
:For d = 6, there are 300,540,195 subsets of vertices to consider (so we are
:potentially already in tractible territory given an efficient method to
:determine the number of ways to choose edges for each subset), though I
:believe we can use additional symmetries to reduce this by a large factor.
:
:- Zach
:
:On Sat, Oct 29, 2022 at 7:24 AM <hv at crypt.org> wrote:
:
:> 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/
:>
:> --
:> Seqfan Mailing list - http://list.seqfan.eu/
:>
:
:--
:Seqfan Mailing list - http://list.seqfan.eu/