Counting by stabilizer class |

The preceding chapter was devoted to the enumeration of orbits by weight, a
problem that can be solved by an easy refinement of the
Cauchy-Frobenius Lemma.
In the present chapter we shall introduce another variation of this lemma
in order to count orbits by stabilizer class.
Recall that the elements of an orbit have
as their stabilizers a conjugacy class *[~U] * of subgroups
of *G*. We say that *[~U] * is the *type*

of this orbit.
The *set*
of orbits of type *[~U] *, for a given subgroup *U* of *G*, is
called the *[~U] *-*stratum* and indicated by

[~U] \\\X.

First we consider the lattice *L(G)* of
subgroups of *G*. The group *G* is supposed to be finite and hence *L(G)*
is a locally finite poset with respect to the inclusion order * <= * and we
shall be able to apply in particular the Moebius Inversion. We assume that
the subgroups *U ^{i}* of

U^{i}<= U^{k}Þ i <= k.

In this case the *zeta-matrix*
as well as the *Moebius-matrix*
of *G*, defined by

z(G):=(z(U^{i},U^{k})), and m(G):=(m(U^{i}, U^{k}))=z(G)^{-1},

are upper triangular.
Let us consider an easy example: *G:=S _{3}*.
This group has the lattice of subgroups shown in figure,

The subgroup lattice of *S*_{3}

where *U ^{1}=á1ñ, U^{2}=á(12)ñ,
U^{3}=á(13)ñ,
U^{4}=á(23)ñ, U^{5}=á(123)ñ*, and

m(S_{3})=().

1 -1 -1 -1 -1 3 1 0 0 0 -1 1 0 0 -1 1 0 -1 1 -1 1

In order to calculate
* | [~U] \\\X | *, we consider,
for the finite action * _{G}X* and

