Some congruencesEnumeration of symmetry classesGraphsThe 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

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:

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))/( Õiiaiai!), where c bar (a) :=(1)/(2) åii ·ai2-(1)/(2) åi odd ai + år<saras gcd (r,s).

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

v \k01234
111111
212345
314102035
411166276900
51347921068890005
6115625506160195243571400
Check these numbers and compute some more of them.
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
last changed: January 19, 2005

Some congruencesEnumeration of symmetry classesGraphsThe cycle type of the induced action on 2-subsets