An official website of the United States government
Chow rings of flag varieties have bases of Schubert cycles \sigma_u, indexed by permutations. A major problem of algebraic combinatorics is to give a positive combinatorial formula for the structure constants of this basis. The celebrated Littlewood-Richardson rules solve this problem for special products \sigma_u \cdot \sigma_v where u and v are p-Grassmannian permutations. Building on work of Wyser, we introduce backstable clans to prove such a rule for the problem of computing the product \sigma_u \cdot \sigma_v when u is p-inverse Grassmannian and v is q-inverse Grassmannian. By establishing several new families of linear relations among structure constants, we further extend this result to obtain a positive combinatorial rule for \sigma_u \cdot \sigma_v in the case that u is covered in weak Bruhat order by a p-inverse Grassmannian permutation and v is a q-inverse Grassmannian permutation.
more »
« less
RSK Tableaux and the Weak Order on Fully Commutative Permutations
For each fully commutative permutation, we construct a “boolean core,” which is the maximal boolean permutation in its principal order ideal under the right weak order. We partition the set of fully commutative permutations into the recently defined crowded and uncrowded elements, distinguished by whether or not their RSK insertion tableaux satisfy a sparsity condition. We show that a fully commutative element is uncrowded exactly when it shares the RSK insertion tableau with its boolean core. We present the dynamics of the right weak order on fully commutative permutations, with particular interest in when they change from uncrowded to crowded. In particular, we use consecutive permutation patterns and descents to characterize the minimal crowded elements under the right weak order.
more »
« less
- Award ID(s):
- 2054436
- PAR ID:
- 10511997
- Publisher / Repository:
- The Electronic Journal of Combinatorics
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 30
- Issue:
- 4
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let π n be a uniformly chosen random permutation on [ n ]. Using an analysis of the probability that two overlapping consecutive k -permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths k ∈ {1, 2,…, n } in π n is n 2 2 ( 1 - o ( 1 ) ) {{{n^2}} \over 2}\left( {1 - o\left( 1 \right)} \right) as n → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.more » « less
-
A box-ball system (BBS) is a discrete dynamical system consisting of n balls in an infinite strip of boxes. During each BBS move, the balls take turns jumping to the first empty box, beginning with the smallest-numbered ball. The one-line notation of a permutation can be used to define a BBS state. This paper proves that the Robinson-Schensted (RS) recording tableau of a permutation completely determines the dynamics of the box-ball system containing the permutation. Every box-ball system eventually reaches steady state, decomposing into solitons. We prove that the rightmost soliton is equal to the first row of the RS insertion tableau and it is formed after at most one BBS move. This fact helps us compute the number of BBS moves required to form the rest of the solitons. First, we prove that if a permutation has an L-shaped soliton decomposition then it reaches steady state after at most one BBS move. Permutations with L-shaped soliton decompositions include noncrossing involutions and column reading words. Second, we make partial progress on the conjecture that every permutation on n objects reaches steady state after at most n-3 BBS moves. Furthermore, we study the permutations whose soliton decompositions are standard; we conjecture that they are closed under consecutive pattern containment and that the RS recording tableaux belonging to such permutations are counted by the Motzkin numbers.more » « less
-
A permutation in a finite symmetric group on a set of ordered elements has a descent at the i-th index if the permutation value at the i-th index is greater than the permutation value that follows. The descent set of a permutation is the set of all indices where the permutation has a descent. Each finite symmetric group can be partitioned by descent sets. In this paper we study the Hamming metric and the L-infinity metric on the sets of permutations that share the same descent set for all nonempty descent sets to determine the maximum possible value that these metrics can achieve when restricted to these subsets.more » « less
-
We study relationships between permutation statistics and pattern-functions, counting the number of times particular patterns occur in a permutation. This allows us to write several familiar statistics as linear combinations of pattern counts, both in terms of a permutation and in terms of its image under the fundamental bijection. We use these enumerations to resolve the question of characterizing so-called "shallow" permutations, whose depth (equivalently, disarray/displacement) is minimal with respect to length and reflection length. We present this characterization in several ways, including vincular patterns, mesh patterns, and a new object that we call "arrow patterns." Furthermore, we specialize to characterizing and enumerating shallow involutions and shallow cycles, encountering the Motzkin and large Schröder numbers, respectively.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/11877
