[seqfan] Re: eulerian orientations of hypercube graphs

[Hugo Pfoertner]

Could you please put the post into a file with a bit of formatting and then
upload it to e.g. A358177? Because of the unreliability of the archive
function here in SeqFan, there's a good chance this will be lost otherwise.

On Wed, Nov 30, 2022 at 3:21 AM Christian Sievers <seqfan at duvers.de> wrote:

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