The Decomposition Theorem |

Proof: The set of bijectionsLemma:The number of orbits ofHon^{G}, wheren_{i}^{n}H,G <= S, is equal to the cap-product_{n}C(H,n)ÇC(G,n).

Noticing that bijections are permutations, we can reformulate this lemma as follows:

An expression for the number of graphs can also be obtained from Redfield's Counting Theorem as follows. A labelled graph withCorollary:The cap productC(H,is equal to the number of classes of elementsn)ÇC(G,n)sÎSwith respect to the following equivalence relation:_{n}In other words, this cap product is equal to the number ofs_{1}~s_{2}iff $pÎH,rÎG: s_{1}=ps_{2}r^{-1}.(H,G)-double cosets inS. More explicitly, in terms of intersections of conjugacy classes_{n}Cof the symmetric group^{a}Swith_{n}HandG, this cap product is equal to(1)/(| H | | G |)å_{a|¾| n}| C^{a}ÇH | | C^{a}ÇG | Õ_{k}a_{k}!k^{ak}=(n!)/(| H | | G |)å_{a|¾| n}(| C^{a}ÇH | | C^{a}ÇG |)/(| C^{a}|).

More generally we obtain for the number ofCorollary:The number of graphs withvvertices andeedges is equal to the cap productC(S_{v},[v choose 2])ÇC(S_{e}ÅS_{[v choose 2]\e}).

We shall return to this later. Tools from linear representation theory will allow a further elucidation of Redfield's methods and results. Furthermore we can derive an algorithm for a redundancy free construction of representatives of theCorollary:The number ofG-classes of content(bon_{1}, ...,b_{m})is equal to the cap productm^{n}C(G,n)ÇC(S_{b1}Å...ÅS_{ bm},n).

Besides this useful cap operation Redfield introduced a *cup operation*
*È*, defined to be the linear extension of the following operation on
monomials:

It clearly has the following property:Y^{c}È...ÈY^{d}:=(Y^{c}Ç...ÇY^{d})Y^{d}.

This shows that it should be useful to examine cup products of cycle indicator polynomials. In fact it is possible to write each such cup product as a sum of cycle indicators of stabilizers. We shall prove this result of Redfield with the aid of the following lemma:Lemma:The cap productC(H,is equal to the sum of the coefficients in the cup productn)ÇC(G,n)C(H,.n)ÈC(G,n)

Proof:Redfield's LemmaLetbe a finite action,_{G}Xwits orbits,_{1},...,w_{r}xand_{i}Îw_{i}c:G ->a class function. Then we have for the stabilizersQ[Y]Gof these representatives that_{i}:=G_{xi}(1)/(| G |)å_{gÎG}c(g) | X_{g}| =å_{i=1}^{r}(1)/(| G_{i}|)å_{gÎGi}c(g).

| G | å_{i}(1)/(| G_{i}|)å_{gÎGi}c(g)= å_{i}| w_{i}| å_{gÎGi}c(g)

=å_{xÎX}å_{gÎGx}c(g)=å_{g}c(g) | X_{g}| .

We are now in a position to prove the main theorem of Redfield's first paper:

Proof: Recall the action in question:Redfield's Decomposition TheoremAssume that we are given subgroupsHof_{1},...,H_{m}Sand an action of_{n}´on_{i}H_{i}M. Let_{c}wdenote the orbits, choose representatives_{1},...,w_{r}A, and denote by_{i}Îw_{i}Gtheir stabilizers. Then each_{i}Gis conjugate in_{i}´to a subgroup of the diagonal^{m}S_{n}D(´, and the cup product of the cycle indicator polynomials of the^{m}S_{n})Hcan be decomposed with the aid of the_{i}Gas follows:_{i}C(H_{1},n)È...ÈC(H_{m},n)=å_{i=1}^{r}(1)/(| G_{i}|)å_{(p1,...,pm)ÎGi}Õ_{k=1}^{n}y_{k}^{ak(p1)}.

Then(´_{i}H_{i})´M_{c}-> M_{c}:((p_{1},...,p_{m}),(a_{ik})_{c}) -> (p_{i}a_{ik})_{c}.

Thus the equivalence classA~_{c}B iff $sÎS_{n}: (r_{1}',...,r_{m}')= (r_{1}s,...,r_{m}s).

Analogously we can rewrite Redfield's action of{(r_{1}s,...,r_{m}s) | sÎS_{n}}=(r_{1},..., r_{m})D(´^{m}S_{n}).

The stabilizer of((p_{1},...,p_{m}),(r_{1},..., r_{m})_{c}) -> (p_{1}r_{1},...,p_{m}r_{m})_{c}.

and hence is conjugate to a subgroup of the diagonal, as is claimed.H_{1}´...´H_{m}Ç(r_{1},...,r_{m})D(´^{m}S_{n}) (r_{1}, ...,r_{m})^{-1},

In order to prove the second part of the assertion, we first of all note that by the definition of the cup operation we have that

whereÈ_{i=1}^{m}C(H_{i},n)=(1)/(Õ_{i}| H_{i}|)å(Õ_{k}a_{k}!k^{ak})^{m-1}Õ_{k}y_{k}^{ak},

(Õ_{k}a_{k}!k^{ak})^{m-1}=a_{1}((p_{1},..., p_{m}))

where the sum is taken over all the *(p,...,p _{m})Î´_{i}H_{i}* such
that

