ﻻ يوجد ملخص باللغة العربية
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 Poincare 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.
We study the combinatorial properties of vexillary signed permutations, which are signed analogues of the vexillary permutations first considered by Lascoux and Schutzenberger. We give several equivalent characterizations of vexillary signed permutat
Computing the reversal distances of signed permutations is an important topic in Bioinformatics. Recently, a new lower bound for the reversal distance was obtained via the plane permutation framework. This lower bound appears different from the exist
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are ver
In this note we investigate correlation inequalities for `up-sets of permutations, in the spirit of the Harris--Kleitman inequality. We focus on two well-studied partial orders on $S_n$, giving rise to differing notions of up-sets. Our first result s
There is a bijection from Schroder paths to {4132, 4231}-avoiding permutations due to Bandlow, Egge, and Killpatrick that sends area to inversion number. Here we give a concise description of this bijection.