[seqfan] Re: eulerian orientations of hypercube graphs

[Zach DeStefano]

Thanks! I coded up a brute force version of my approach to test it and it
instantly verified d = 2 and d = 4. I estimate d = 6 would take a century,
but my program is hardly optimized.

To seriously attempt d = 6, we just need an efficient subroutine for
counting the number of ways to choose edges for a given set of constraints
on H1. That's the only bottleneck in the program right now.

Also, the hypercube of degree d has a symmetry group of size (2^d)*(d!)
which we could exploit to significantly reduce the number of cases further.
It is easy to check if a given selection of vertices is canonical with
respect to a reflection symmetry; however, I don't have a good approach
right now to check symmetries involving rotations.

With a faster subroutine for counting edges, proper symmetry checks, and
multithreading, I estimate that we can get the runtime down to under a week
with this approach.

- Zach


On Sat, Oct 29, 2022 at 5:11 PM <hv at crypt.org> wrote:

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