[seqfan] eulerian orientations of hypercube graphs

Christian Sievers seqfan at duvers.de
Wed Nov 30 03:06:28 CET 2022


In the last month, here was some discussion about the number of
eulerian orientations of hypercube graphs.
(This mail is not a proper response with an In-Reply-To:-header
because I wasn't subscribed then.)
I computed the dimension 6 case and went to the OEIS, hoping for
a coincidence. Instead, I found

  A358177 Number of Eulerian orientations of a (labeled)
          2n-dimensional hypercube graph, [...].

So the result had already been found in the meantime, making this
mail much less exciting than I hoped.
But I can confirm the result and tell you how I got it.
A lot of that was already mentioned here, but I'm adding a generating
function and some group theory.

Let HC(d) be the d-dimensional hyper cube.
Use bitstrings of length d for the nodes in the usual way
and identify nodes of HC(d) with nodes of HC(d') (d'>d)
iff the bitstrings only differ by leading zeros,
thus embedding HC(d) in HC(d').
Define a variable x_n for each node n.

Each choice of an orientation of an edge {s,t} can be seen as a choice
between one of the two nodes of the edge. This suggests a generating
function to see how many ways there are to choose each node a given
number of times. So let

p(d) = product over all edges {s,t} of HC(d)  (x_s + x_t),

and we want the coefficient of the term whose monomial is
product over all nodes n of HC(d)  (x_n^{d/2}).

We could also count both the in- and the out-degrees using a second set
of variables y_n and taking the product of (x_s*y_t + x_t*y_s).
That gives essentially the same polynomial, just that in each
monomial, each variable x_n that appears with exponent e_n is
"complemented" by an appearance of y_n^{d-e_n}.

The invariance of the polynomial under exchanging all x with all y
variables shows that in p(d) the monomials \prod_n x_n^{e_n} and
\prod_n x_n^{d-e_n} have the same coefficient. (*)

Also, when considering the dimension 6 case, when computing p(6) we
can drop all terms that involve a variable with an exponent >=4.
This corresponds to computing modulo the ideal generated by the 4th
powers of all the variables. When we compute p(4) as a subterm of
p(6), we can also drop all terms where a variable x_n has exponent 0.
That's clear, but nicer to justify by noticing that it corresponds to
modding out y_n^4 in the extended polynomial.

It's also tempting to set y_n=1/x_n, but I cannot see this leading
anywhere, and from now on we'll only use p(d).

Computing p(3) is no problem for sympy.

Computing the terms of p(4) where each variable has exponent between 1
and 3 can be done in less than a second. (I used Rust and packed each
exponent in two bits).
There are 5033003 such terms, corresponding to nearly all the ways of
getting 32 as the sum of 16 numbers in {1,2,3}.

Next, observe that p(d) can be decomposed as
p(d) = p(d-1) * p'(d-1) * c(d-1),
where p' is as p but with the variables from the embedding of
  HC(d-1) in HC(d) replaced with the corresponding ones from the
  other parallel subhypercube, i.e. the nodes get a 1 prepended
  to the bitstream instead of a 0 from the embedding,
and c is the product of the sums x_n+x_n' corresponding to the edges
  along the new dimension. Its expansion has 2^{d-1} terms, each with
  coefficient 1 and monomial describing a choice of selecting (for
  each node in HC(d-1)) the corresponding node in either the embedding
  or the parallel subhypercube.

To get the all-exponent 3 term of p(6), we need the p(5) terms where
each variable has exponent 2 or 3. HC(5) has 80 edges, so both
exponent 2 and 3 have to appear 16 times. So we only get a
contribution to the term we want when the term from c(d-1) selects 16
nodes from each of the subhypercubes.

So the number of eulerian orientations of HC(6) is
sum over selections of 16 nodes from HC(5) of
    (the coefficient of p(5) of the term
         with exponent 2 (else 3) for x_n iff n is selected)
  * (the coefficient of p'(5) of the term
         with exponent 2 (else 3) for x_n' iff n' is selected).

But n' is selected if the corresponding n is not selected,
so the second factor is just the coefficient of p(5) of the term
where the 2 and 3 exponents are opposite to the term used in the first
factor. By (*), the coefficients are equal.

The polynomial p(d) is invariant under permuting the variables
according to the automorphisms of HC(d).

So we can find the number as
sum over the orbits of selections of 16 nodes from HC(5)
         under the setwise action of Aut(HC(5)) of
    (size of the orbit) *
    (coefficient of p(5) of a term with
     exponents according to a representative of the orbit)^2.

The usual way to compute the orbits still let's us see all the
binomial(32,16) selections, but we need less coefficients of p(5).
A small GAP calculation using Burnside's lemma predicts 169112 orbits.
We don't need to know this number in advance, but it is good for a
cross check of the computation, and gives an idea if it is worth the
trouble.

To determine the coefficients of p(5), we use the decomposition again:
p(5)=p(4)*p'(4)*c(4).
To get terms of p(5) with exponents 2 and 3, we need the terms of p(4)
with exponents between 1 and 3. Since these were calculated before, we
can just look them up. This time, we need all the terms from c, but
that's okay as there are only 2^16.

So to get the coefficent of \prod_n x_n^{e_n} in p(5)
where each e_n is 2 or 3:
let e0 be the vector with the first half of the exponents e_n
let e1 be the vector with the second half of the exponents e_n
return the sum over all 0-1-vectors c of length 16 of
  (the coefficient of p(4) of the term with exponents (e0-c)) *
  (the coefficient of p(4) of the term with exponents (e1-[1,1...1]+c))

All this allows to compute the result 351135773356461511142023680
in a few minutes.

The selections of 64 nodes of HC(7) have
37126652766640082937217814348006 orbits under the action of
Aut(HC(7)), so we need some other ideas for dimension 8.
Oh, I just see that's A000721.
(The lower bound binomial(128,64)/(7!*2^7) is a very good aproximation
to that number.)


All the best,
Christian



More information about the SeqFan mailing list