[seqfan] Re: eulerian orientations of hypercube graphs

[Zach DeStefano]

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/
>