Cycle Decomposition of Permutations

FlickS
Messages
3
Reaction score
0

Homework Statement


Let α = (α1α2...αs) be a cycle, for positive integers α1α2...αs. Let π be any permutation that παπ-1 is the cycle (π(α1)πα2...π(αs)).

Homework Equations

The Attempt at a Solution


I started by choosing a specific α and π, and tried finding παπ-1 to give myself some idea of what to do but have had no luck. Suggestions would be welcomed.
 
Physics news on Phys.org
FlickS said:

Homework Statement


Let α = (α1α2...αs) be a cycle, for positive integers α1α2...αs. Let π be any permutation that παπ-1 is the cycle (π(α1)πα2...π(αs)).

Homework Equations

The Attempt at a Solution


I started by choosing a specific α and π, and tried finding παπ-1 to give myself some idea of what to do but have had no luck. Suggestions would be welcomed.

For example, work out what is ##\pi \alpha \pi^{-1}(\pi(\alpha_1))##?
 
I would get παπ−1(π(α1)) = πα(α1)) = πα2?
It gives me the next element in the cycle. So παπ−1 would be that cycle.
I'm still relatively confused.
 
FlickS said:
I would get παπ−1(π(α1)) = πα(α1)) = πα2?
It gives me the next element in the cycle. So παπ−1 would be that cycle.
I'm still relatively confused.

Let's set ##\sigma=\pi \alpha \pi^{-1}## for short. You've shown ##\sigma(\pi(\alpha_1))=\pi(\alpha_2)##. Generalizing that I'd say the cycle structure of ##\sigma## is ##(\pi(\alpha_1)\pi(\alpha_2)...)##. Still confused?
 
Dick said:
Let's set ##\sigma=\pi \alpha \pi^{-1}## for short. You've shown ##\sigma(\pi(\alpha_1))=\pi(\alpha_2)##. Generalizing that I'd say the cycle structure of ##\sigma## is ##(\pi(\alpha_1)\pi(\alpha_2)...)##. Still confused?
Okay, that definitely makes its more clear. Thanks so much!
 
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