Transposition graphs, stirling numbers and the parity theorem for permutations

• Main Authors: Abis, Genesis V., Sioco, Elaine S.
• Format: text
• Language: English
• Published: Animo Repository 2006
• Subjects: Algebra, Abstract; Graph theory; Algebra > Graphic methods; Permutations; Combinatorial analysis; Mathematical recreations
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/17431
• Institution: De La Salle University

This thesis is about an interplay between Abstract Algebra, Graph Theory, Combinatorics and Recreational Mathematics. In abstract Algebra, the Parity Theorem states that every permutation can be written as a product of either an even number of transpositions or an old number of transpositions but not both. In most textbooks, this theorem is proved in a non-pictorial and unintuitive manner. This thesis discusses an alternative proof to the theorem that is pictorial and constructive. The key to do this to define a transposition Graph Gn associated with the permutation group on n distinct elements. Gn has permutations as verticies wherein two are joined by an edge if one is obtained from the other by a transposition. The recursive construction of Gn and its nested structure turns out to be related to the Stirling numbers. This thesis is an exposition of the article Transposition Graphs: An Intuitive Approach to The Parity Theorem for Permutations , by Dean Clark which appeared in the April 2005 issue of Mathematics Magazine.