Transposition graphs, stirling numbers and the parity theorem for permutations

Date of Publication

2006

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Arlene A. Pascasio

Defense Panel Member

Jose Tristan F. Reyes
Sonia Y. Tan
Mark A. Garcia

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Print

Accession Number

TU13532

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

vi, 48 leaves : ill.

Keywords

Algebra, Abstract; Graph theory; Algebra--Graphic methods; Permutations; Combinatorial analysis; Mathematical recreations

This document is currently not available here.

Share

COinS