A topological framework for signed permutations

DOI10.1016/J.DISC.2017.03.019MaRDI QIDQ2359959zbMATH OpenOpenAlexWikidataFDO

Authors Fenix W. D. Huang, Christian M. Reidys

Publication date 23 June 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4706

zbMATH Keywords

\(\pi\)-mapfatgraphPoincaré dualreversal distancesigned permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: In this paper we present a topological framework for studying signed permutations and their reversal distance. As a result we can give an alternative approach and interpretation of the Hannenhalli-Pevzner formula for the reversal distance of signed permutations. Our approach utlizes the Poincar'e dual, upon which reversals act in a particular way and obsoletes the notion of "padding" of the signed permutations. To this end we construct a bijection between signed permutations and an equivalence class of particular fatgraphs, called $pi$-maps, and analyze the action of reversals on the latter. We show that reversals act via either slicing, gluing or half-flipping of external vertices, which implies that any reversal changes the topological genus by at most one. Finally we revisit the Hannenhalli-Pevzner formula employing orientable and non-orientable, irreducible, $pi$-maps.

Recommendations

• SORTING SIGNED PERMUTATIONS BY FIXED-LENGTH REVERSALS
• On the average number of reversals needed to sort signed permutations
• A very elementary presentation of the Hannenhalli-Pevzner theory
• scientific article; zbMATH DE number 1786450
• Transforming cabbage into turnip

Cites work

• A new combinatorial identity for unicellular maps, via a direct bijective approach
• A very elementary presentation of the Hannenhalli-Pevzner theory
• Counting unicellular maps on non-orientable surfaces
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Fatgraph models of proteins
• Fermionic sector of the 8-dimensional Kaluza-Klein theory
• Genome Rearrangements and Sorting by Reversals
• scientific article; zbMATH DE number 1303563 (Why is no real title available?)
• scientific article; zbMATH DE number 6472609 (Why is no real title available?)
• scientific article; zbMATH DE number 3246034 (Why is no real title available?)
• RNA folding and large \(N\) matrix theory
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• Transforming cabbage into turnip

Cited in

(7)

• Topological equivalents to n-permutability
• On the topology of the permutation pattern poset
• Moduli spaces and macromolecules
• scientific article; zbMATH DE number 5186439 (Why is no real title available?)
• scientific article; zbMATH DE number 6928875 (Why is no real title available?)
• scientific article; zbMATH DE number 854874 (Why is no real title available?)
• Short topological decompositions of non-orientable surfaces

This page was built for publication: A topological framework for signed permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359959)