Injective proof about sizes of conjugacy classes in S_n - MathOverflow

Injective proof about sizes of conjugacy classes in S_n

2009-10-27T20:34:03Z

It's not hard to count the number of permutations in a given conjugacy class of S_n. In particular, the number of permutations in S_n whose cycle decomposition has c_i i-cycles is n!/(Π_i=1ⁿ c_i!i^c_i). It's also not too hard to see that this is maximized for the conjugacy class that leaves one element fixed and permutes the others in an (n-1)-cycle, and that this is strictly the maximum when n ≥ 3.

What I'm looking for is an "injective proof" of this fact. Namely, a set of injections from the other conjugacy classes into the set of (n-1)-cycles. Ideally you should be able to define a single nice function from S_n into these cycles, which is injective but not surjective (for n ≥ 3) when restricted to every other conjugacy class.

Answer by Sonia Balagopalan for Injective proof about sizes of conjugacy classes in S_n

2009-10-28T08:09:46Z

This is rather vague, but I'll try and restate the question to something I think can be done without much difficulty. Here goes:
What you want is a fixed way of representing each permutation (written as its cycle decomposition, but with rules as to what order the cycles are written in and for picking first elements of each cycle, and an ordering of all permutations of a particular cycle type under this "representation"), such that the (n-1)-cycles you get from reading off the first n-1 symbols of each permutation are all different.

We can write down the permutation \sigma with bigger cycles first, and within cycles of same size (if size >1), we can choose the cyle containing the least of the symbols (from {1,2,...,N}), say x, let the first cycle be (x,\sigma(x),...,\sigma^(d-1)(x)) (where d is the order of x in \sigma), look for the smallest of the remaining symbols, etc. For cycles of size 1, we may have to reverse the ordering, or apply some sort of cyclic order.

Answer by Lavender Honey for Injective proof about sizes of conjugacy classes in S_n

2009-11-03T16:22:52Z

For any cycle decomposition, we can uniquely order the cycles from smallest length to largest length, breaking ties between cycles of the same length in some fixed arbitrary way (say by maximal elements). Let us do this for concreteness.

Suppose there was an (injective) way to "join" and A-cycle and a B-cycle together to form an A+B cycle whenever |A| and |B| are > 1. Then, given any cycle decomposition as above, one can start bubbling the two largest cycles together to eventually form a single cycle of some length m.

If m = n - 1, we are done.

If m = n, write S = (1............) and then omit the last term.

If m = 1 the problem is very easy.

If n - 1 > m > 2, there is an injective map from m-cycles to elements whose cycle decomposition is a product of an m-cycle with a 2-cycle. For concreteness, one can add the 2-cycle with the two lowest missing entries. Now bubble again to form an m+2 cycle.

If m = 2, and n is at least 5, bubble with a 3-cycle.

If m = 2 and n = 4 (the last case), form whatever bijection you like between the two sets of 6 elements.

The key point is therefore to find a way to bubble an A-cycle and a B-cycle when |A|,|B| > 1. We do this as follows.

Amongst the entries of A and B, there is a unique smallest integer, call it X.

Case 1. If X lies in A, Let Z denote the largest element of B. Then one can (uniquely) write A = (X.....) and B = (.....Y,Z), where Y < Z. Then consider the A+B cycle obtained by concatenating A and B in this form, i.e. (X,......,Y, Z).

Case 2. If X lies in B, let Z denote the smallest element of A. Then one can (uniquely) write B = (X....) and A = (.....,Y,Z), where now Y > Z. Then consider the A+B cycle (X,.....,Y,Z).

Given an A+B cycle, one can uniquely write it in the form (X,....,Y,Z), where X is the smallest entry. Then one can break it up into an A-cycle and B-cycle depending on whether Y < Z or Y > Z.

Since this was apparently a little confusing, suppose that the cycle lengths of S are a_1 <= a_2 <= a_3 <= ..... <= a_r. Here I omit the 1-cycle lengths, so a_1 > 1, and sum a_r = m for some m possibly less than n. Then the cycle lengths of the steps in the algorithm will have lengths:

(a_1, ...., a_(r-1),a_r),

(a_1, ...., a_(r-2),a_(r-1) + a_r),

(a_1, ...., a_(r-3),a_(r-2) + a_(r-1) + a_r),

....

(a_1 + a__2 + ... + a_r) = (m)

(2,m)

(m+2)

(2,m+2)

(m+4)

...

(n-1 or n, depending on m mod 2),

then n-1.

(if m = 2 and n is at least 5, then instead it should go

(2) --> (2,3) --> (5) --> (2,5) --> (7) --> (2,7) --> (9) ...,etc.

Answer by Michael Lugo for Injective proof about sizes of conjugacy classes in S_n

2009-11-03T16:48:03Z

The second largest conjugacy class in S_n is the n-cycles, which make up 1/n of all elements of S. Although I haven't thought about this too hard, it may be easier to find an injection from C to the set of n-cycles in S_n, where C is any conjugacy class in S_n other than the largest one. The "hard part" here in finding an injection from C to permutations with a fixed point and an (n-1)-cycle could be choosing the fixed point, and finding an injection from C to the set of n-cycles would avoid that problem.