Algebraic Combinatorics -- The cycle type of the induced action on 2-subsets

The cycle type of the induced action on 2-subsets

The cycle type of the induced action on 2-subsets

Lemma: If pÎS_v, then
Each i-cycle of p, i odd, contributes to bar ( p) exactly (i-1)/2 cyclic factors, each of which is an i-cycle.
Each i-cycle of p, i even, contributes to bar ( p) exactly one cycle of length i/2 and (i/2)-1 further cycles, which are of length i.
Each pair of cyclic factors of p, say an i-cycle and a j-cycle, contributes to bar ( p) exactly gcd (i,j) cyclic factors, each of which has the length lcm (i,j).
All the cyclic factors of bar ( p) arise in this way.

Proof:

i) First let i be odd. Without loss of generality we may assume that the i-cycle in question is (1, ...,i). Consider a positive k <= (i-1)/2. Then bar ( p) contains the following cyclic permutation of 2-subsets:

( {1,k+1 }, {2,k+2 }, ..., {i-k,i }, {1,i-k+1 }, ..., {k,i }).

This cycle is of length i, and the cycles of this form arising from different k <= (i-1)/2 are pairwise disjoint. Furthermore these are all the cycles arising from (1, ...,i) since, for each such k, we have, as i is odd:

( {1,k+1 }, {2,k+2 }, ...)=( {1,i-k+1 }, {2,i-k+2 }, ...).

ii) If i is even, say i=2j, we may assume that the cyclic factor of p is (1 ...2j). It yields, for 2 <= k <= j, the (i/2)-1 different i-cycles

( {1,k }, {2,k+1 }, ..., {i-k+1,i }, {1,i-k+2 }, ..., {k-1,i }),

together with the (i/2)-cycle

( {1,j+1 }, ..., {j,2j }).

iii) A pair of cyclic factors of p, say the pair (1...i)(i+1...i+j) contributes to bar ( p) the following product of disjoint cycles:

( {1,i+k }, {2,i+k+1 }, ...)( {1,i+k+1 }, {2,i+k+2 }, ...) ...

The length of each of these cyclic factors is lcm (i,j), and their number is therefore equal to gcd (i,j).

iv) is clear.

This lemma yields the cycle structure of bar ( p) and the desired number c( bar ( p)) of cyclic factors which we need in order to evaluate the number of graphs on v vertices by an application of the Cauchy-Frobenius Lemma:

Corollary: For each bar ( p) on [v choose 2] we have:
If i is odd, then
a_i( bar ( p))=(a_i( p))/(2)(i ·a_i( p)-1)+a_2i( p) + å_{r<s lcm(r,s)=i} a_r( p)a_s( p) gcd (r,s).

If i is even, then
a_i( bar ( p))=(a_i( p))/(2)(i ·a_i( p)-2)+a_2i( p) + å_{r<s lcm(r,s)=i} a_r( p)a_s( p) gcd (r,s).

The total number of cyclic factors is
c( bar ( p))=(1)/(2) å_i i ·a_i( p)²-(1)/(2) å_{i odd}a_i( p) + å_r<sa_r( p)a_s( p) gcd (r,s).

In the next two programs you can enter a permutation and compute the cycle type and the total number of cyclic factors of the induced permutation on 2-subsets.

Thus, by an application of the Cauchy-Frobenius Lemma, we obtain

Corollary: The number of k-graphs on v vertices is equal to
v!^-1 å_{pÎS_v}(k+1)^{c( bar ( p))},
where c( bar ( p)) is as above. More explicitly and in terms of cycle types of v (see Corollary) this number is equal to
å_{a |¾| v}((k+1)^{c_{bar (a)}})/( Õ_ii^a_ia_i!), where c_{bar (a)} :=(1)/(2) å_ii ·a_i²-(1)/(2) å_{i odd} a_i + å_r<sa_ra_s gcd (r,s).

A table giving the first of these numbers looks as follows:

v \k 0 1 2 3 4

1 1 1 1 1 1

2 1 2 3 4 5

3 1 4 10 20 35

4 1 11 66 276 900

5 1 34 792 10688 90005

6 1 156 25506 1601952 43571400

Check these numbers and compute some more of them.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

The cycle type of the induced action on 2-subsets

v \k	0	1	2	3	4
1	1	1	1	1	1
2	1	2	3	4	5
3	1	4	10	20	35
4	1	11	66	276	900
5	1	34	792	10688	90005
6	1	156	25506	1601952	43571400