A generalization |

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

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

It is clear thatM_{c}:={(a_{ik})_{c}| (a_{ik})ÎM}.

Assume that we are given subgroups| M | =m!^{n}, and | M_{c}| =m!^{n-1}.

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

In addition we recall the action in form of th exponentiation of the exponentiation group. For subgroups^{T}(f(1),...,f(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^{T}([~f] (1),...,[~f] (n))=^{T}(y(1)f(p^{-1}1),...,y(n)f(p^{-1}n)).

The order of this set is obviouslyM^{<s>}:={AÎm^{n´s}| each row lies inm_{i}^{s}}.

In order to introduce a suitable group which acts on| M^{<s>}| =([m choose s]s!)^{n}=([m]_{s})^{n}, [m]_{s}:=m(m-1)...(m-s+1).

The multiplication is still defined by(´_{i=1}^{r}H_{i}) wr G:={(y,p) | yÎ(È_{i}H_{i})^{n}, pÎG,iÎw_{j}Þy(i)ÎH_{j}}.

As we have just seen, the particular case(´_{i}H_{i}) wr G´M^{<s>}-> M^{<s>}:((y,p),(a_{ik})) -> (y(i)a_{p-1i,k}).

and note that these two actions commute:S_{s}´M^{<s>}-> M^{<s>}:(s,(a_{ik})) -> (a_{i,s-1k}),

Hence we have in fact obtained an action of the direct product:(y,p)sA=s(y,p)A.

defined by(´_{i}H_{i}) wr G´S_{s}´M^{<s>}-> M^{<s>},

The character of this action is given in(((y,p),s),(a_{ik})) -> (y(i)a_{p-1i,s-1k}).

Proof: We start by considering the particular caseLemma: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)}.

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

Now we consider a fixeda_{ik}=yy_{p}...y_{pt-1}(i) a_{p-ti,s-tk}.

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

by the second equation above. In order to evaluate the number of fixed points of(yy_{p}...y_{pl-1}(j),s^{l}),

For each one of its cyclic factorsp=Õ_{n=1}^{c(p)}(j_{n}...p^{ln-1}(j_{n})).

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

Proof: It is easy to check thatde 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).

å_{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

where the sum is taken over thea_{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)},

Applying this to the equation above we get(Õ_{k}a_{k}(s)!k^{ak(s)})^{n}.

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

This result allows to express the number of orbits ofa_{1}((p_{1},...,p_{n}))= 0 otherwise.

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

This together with the character formula yieldsY^{c}ÇY^{d}Ç...ÇY^{e}=0 otherwise.

In order to provide an example we consider the dihedral group on 5 points and putRedfield'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).

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}))

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=(1)/(100)(5!+16·5+25·8)=4,

An immediate consequence is(1)/(4p^{2})(p!+(p-1)^{2}·p+p^{2}((p-1)/2)!2^{(p-1)/2}).

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@kfunigraz.ac.at,

last changed: August 28, 2001

A generalization |