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ÎSv(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

The cycle type of the induced action on 2-subsets