Algebraic Combinatorics -- A generalization

A generalization

A generalization

Ten years before Pólya published his pioneering work, a paper by J. H. Redfield appeared concerning superpositions of graphs. But it was overlooked for many years (a second paper which went even further was rejected and printed only recently after it had been discovered among his mathematical papers). It is difficult to read, but it already contains the main results on enumeration by weight, moreover it presents a more general approach which we are going to describe next. It will not be necessary to give a formal definition of superposition , since the reader will clearly see what is meant from an example, and we shall examine a more general situation later on anyway. Two graphs on 5 vertices together with one (out of 4) superpositions of these graphs are shown in figure. The edges of one of the two superimposed graphs are dotted.

Two graphs on 5 vertices and a superposition

Now we introduce an enumeration problem, a special case of which is the enumeration of superpositions of graphs. Consider, for given m,nÎN^*, the set M of all the n´m-matrices A=(a_ik) which contain in each row all the elements of m, i.e. each row of AÎM is an injective m-tuple over m. Now we establish on M an equivalence relation ~_c by saying that A,A'ÎM are column equivalent if A' arises from A by applying a suitable column permutation s:

(a_ik)~_c(a_ik') :Û $ sÎå " i,k: a'_ik=a_i,s^-1k.

The equivalence class of (a_ik) will be denoted by (a_ik)_c, and we put

M_c:={(a_ik)_c | (a_ik)ÎM}.

It is clear that

| M | =m!ⁿ, and | M_c | =m!^n-1.

Assume that we are given subgroups H₁,...,H_n <= å. Their direct product acts on M_c as follows:

(´_i H_i)´M_c -> M_c:((p₁,...,p_n), (a_ik)_c) -> (p_ia_ik)_c,

and we ask for the number of orbits. One of the most important results of Redfield's paper is the proof of the fact that the number of superpositions of n graphs with m vertices and automorphism groups H₁,...,H_n is equal to

| (´_iH_i)\\M_c | .

Since we are not particularly interested in this number of graphs, we go further and formulate and solve a counting problem which generalizes both Redfield's superposition problem and the enumeration of symmetry classes of mappings. To begin with we note that fÎmⁿ can be identified with the one column matrix

^T(f(1),...,f(n)).

In addition we recall the action in form of th exponentiation of the exponentiation group. For subgroups H <= å, G <= S_n , the image [~f] :=(y,p)f, for (y,p) in H wr G, satisfies

^T([~f] (1),...,[~f] (n))= ^T(y(1)f(p^-11),...,y(n)f(p^-1n)).

We compare this with Redfield's approach and seek for a generalization which covers this and the former approach. We are led to the following Ansatz. Consider, instead of n´m-matrices, the n´s-matrices A, for a fixed sÎm, where each row of A is an injective s-tuple over m:

M^<s>:={AÎm^n´s | each row lies in m_i^s}.

The order of this set is obviously

| M^<s> | =([m choose s]s!)ⁿ=([m]_s)ⁿ, [m]_s:=m(m-1)...(m-s+1).

In order to introduce a suitable group which acts on M^<s>, we define the following generalized wreath product . Assume that G <= S_n has the orbits w₁,...,w_rÍn. We put, for H_i <= S_m,iÎr,

(´_i=1^rH_i) wr G:={(y,p) | yÎ(È_iH_i)ⁿ, pÎG,iÎw_jÞy(i)ÎH_j}.

The multiplication is still defined by (y,p)(j,r):=(yj_p, pr), and this group acts on M^<s> in the following way:

(´_iH_i) wr G´M^<s> -> M^<s>:((y,p),(a_ik)) -> (y(i)a_p^-1i,k).

As we have just seen, the particular case s:=1 yields the exponentiation group action on mⁿ. In order to cover also Redfield's column equivalence relation we furthermore introduce the corresponding action of S_s:

S_s´M^<s> -> M^<s>:(s,(a_ik)) -> (a_i,s^-1k),

and note that these two actions commute:

(y,p)sA=s(y,p)A.

Hence we have in fact obtained an action of the direct product:

(´_i H_i) wr G´S_s ´M^<s> -> M^<s>,

defined by

(((y,p),s),(a_ik)) -> (y(i)a_p^-1i,s^-1k).

The character of this action is given in

Lemma:
a₁((y,p),s)=Õ_n=1^c(p)Õ_k=1^s [a_k(h_n( y,p)) choose a_k(s^l_n)] a_k(s^l_n)!k^{a_k(s^l_n)}.

Proof: We start by considering the particular case n=1, in which the set M^<s> is just the set of injective s-tuples over m, while the wreath product ((´_iH_i) wr G)´S_s is isomorphic to the direct product H₁´S_s. Hence, for this case, we obtain the assertion from the Corollary on the number of fixed points. For the general case n >= 1 we remark that A is a fixed point of ((y,p),s) if and only if its elements satisfy the equations

a_ik=y(i)a_p^-1i,s^-1k.

Hence, for each tÎN^*, the following is true:

a_ik=yy_p...y_p^t-1(i) a_p^-ti,s^-tk.

Now we consider a fixed jÎn, and l, the length of its cyclic factor in p, which satisfy:

" kÎs: a_jk=yy_p...y_p^l-1 (j)a_j,s^-lk.

The first equation above means that the rows, the numbers i of which belong to the cycle containing j, are completely determined by the entries of the j-th row. Furthermore the j-th row of A, considered as an element of m_i^s, must be a fixed point of

(yy_p...y_p^l-1(j),s^l),

by the second equation above. In order to evaluate the number of fixed points of ((y,p),s), we consider the standard cycle notation for p, say

p=Õ_n=1^c(p)(j_n...p^l_n-1(j_n)).

For each one of its cyclic factors (j_n...p^l_n-1(j_n)) we can freely choose an injective s-tuple over m among the fixed points of (h_n(y,p),s^l_n). If we now form the product over all the cycles of p, taking the number of fixed points of (h_n(y,p), s^l_n) as the factor corresponding to the n-th cyclic factor, then we obtain the desired number, and this proves the statement, as can be seen from the foregoing argument in the case n=1.

In order to derive Redfield's results from this more general one, we need another tool:

de Bruijn's Lemma Assume that X is both a G- and an H-set, and that we have
" gÎG, hÎH $h'ÎH " x: g(hx)=h'(gx).
Then G acts on H\\X as follows:
G´(H\\X) -> H\\X:(g,H(x)) -> H(gx),
and the character of this action is
a₁(g):= | (H\\X)_g | =(1)/( | H | )å_hÎH | X_gh | =:(1)/( | H | )å_hÎHa₁(gh).

Proof: It is easy to check that (g,H(x)) -> H(gx) is an action. Furthermore we have that

å_h | X_gh | =å_hÎHå_{xÎX_gh}1

=å_{x:gH(x)
=H(x)}å_h:hx=g^-1x1 =å_x:gH(x)=H(x) | H_x |

= | H | å_{x:gH(x
)=
H(x)} | H(x) | ^-1= | H | å_{wÎH\\X:gw=
w}1= | H | | (H\\X)_g | .

In order to derive from this the character of the action we use the lemma and de Bruijn's Lemma which give

a₁((p₁,...,p_n))=(1)/(m!)å_sÕ_n=1ⁿ Õ_k=1^m[a_k(p_n) choose a_k(s)]a_k(s)!k^a_k(s),

where the sum is taken over the sÎå. Now we observe that the summand on the right hand side is nonzero only if all the p_n are of the same cycle type as s, in which case the double product takes the value

(Õ_ka_k(s)!k^a_k(s))ⁿ.

Applying this to the equation above we get

a₁((p₁,...,p_n))=(Õ_ka_k!k^a_k)^n-1 if each a(p_n)=(a₁,...,a_n)

a₁((p₁,...,p_n))= 0 otherwise.

This result allows to express the number of orbits of ´H_i on M_c in terms of the cycle indicator polynomials of the H_i. We introduce Redfield's so-called cap operation Ç on the set Q[Y] of polynomials over Q in the set Y:={y₁,...,y_m} of indeterminates. It is defined to be the linear extension of the following operation on monomials. Using the abbreviation Y^b:=y₁^b₁...y_m^b_m, for b:=(b₁,...,b_m), where b_iÎN, we put:

Y^cÇY^dÇ...ÇY^e=(Õ_ka_k!k^a_k)^n-1 if c_i=d_i=...=e_i=a_i, where we take the Ç-product of n terms

Y^cÇY^dÇ...ÇY^e=0 otherwise.

This together with the character formula yields

Redfield's Counting Theorem The number of orbits of the direct product on the set of equivalence classes of matrices is equal to the cap product of the corresponding cycle indicator polynomials:
| (´_i=1ⁿ H_i)\\M_c | = Ç_iC(H_i,m).

In order to provide an example we consider the dihedral group on 5 points and put H₁:=H₂:=D₅. This group D₅ is the automorphism group of the graphs of Figure. The cycle indicator polynomial of this group is (use these formulae) C(D₅,5)=(1)/(10)(y₁⁵+4y₅+ 5y₁y₂²). Hence, according to Redfield's theorem, we obtain for the number of superpositions of two such graphs:

C(D₅,5)ÇC(D₅, 5)=(1)/(10)(y₁⁵+4y₅+5y₁y₂²)Ç(1)/(10) (y₁⁵+4y₅+5y₁y₂²)

=(1)/(100)(y₁⁵Çy₁⁵+16(y₅Çy₅)+25(y₁y₂²Çy₁y₂²))

=(1)/(100)(5!+16·5+25·8)=4,

which means that there are exactly 4 superpositions of two such graphs (see exercise). We can easily generalize this example since we know the cycle structure of the elements in dihedral groups (see). For example, if p denotes an odd prime, then the cap product of the cycle indicator polynomials of D_p is equal to

(1)/(4p²)(p!+(p-1)²·p+p²((p-1)/2)!2^(p-1)/2).

An immediate consequence is

Corollary: Each prime p>3 satifies the congruence
(p-1)!+p(p-2)+1º (4p).

Exercises

E: Draw the four different superpositions of the two pentagonal graphs shown in Figure.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

A generalization