If a given permutation in S_n has a given cycle type, describe sgn(sig).

Edellaine
Messages
11
Reaction score
0

Homework Statement


5.4: If sigma in S_n has cycle type n_1,...,n_r, what is sgn(sig)? (sgn is the sign homomorphism)

Homework Equations


sgn(sigma) = 1 if sigma is even. sgn(sigma) = -1 is sigma is odd
cycle type is the length of the cycle type. If n_2 = 2, sigma has two 2-cycles.

The Attempt at a Solution


I know what cycle type is (if n_i = j, there are j cycles of length i), and sgn(sigma) is easy. How would I go about expanding (sig) to find how many two cycles I have, if that's even what I should be doing. It doesn't seem that worthwhile to generalize this for cycle type.

I was thinking of writing sgn(sig) as a product of sgn(sig_i) where (sig_i) is an individual cycle of the product of cycles forming (sig), but I don't think that exactly accounts for multiples.

I'm also not sure how to come up with conditions that will say, depending on r, if sgn(sig) = 1, or sgn(sig) = -1.
 
Physics news on Phys.org
I'm not quite following your notation here. But to get the sign you just take (-1)^(number of even length cycles), right?
 
Yup. But since you can write any n-cycle as a product of 2-cycles, how do I account for the cycles of odd length.
 
Cycles of even length break into an odd number of two cycles, cycles of odd length break into an even number. I don't see the problem.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top