X_{U}:={x | " gÎU: gx=x}.

Burnside called the order
* | X _{U} | * of this set the

| X_{U}| =å_{x:U <= Gx}1=å_{V:U <= V <= G}å_{x:V=Gx}1=å_{V:U <= V <= G}(1)/(| [~V] |)å_{x:GxÎ[~V] }1

=å_{V:U <= V <= G}(| G/V |)/(| [~V] |)å_{tÎT:GtÎ[~V] }1 =å_{V:U <= V <= G}(| G/V |)/(| [~V] |)| [~V] \\\X | ,

=å_{V}z(U,V)(| G/V |)/(| [~V] |)| [~V] \\\X | ,

where
*T* denotes a transversal of the orbits of *G* on *X*.
By Moebius Inversion this equation is equivalent to:

| [~U] \\\X | =(| [~U] |)/(| G/U |)å_{V}m(U,V) | X_{V}| .

In order to simplify this expression we consider the set
*[~L] (G)* consisting of the conjugacy classes of subgroups of
*G*:

[~L] (G):={[~U]_{1},...,[~U]_{d}}, with representatives U_{i}Î[~U]_{i}.

(*U ^{i}* should not be mixed up with

b_{ik}:=(| [~U]_{i}|)/(| G/U_{i}|)å_{VÎ[~U] k}m(U_{i},V), and B(G):=(b_{ik}),

we can now reformulate the equation above
in terms of this matrix *B(G)*, which I
call the *Burnside matrix*
of *G* (in fact Burnside
considered the inverse of *B(G)* and called it
the table of marks; we shall return to this matrix later). It is
in fact the following lemma (and *not* the lemma of
Cauchy-Frobenius that is quite
often named after Burnside, see the remarks on history in the
chapter containing the comments and references) which is

Burnside's LemmaIfis a finite action, then the vector of the lengths_{G}X| [~U]of the strata of_{i}\\\X |GonXsatisfies the equation

We can apply this now in order to enumerate the *G*-classes on *Y ^{X}* by type.
Since

Corollary:The number of symmetry classes ofGonYof type^{X}[~U]is the_{i}i-th entry of the one column matrix

Thus, for example, the number of *k*-graphs on
*v* vertices which are
of type *[~U] _{j}*,

type\k 0 1 2 3 4 [~U] _1 0 0 11 100 465 [~U] _2 0 2 21 84 230 [~U] _3 0 1 9 36 100 [~U] _4 0 0 0 0 0 [~U] _5 0 2 9 24 50 [~U] _6 0 0 0 0 0 [~U] _7 0 0 1 4 10 [~U] _8 0 2 6 12 20 [~U] _9 0 2 6 12 20 [~U] _10 0 0 0 0 0 [~U] _11 1 2 3 4 5 å 1 11 66 276 900

Multigraphs on 4 vertices, counted by type

The last column of this table shows among
other things that there exist
altogether 900 4-graphs on 4 vertices, and that exactly 465 of them are of
type *[~U] _{1}*. Furthermore we note that the fourth, the sixth
and the tenth row of this table consist of zeros only, which stimulates the
question whether this also holds for bigger

(S_{X})_{f}=Å_{yÎY}S_{Xy}.

This implies

Corollary:The stabilizers of thefÎYare the subgroups^{X}U <= G, the corresponding permutation groupbar (U)of which satisfieswherebar (U)=S_{a}Ç bar (G),bar (G)corresponds toG, andSis the direct sum of the symmetric groups on the orbits of_{a}U:S_{a}:=Å_{wÎU\\X}S_{w}.

We can now answer one of the questions posed above concerning automorphism groups of graphs.

Corollary:The alternating groupAdoes not occur as an automorphism group of a multigraph on_{v}vvertices, ifv >= 3.

Proof: The assumption *bar (A) _{v} = S_{a}Çbar (S)_{v}* yields, as

A similar result holds for the cyclic group *C _{v}* (see
exercise *) and the alternating subgroup

m(U,[~V] ):=å_{WÎ[~V] }m(U,W),

we derive from *

Corollary:Ifis a finite action, then the number of orbits of length_{G}XkofGonXis equal toand in particular the number of(1)/(k)å_{i: | G/Ui | =k}| [~U]_{i}| å_{j}m(U_{i},[~U]_{j}) | X_{Uj}| ,primitive orbits, i.e. of orbits of the (maximal) length| G |, is equal to(1)/(| G |)å_{j}m(1,[~U]_{j}) | X_{Uj}| .

We consider a well known example from Galois theory.

Examples:Consider the finite fieldGF(q),q:=pa prime number, and its extension field^{m},pGF(qof degree^{n})n. By Galois theory its Galois groupGis generated by theFrobenius isomorphismwhich is of orders:GF(q^{n}) -> GF(q^{n}):x -> x^{q},n:MoreoverG=ásñ={1,s,...,s^{n-1}} simeq C_{n}.GF(qpossesses a^{n})normal basis, which means that there existxÎ GF(qsuch that^{n}){x,sx,..., sis a^{n-1}x}GF(q)-basis ofGF(q. Expressing the elements of^{n})GF(qin terms of this basis as^{n})GF(q)-linear combinationswe can identify them with vectorså_{i=1}^{n}f(i)s^{i}x, f(i)ÎGF(q),f=(f(1),...,f(n))Îon which the Galois group generatorq^{n}sacts as a cyclic shift. Hence the existence of a normal basis shows that the action of the Galois groupGonGF(qis isomorphic to the canonical action of the cyclic group^{n})Con_{n}. Denoting byq^{n}G\\the set of orbits of (maximal) length_{ | G | }X| G |, we now evaluate the numberof orbits of maximal length| G\\_{ | G | }GF(q^{n}) | = | C_{n}\\_{n}q^{n}|nof the Galois group. As the cyclic groupChas a subgroup lattice isomorphic to the lattice of divisors_{n}dofn, the Moebius functionmofL(Cis the number theoretic Moebius function. Moreover the unique subgroup of order_{n})d, wheredis a divisor ofn, in the cyclic groupCis generated by the power_{n}(1...n)of the full cycle and, by *, this power consists of^{n/d}n/ddisjoint cycles, each of which has the lengthd. FurthermorefÎis fixed under this subgroupq^{n}á(1...n)if and only if^{n/d}ñfis constant on the disjoint cyclic factors of(1...n). Hence, by *, we obtain^{n/d}where| G\\_{ | G | }GF(q^{n}) | = | C_{n}\\_{n}q^{n}| =(1)/(n)å_{d | n}m(d)q^{n/d},mdenotes the number theoretic Moebius function. Note that this number of primitive orbits is also equal to the number of irreducible monic polynomials with zeros inGF(qand coefficients in^{n})GF(q), since by Galois theory a root of a polynomial is mapped onto a root by each element of the Galois group. More generally, we can consider the orbits of maximal length ofCon_{n}. The numbersm^{n}are calledl_{mn}:= | C_{n}\\_{n}m^{n}| =(1)/(n)å_{d | n}m(d) m^{n/d}Dedekind numbers. Some of the smaller ones are shown in the following table:The.

m\n 1 2 3 4 5 1 1 0 0 0 0 2 2 1 2 3 6 3 3 3 8 18 48 4 4 6 20 60 204 5 5 10 40 150 624 fÎcan be considered asm^{n}wordsoff=f(1)...f(n)lengthnover thealphabet. Themlexicographically smallestelements in the orbits (for short:f£C) of length_{n}(f)nofCon_{n}form them^{n}canonic transversalits elements are called theL_{n}(m):={fÎm^{n}| | C_{n}(f) | =n,f£C_{n}(f)};Lyndon wordsof lengthnover the alphabet. The union of all these setsmis called theL(m):=È_{n}L_{n}(m)Lyndon setover the alphabet. Now we consider an arbitrary wordmfÎ. As each letterm^{n}iÎforms a Lyndon word of length 1, there exists a uniquely determined longest left factormlof_{1}(f)=f(1)...fwhich is a Lyndon word. The same holds for the remaining partwoff=l, and hence there is a unique decomposition_{1}(f)woff=l_{1}(f)l_{2}(f)...l_{l(f)}(f)finto Lyndon words such that in the right partlthe Lyndon word_{i}(f)...l_{l(f)}(f)lis the maximal left Lyndon factor. This decomposition is called the_{i}(f)Lyndon decompositionoff, and the numberl(f)of factors is called theLyndon lengthoff. Even more, the Lyndon decomposition can also be described as follows (exercise *)Using the Lyndon length we can define the following generating function:Lyndon's TheoremThe factorslof the decomposition * defined above are lexicographically nonincreasing:_{i}(f)Conversely, each decomposition into nonincreasing Lyndon words is the decomposition * introduced above.l_{1}(f)³l_{2}(f)³...³l_{l(f)}(f).which generates the numbers of words of lengthl_{n}(x,m):=å_{fÎmn}x^{l(f)},noverwith prescribed Lyndon length. V. Strehl has recently noticed and proved the remarkable fact that this function is symmetric inmxandm. For exampleIn order to prove this it is enough to show that, for alll_{3}(x,m)=(1)/(3!)(x^{3}m^{3}+3(x^{3}m^{2}+x^{2}m^{3}-x^{2}m^{2})+2(x^{3}m+m^{3}x)-2xm).k,m,nin, the identityN^{*}lis true. We consider a second alphabet_{n}(k,m)=l_{n}(m,k), say, and the corresponding setkof all the words overk^{*}. LetkF(denote the set of all the mappingsm,k)f:L(such that all but a finite number of valuesm) ->k^{*}f(f)are equal to the empty wordepsÎ. We mapk^{*}fonto[^f] :L(, defined as follows: Letk) ->m^{*}[^f] ÎL(occur in the Lyndon decompositions ofk)f(f, say with the multiplicity_{i})m(f(f. We can assume without restriction that_{i}),[^f] )f, for each_{i}³f_{i+1}i. Then putLet us consider an example. Assume that[^f] ([^f] ):=f_{1}·...·f_{i}·...·f_{i}_{m(f(fi),[^f] )}·...·f_{n}.f:L(has the following nonempty images (we separate Lyndon factors by dots):3) ->2^{*}thenf(12)=2·12, f(113)=12·1·1, f(2)=2·12·1,[^f]has just the following nonempty images:It is clear that[^f] (1)=2·113·113, [^f] (12)=2·12·113, [^f] (2) =2·12.fcan be reconstructed from[^f], and Lyndon's Theorem assures that this is true also in general. Hencef -> [^f]is a bijection betweenF(andm,k)F(. Now we introduce ak,m)normby puttingwhere| | f | | :=å_{fÎL(m)}| f | | f(f) | ,| w |denotes the length (number of letters) of the wordw. An important property of the norm is the identitywhere the last equation holds since| | f | | =å_{fÎL(m)}| f | å_{[^f] ÎL(k)}| [^f] | ·m(f(f),[^f] )= | | [^f] | | ,m(f(f),[^f] )=m([^f] ([^f] ),f), by construction of[^f].Proof: ConsiderLemma:(Strehl)For allk,m,nÎwe have the identityN^{*}l_{n}(k,m)=l_{n}(m,k).fÎand the corresponding subsetm^{n}L, consisting of the following_{f}ÍF(m,k)f:f(f')=epsif and only if the Lyndon wordf'is not a factor off, while otherwisef(f')Î. Easy checks show thatk^{m(f,f')}| Land_{f}| =k^{l(f)}which allows to complete the proof:fÎÈ_{fÎmn}L_{f}iff | | f | | =n,l_{n}(k,m)=å_{fÎmn}k^{l(f)}= | {fÎF(m,k) | | | f | | =n } |Now we use a further indeterminate= | {[^f] ÎF(k,m) | | | [^f] | | =n} | = å_{[^f] Îkn}m^{l([^f] )}=l_{n}(m,k).zin order to define the formal power seriesLyndon's Theorem shows that the following is true:L(x,m):=å_{n}l_{n}(x,m)z^{n}.so that we obtain the following surprising result:L(x,m)=Õ_{n}((1)/(1-k·z^{n}))^{lmn},which implies in particular (putÕ_{n}((1)/(1-k·z^{n}))^{lmn}=Õ_{n}((1)/(1-m·z^{n}))^{lkn},k:=1and note thatlif_{1n}=1n=1, andl, otherwise):_{1n}=0The cyclotomic identityFor allk,m,nÎand the Dedekind numbersN^{*}lwe have the identity_{mn}=(1)/(n)å_{d | n}m(d) m^{n/d}Õ_{n}((1)/(1-z^{n}))^{lmn}=(1)/(1-m·z).

E:Prove the following identity for the elements of the Burnside matrix:b_{ik}=m([~U]_{i},U_{k})(| [~U]_{k}|)/(| G/U_{i}|), where m([~U]_{i},U_{k}):= å_{VÎ[~U] i}m(V,U_{k}).

E:Prove that the cyclic groupCdoes not occur as an automorphism group of a multigraph on_{v}vvertices, ifv³2.

E:Prove that the subgroupAof_{v-1}Adoes not occur as an automorphism group of a multigraph on_{v}vvertices, ifv³3.

E:Prove *.

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 |

Counting by stabilizer class |