[seqfan] Re: eulerian orientations of hypercube graphs

Wed Nov 30 13:05:11 CET 2022

I was about to say exactly what Hugo said.  Please follow his suggestion!

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com

On Wed, Nov 30, 2022 at 4:57 AM Hugo Pfoertner <yae9911 at gmail.com> wrote:

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