The Decomposition TheoremWeightsSums of cycle indicators, recursive methodsA 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=(aik) 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:

(aik)~c(aik') :Û $ sÎå " i,k: a'ik=ai,s-1k.
The equivalence class of (aik) will be denoted by (aik)c, and we put
Mc:={(aik)c | (aik)ÎM}.
It is clear that
  | M | =m!n, and | Mc | =m!n-1.
Assume that we are given subgroups H1,...,Hn <= å. Their direct product acts on Mc as follows:
  (´i Hi)´Mc -> Mc:((p1,...,pn), (aik)c) -> (piaik)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 H1,...,Hn is equal to
  | (´iHi)\\Mc | .
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Îmn 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 <= Sn , 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Îmn´s | each row lies in mis}.
The order of this set is obviously
| M<s> | =([m choose s]s!)n=([m]s)n, [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 <= Sn has the orbits w1,...,wrÍn. We put, for Hi <= Sm,iÎr,
(´i=1rHi) wr G:={(y,p) | yÎ(ÈiHi)n, pÎG,iÎwjÞy(i)ÎHj}.
The multiplication is still defined by (y,p)(j,r):=(yjp, pr), and this group acts on M<s> in the following way:
(´iHi) wr G´M<s> -> M<s>:((y,p),(aik)) -> (y(i)ap-1i,k).
As we have just seen, the particular case s:=1 yields the exponentiation group action on mn. In order to cover also Redfield's column equivalence relation we furthermore introduce the corresponding action of Ss:
  Ss´M<s> -> M<s>:(s,(aik)) -> (ai,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 Hi) wr G´Ss ´M<s> -> M<s>,
defined by
(((y,p),s),(aik)) -> (y(i)ap-1i,s-1k).
The character of this action is given in
Lemma:  
a1((y,p),s)=Õn=1c(p)Õk=1s [ak(hn( y,p)) choose ak(sln)] ak(sln)!kak(sln).
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 ((´iHi) wr G)´Ss is isomorphic to the direct product H1´Ss. 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
aik=y(i)ap-1i,s-1k.
Hence, for each tÎN*, the following is true:
  aik=yyp...ypt-1(i) ap-ti,s-tk.
Now we consider a fixed jÎn, and l, the length of its cyclic factor in p, which satisfy:
  " kÎs: ajk=yyp...ypl-1 (j)aj,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 mis, must be a fixed point of
(yyp...ypl-1(j),sl),
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=1c(p)(jn...pln-1(jn)).
For each one of its cyclic factors (jn...pln-1(jn)) we can freely choose an injective s-tuple over m among the fixed points of (hn(y,p),sln). If we now form the product over all the cycles of p, taking the number of fixed points of (hn(y,p), sln) 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
a1(g):= | (H\\X)g | =(1)/( | H | )åhÎH | Xgh | =:(1)/( | H | )åhÎHa1(gh).
Proof: It is easy to check that (g,H(x)) -> H(gx) is an action. Furthermore we have that
åh | Xgh | =åhÎHåxÎXgh1
=åx:gH(x) =H(x)åh:hx=g-1x1 =åx:gH(x)=H(x) | Hx |
= | H | åx:gH(x )= H(x) | H(x) | -1= | H | åwÎH\\X:gw= w1= | 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

  a1((p1,...,pn))=(1)/(m!)åsÕn=1n Õk=1m[ak(pn) choose ak(s)]ak(s)!kak(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 pn are of the same cycle type as s, in which case the double product takes the value
(Õkak(s)!kak(s))n.
Applying this to the equation above we get
a1((p1,...,pn))=(Õkak!kak)n-1 if each a(pn)=(a1,...,an)
a1((p1,...,pn))= 0 otherwise.
This result allows to express the number of orbits of ´Hi on Mc in terms of the cycle indicator polynomials of the Hi. We introduce Redfield's so-called cap operation  Ç on the set Q[Y] of polynomials over Q in the set Y:={y1,...,ym} of indeterminates. It is defined to be the linear extension of the following operation on monomials. Using the abbreviation Yb:=y1b1...ymbm, for b:=(b1,...,bm), where biÎN, we put:
YcÇYdÇ...ÇYe=(Õkak!kak)n-1 if ci=di=...=ei=ai, where we take the Ç-product of n terms
YcÇYdÇ...ÇYe=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=1n Hi)\\Mc | = ÇiC(Hi,m).
In order to provide an example we consider the dihedral group on 5 points and put H1:=H2:=D5. This group D5 is the automorphism group of the graphs of Figure. The cycle indicator polynomial of this group is (use these formulae) C(D5,5)=(1)/(10)(y15+4y5+ 5y1y22). Hence, according to Redfield's theorem, we obtain for the number of superpositions of two such graphs:
C(D5,5)ÇC(D5, 5)=(1)/(10)(y15+4y5+5y1y22)Ç(1)/(10) (y15+4y5+5y1y22)
=(1)/(100)(y15Çy15+16(y5Çy5)+25(y1y22Çy1y22))
=(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 Dp is equal to
(1)/(4p2)(p!+(p-1)2·p+p2((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

The Decomposition TheoremWeightsSums of cycle indicators, recursive methodsA generalization