Adjacent transpositions: question about definition

In summary, the conversation discusses the definition of adjacent transpositions in a permutation. It is clarified that the transpositions refer to the original set and not the last result before the transposition is applied. The example of <1,2,3> is used to demonstrate that even after composing (2,3) and (1,2), (2,3) is still considered an adjacent transposition. This may go against intuition, but the numbers in the transposition are fixed and always mean the same thing. The conversation ends with a thank you for the clarification.
  • #1
nomadreid
Gold Member
1,732
231
Question: In defining adjacent transpositions in a permutation as swaps between neighbors, is one referring to the original set or to the last result before the transposition is applied? I clarify with an example.
Suppose one assumes a beginning ordered set of <1,2,3>
It is clear that (1,2) (2,3), and (1,3) are the adjacent transpositions for <1,2,3>
However, if I compose them (2,3)(1,2), I first apply the transposition (1,2) to <1,2,3> I now have <2,1,3> and now 2 and 3 are no longer neighbors. So is (2,3) still considered an adjacent transposition?
According the the definitions I find on the Internet, it appears that the answer is yes, but this goes contrary to the intuition of sapping neighbors at each step.
Thanks.
 
Mathematics news on Phys.org
  • #2
Initial statement: (1,3) - end points - adjacent. After trans. (2,3) - end points - not adjacent. Doesnt look right.
 
  • #3
mathman said:
Initial statement: (1,3) - end points - adjacent. After trans. (2,3) - end points - not adjacent. Doesnt look right.
Thanks, mathman. I am not sure which part doesn't look right to you. I picked a short example, but perhaps a longer example would be appropriate. (I can give the source if desired.)
adjacent.png
 
  • #4
nomadreid said:
So is (2,3) still considered an adjacent transposition?
According the the definitions I find on the Internet, it appears that the answer is yes, but this goes contrary to the intuition of swapping neighbors at each step.
Thanks.
The numbers in the transposition are fixed dummy variables. ##(2,3)## always means the same thing: swap the second and third elements in the permutation. It does not mean "swap the numbers 2 and 3, wherever they may be". You can look at ##(2, 3)## as the mapping:
$$(2, 3): (x, y, z) \rightarrow (x, z, y)$$
 
  • Love
Likes nomadreid
  • #5
Super! Thanks, PeroK. That clears up the confusion. Question answered!.
 

FAQ: Adjacent transpositions: question about definition

What is an adjacent transposition?

An adjacent transposition is a specific type of permutation in which two elements that are next to each other in a sequence are swapped. For example, in the sequence (1, 2, 3, 4), an adjacent transposition could swap 2 and 3 to produce (1, 3, 2, 4).

How are adjacent transpositions represented in permutation notation?

In permutation notation, an adjacent transposition that swaps elements at positions i and i+1 is typically represented as (i, i+1). For instance, the adjacent transposition that swaps the second and third elements would be written as (2, 3).

What is the significance of adjacent transpositions in combinatorics?

Adjacent transpositions are significant in combinatorics as they form a basis for the symmetric group, which consists of all possible permutations of a finite set. They can be used to express any permutation as a product of adjacent transpositions, making them fundamental in studying permutation structures and algorithms.

Can adjacent transpositions be used to sort a sequence?

Yes, adjacent transpositions can be used to sort a sequence. The process of sorting can be achieved by repeatedly applying adjacent transpositions to move elements into their correct positions, often referred to as bubble sort or adjacent swapping in sorting algorithms.

Are adjacent transpositions commutative?

No, adjacent transpositions are not commutative. The order in which adjacent transpositions are applied can affect the final arrangement of the elements. For example, applying (1, 2) followed by (2, 3) yields a different result than applying (2, 3) followed by (1, 2).

Similar threads

Back
Top