Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVexillary signed permutations revisited
138
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 permutations, including descriptions in terms of essential sets and pattern avoidance, and we relate them to the vexillary elements introduced by Billey and Lam.
rate research
Read More
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.
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 existing lower bound obtained by Bafna and Pevzner through breakpoint graphs. In this paper, we prove that the two lower bounds are equal. Moreover, we confirm a related conjecture on skew-symmetric plane permutations, which can be restated as follows: let $p=(0,-1,-2,ldots -n,n,n-1,ldots 1)$ and let $$ tilde{s}=(0,a_1,a_2,ldots a_n,-a_n,-a_{n-1},ldots -a_1) $$ be any long cycle on the set ${-n,-n+1,ldots 0,1,ldots n}$. Then, $n$ and $a_n$ are always in the same cycle of the product $ptilde{s}$. Furthermore, we show the new lower bound via plane permutations can be interpreted as the topological genera of orientable surfaces associated to signed permutations.
We show that the number of members of S_n avoiding any one of five specific triples of 4-letter patterns is given by sequence A111279 in OEIS, which is known to count weak sorting permutations. By numerical evidence, there are no other (non-trivial) triples of 4-letter patterns giving rise to this sequence. We make use of a variety of methods in proving our result, including recurrences, the kernel method, direct counting, and bijections.
This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set $S$ with asymptotic density $sigma$ and, on the other hand, permutations selected according to the Ewens distribution with parameter $sigma$. In particular we show that the asymptotic expected number of cycles of random permutations of $[n]$ with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter 1/2 are all ${1 over 2} log n + O(1)$, and the variance is of the same order. Furthermore, we show that in permutations of $[n]$ chosen from the Ewens distribution with parameter $sigma$, the probability of a random element being in a cycle longer than $gamma n$ approaches $(1-gamma)^sigma$ for large $n$. The same limit law holds for permutations with cycles carrying multiplicative weights with average $sigma$. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.
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 shows that, under the strong Bruhat order on $S_n$, up-sets are positively correlated (in the Harris--Kleitman sense). Thus, for example, for a (uniformly) random permutation $pi$, the event that no point is displaced by more than a fixed distance $d$ and the event that $pi$ is the product of at most $k$ adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure $1/2$ whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