c((p_{1},...,p_{m})):=Õ_{k}y_{k}^{ak}for each i Îm: a(p_{i})=(a_{1},...,a_{n}),

Then the cup operation together with Redfield's Lemma yields the statement.c((p_{1},...,p_{m})):=0 otherwise.

Putting *m:=1*, we obtain the following decomposition of the cycle indicator
polynomial according to the stabilizers of the orbits:

Corollary:ConsiderH£Swith orbits_{n}won_{1},..., w_{r}Y, representatives^{X}fand stabilizers_{i}Îw_{i}Gof these representatives. Then the cycle indicator polynomial_{i}C(H,is equal to the following sum:n)C(H,n)=å_{i=1}^{r}(1)/(| G_{i}|)å_{pÎGi}Õ_{k=1}^{n}y_{k}^{ak(p)}.

Examples:Let us also consider a few examples of the particular casem:=2. Redfield's Decomposition Theorem yieldsThe mappingC(H_{1},n)ÈC(H_{2},n)=å_{i=1}(1)/(| G_{i}|)å_{(p1,p2)ÎGi}Õ_{k}y_{k}^{ak(p1)}.is clearly a bijection, and it has the propertyj:M_{c}-> S_{n}:(r_{1},r_{2})_{c}-> r_{1}r_{2}^{-1}which means that the orbit ofj((p_{1},p_{2})(r_{1},r_{2})_{c})=p_{1}r_{1}r_{2}^{-1}p_{2}^{-1},(ris mapped onto the_{1},r_{2})_{c}(H-double coset_{1},H_{2})H. The stabilizer of_{1}r_{1}r_{2}^{-1}H_{2}(r,1), is conjugate to the intersection_{c},rÎS_{n}(r, and we have obtained:^{-1}H_{1}r´H_{2})ÇD(S_{n}´S_{n})Special cases areCorollary:If{pis a transversal of the_{1},...,p_{r}}(H-double cosets of_{1},H_{2})S, then, by Redfield's Decomposition Theorem, we have_{n}C(H_{1},n)ÈC(H_{2},n)=å_{i=1}^{r}C(p_{i}^{-1}H_{1}p_{i}ÇH_{2},n).and (exercise)C(A_{n},n)ÈC(A_{n},n)= | A_{n}\S_{n}/A_{n}| ·C(A_{n},n),C(S_{n-1},n)ÈC(S_{n-1},n)= C(S_{n-1},n)+C(S_{n-2},n).

Redfield's Decomposition Theorem shows that a good knowledge of the conjugacy
classes of subgroups of *D(´ ^{m}S_{n} )* is important. We can obtain
the desired information from a transversal of the left cosets of the
normalizer of

Proof: It is easy to check thatTheorem:LetGbe a finite group andlÎ. The lattice of subgroups ofN^{*}´, the normalizer of which contains^{l}GD(´, is isomorphic to the lattice of subgroups in between^{l}G)D(´and^{l+1}G)´. A lattice isomorphism is provided by the mapping^{l+1}GU -> (U | G):={(u_{1}g,...,u_{l}g,g) | (u_{1},...,u_{l}) ÎU,gÎG}.

This action is clearly transitive, and the stabilizer of the identity element((g_{1},...,g_{l+1}), (g_{1}',...,g_{l}')) -> (...,g_{i}g_{i}'g_{l+1}^{-1},...).

and the orbitD(´^{l+1}G) <= H <= ´^{l+1}G,

Using this remark it is easy to check that(h_{1},...,h_{l},1)ÎH iff (h_{1},...,h_{l})Îw.

This theorem has the following consequence:

Recall now the definition ofCorollary:The lattice of subgroups in betweenD(G´G)andG´G, whereGis a finite group, is isomorphic to the lattice of normal subgroups ofG.

One easily checks thatZ(G):={hÎG | hg=gh, for each gÎG}.

Z(´^{m}G)=´^{m}Z(G).

Proof: It is obvious, thatTheorem:The normalizer ofD(´in^{l+1}G)´is the subgroup^{l+1}G(Z(´^{l}G) | G)={(g_{1}g,...,g_{l}g,g) | g_{i}ÎZ(G),gÎG}.

shows thath^{*}:=(h_{1},...,h_{l},1)(g,...,g)(h_{1},...,h_{l},1)^{-1}

As the normalizer *N _{G}(U)* of

Consider, for example, the symmetric group[~U] ={g_{1}Ug_{1}^{-1},...,g_{r}Ug_{r}^{-1}}.

{(p_{1},...,p_{l},1) | (p_{1},...,p_{l})Î´^{l}S_{n}}.

E:Prove the formula for cup products of symmetric groups.

E:Prove that the cup product ofmfactors ofC(Sis given by:_{n-1}whereC(S_{n-1},n)È...ÈC(S_{n-1},n)=å_{k=1}^{m}S(m,k) C(S_{n-k},n),S(m,k)denotes a Stirling number of the second kind.Hint: Prove first the following result of Foulkes: For each subgroup

H <= S_{n}holds. Use the fact thatC(H,n)È...ÈC(H,n)=(1)/(n!)å_{a|¾| n}((n! | C^{a}ÇH |)/(| H | | C^{a}|))^{m}Õ_{k}x_{k}^{ak}.x^{m}=å_{k=0}^{m}S(m,k)(x)_{k}.

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

The Decomposition Theorem |