The Reversal Poset of Signed Permutations

Awik, Fadi A (2021) The Reversal Poset of Signed Permutations. Masters thesis, Northern Arizona University.

Text Awik_2021_reversal_poset_signed_permutations.pdf - Published Version Restricted to Repository staff only Download (343kB) | Request a copy

Abstract

The set of signed permutations S±(n) has a fascinating structure. A reversal acting on a permutation π ∈ S±(n) reverses the order of elements in consecutive positions and changes their signs. As a group, S±(n) is generated by the collection of reversals. The reversal distance of a signed permutation π ∈ S±(n) is equal to the minimal number of reversals needed to transform π into the identity permutation. The reversal poset on S±(n) is a poset whose elements are signedpermutations with covering relations determined by: u < v if and only if there exists a reversal that transforms v into u and the reversal distance of u is one less than the reversal distance of v. The reversal poset is ranked by reversal distance. We refer to a signed permutation that attains the maximal reversal distance in S±(n) as a maximal permutation. These are the permutations of maximal rank in the reversal poset on S±(n). It turns out that maximal permutations in S±(n) have reversal distance n+1 when n is not 1 or 3. In this thesis, we derive several results pertaining to the structure of the reversal poset and enumerate permutations of rank 0, 1, 2, and n + 1, and obtain partial results for reversal distance n. Our main result is an enumeration of the maximal permutations.

Item Type:	Thesis (Masters)
Publisher’s Statement:	© Copyright is held by the author. Digital access to this material is made possible by the Cline Library, Northern Arizona University. Further transmission, reproduction or presentation of protected items is prohibited except with permission of the author.
Keywords:	genome rearrangements; inversions; reversal poset; reversals; signed permutations
Subjects:	Q Science > QA Mathematics
NAU Depositing Author Academic Status:	Student
Department/Unit:	Graduate College > Theses and Dissertations College of the Environment, Forestry, and Natural Sciences > Mathematics and Statistics
Date Deposited:	18 Feb 2022 16:42
Last Modified:	18 Feb 2022 16:42
URI:	https://openknowledge.nau.edu/id/eprint/5716

Actions (login required)

IR Staff Record View

Downloads