Adjacent transpositions: question about definition

Click For Summary
SUMMARY

The discussion centers on the definition of adjacent transpositions in permutations, specifically whether they refer to the original set or the result after a transposition is applied. The example provided with the ordered set <1,2,3> illustrates that while (1,2) and (2,3) are adjacent transpositions, applying (1,2) first alters the set to <2,1,3>, making (2,3) no longer adjacent. Despite this, definitions found online confirm that (2,3) remains an adjacent transposition, which contradicts the intuitive understanding of swapping neighbors at each step. The clarification emphasizes that the notation (2,3) consistently refers to the second and third elements of the permutation.

PREREQUISITES
  • Understanding of permutations and their properties
  • Familiarity with the concept of transpositions in mathematics
  • Knowledge of mathematical notation and mappings
  • Basic grasp of the implications of element positioning in ordered sets
NEXT STEPS
  • Research the properties of permutations in group theory
  • Explore the concept of transpositions in detail, focusing on their role in permutation groups
  • Learn about the implications of adjacent transpositions in sorting algorithms
  • Study mathematical mappings and their applications in combinatorics
USEFUL FOR

Mathematicians, computer scientists, and students studying combinatorics or group theory, particularly those interested in the properties of permutations and transpositions.

nomadreid
Gold Member
Messages
1,762
Reaction score
248
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.
 
Physics news on Phys.org
Initial statement: (1,3) - end points - adjacent. After trans. (2,3) - end points - not adjacent. Doesnt look right.
 
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
 
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   Reactions: nomadreid
Super! Thanks, PeroK. That clears up the confusion. Question answered!.
 

Similar threads

  • · Replies 0 ·
Replies
0
Views
1K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 15 ·
Replies
15
Views
3K
  • · Replies 1 ·
Replies
1
Views
11K
  • · Replies 57 ·
2
Replies
57
Views
7K
  • · Replies 4 ·
Replies
4
Views
7K
  • · Replies 17 ·
Replies
17
Views
10K
  • · Replies 2 ·
Replies
2
Views
3K