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

(a_{ik})~_{c}(a_{ik}') :Û $ sÎå " i,k: a'_{ik}=a_{i,s-1k}.

The equivalence class of *(a _{ik})* will be denoted by

M_{c}:={(a_{ik})_{c}| (a_{ik})ÎM}.

It is clear that

| M | =m!^{n}, and | M_{c}| =m!^{n-1}.

Assume that we are given subgroups *H _{1},...,H_{n} <= å*. Their direct
product acts on

(´_{i}H_{i})´M_{c}-> M_{c}:((p_{1},...,p_{n}), (a_{ik})_{c}) -> (p_{i}a_{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 _{1},...,H_{n}* is equal to

| (´_{i}H_{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^{n}*
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

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

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

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

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

(´_{i=1}^{r}H_{i}) wr G:={(y,p) | yÎ(È_{i}H_{i})^{n}, 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

(´_{i}H_{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^{n}*.
In order to cover also Redfield's column equivalence relation we
furthermore introduce the corresponding action of

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_{1}((y,p),s)=Õ_{n=1}^{c(p)}Õ_{k=1}^{s}[a_{k}(h_{n}( y,p)) choose a_{k}(s^{ln})] a_{k}(s^{ln})!k^{ak(sln)}.

Proof: We start by considering the particular case *n=1*, in
which the set *M ^{<s>}* is just the set of injective

a_{ik}=y(i)a_{p-1i,s-1k}.

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

a_{ik}=yy_{p}...y_{pt-1}(i) a_{p-ti,s-tk}.

Now we consider a fixed *jÎ n*, and

The first equation above" kÎs: a_{jk}=yy_{p}...y_{pl-1}(j)a_{j,s-lk}.

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_{pl-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^{ln-1}(j_{n})).

For each one of its cyclic factors *(j _{n}...p^{ln-1}(j_{n}))* we
can freely choose an injective

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

de Bruijn's LemmaAssume thatXis both aG- and anH-set, and that we haveThen" gÎG, hÎH $h'ÎH " x: g(hx)=h'(gx).Gacts onH\\Xas follows:and the character of this action isG´(H\\X) -> H\\X:(g,H(x)) -> H(gx),a_{1}(g):= | (H\\X)_{g}| =(1)/(| H |)å_{hÎH}| X_{gh}| =:(1)/(| H |)å_{hÎH}a_{1}(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ÎXgh}1

=å_{x:gH(x) =H(x)}å_{h:hx=g-1x}1 =å_{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_{1}((p_{1},...,p_{n}))=(1)/(m!)å_{s}Õ_{n=1}^{n}Õ_{k=1}^{m}[a_{k}(p_{n}) choose a_{k}(s)]a_{k}(s)!k^{ak(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

(Õ_{k}a_{k}(s)!k^{ak(s)})^{n}.

Applying this to the equation above we get

a_{1}((p_{1},...,p_{n}))=(Õ_{k}a_{k}!k^{ak})^{n-1}if each a(p_{n})=(a_{1},...,a_{n})

a_{1}((p_{1},...,p_{n}))= 0 otherwise.

This result allows to express the number of orbits of *´H _{i}* on

Y^{c}ÇY^{d}Ç...ÇY^{e}=(Õ_{k}a_{k}!k^{ak})^{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 TheoremThe 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}^{n}H_{i})\\M_{c}| = Ç_{i}C(H_{i},m).

In order to provide an example we consider the dihedral group on 5 points
and put *H _{1}:=H_{2}:=D_{5}*. This group

C(D_{5},5)ÇC(D_{5},5)=(1)/(10)(y_{1}^{5}+4y_{5}+5y_{1}y_{2}^{2})Ç(1)/(10)(y_{1}^{5}+4y_{5}+5y_{1}y_{2}^{2})

=(1)/(100)(y_{1}^{5}Çy_{1}^{5}+16(y_{5}Çy_{5})+25(y_{1}y_{2}^{2}Çy_{1}y_{2}^{2}))

=(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^{2})(p!+(p-1)^{2}·p+p^{2}((p-1)/2)!2^{(p-1)/2}).

An immediate consequence is

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

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

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

A generalization |