Keywords: positroids varieties, plabic graphs, bridge graphs, bounded affine permutations, Deodhar parametrizations, positive distinguished subexpressions

Bridge Graphs and Deodhar Parametrizations for Positroid Varieties

Rachel Karpman † University of Michigan, Ann Arbor, United States Abstract. A parametrization of a positroid variety Π of dimension d is a regular map (C × ) d → Π which is birational onto a dense subset of Π. There are several remarkable combinatorial constructions which yield parametrizations of positroid varieties. We investigate the relationship between two families of such parametrizations, and prove they are essentially the same. Our first family is defined in terms of Postnikov's boundary measurement map, and the domain of each parametrization is the space of edge weights of a planar network. We focus on a special class of planar networks called bridge graphs, which have applications to particle physics. Our second family arises from Marsh and Rietsch's parametrizations of Deodhar components of the flag variety, which are indexed by certain subexpressions of reduced words. Projecting to the Grassmannian gives a family of parametrizations for each positroid variety. We show that each Deodhar parametrization for a positroid variety corresponds to a bridge graph, while each parametrization from a bridge graph agrees with some projected Deodhar parametrization.

Introduction

Lusztig defined the totally nonnegative part of an abstract flag manifold and conjectured that it was made up of cells, a conjecture later proved by Rietsch [START_REF] Lusztig | Total positivity in reductive groups[END_REF][START_REF] Lusztig | Total positivity in partial flag varieties[END_REF][START_REF] Rietsch | An algebraic cell decomposition on the nonnegative part of a flag variety[END_REF]. More than a decade later, Postnikov introduced the positroid stratification of the totally nonnegative Grassmannian Gr ≥0 (k, n), which Rietsch then showed was a special case of Lusztig's stratification [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF][START_REF] Lam | Network parametrizations for the Grassmannian[END_REF]. While Lusztig's approach relied on the machinery of canonical bases, Postnikov's was more elementary. Each of Postnikov's positroid cells is the locus in Gr ≥0 (k, n) where certain Plücker coordinates vanish.

The positroid stratification of Gr ≥0 (k, n) extends to a stratification of the complex Grassmannian Gr(k, n) of k-planes in n-space. That is, we can decompose Gr(k, n) The decomposition of Gr(k, n) into projected Richardson varieties was first studied by Lusztig [START_REF] Lusztig | Total positivity in partial flag varieties[END_REF]. Rietsch showed that this decomposition is a stratification, and described the closure partial order on the cells [START_REF] Rietsch | Closure relations for totally nonnegative cells in G/P[END_REF]. Brown, Goodearl and Yakimov investigated the same stratification from the viewpoint of Poisson geometry [START_REF] Brown | Poisson structures on affine spaces and flag varieties. I. Matrix affine Poisson space[END_REF]. Finally, Knutson, Lam and Speyer showed that Lusztig's (closed) strata were in fact the Zariski closures of Postnikov's totally nonnegative cells [START_REF] Knutson | Positroid varieties: juggling and geometry[END_REF].

Postnikov defined a family of maps onto each positroid cell in Gr ≥0 (k, n). The domain of each map is the space of positive real edge weights of some weighted planar network, and there is a class of such networks for each positroid cell [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF]. If we let the edge weights range over C × instead of R + we obtain a well-defined map onto a dense subset of the positroid variety Π in Gr(k, n) corresponding to the totally nonnegative cell Π≥0 [START_REF] Muller | The twist for positroid varieties[END_REF]. Specializing all but an appropriately chosen set of edge weights to 1 gives a birational map to a dense subset of Π, which we call an parametrization. In this paper, we investigate a particular class of network parametrizations, which arise from bridge graphs. Bridge graphs are constructed by an inductive process, and the definition of the corresponding parametrization is particularly straightforward. In addition, bridge graphs have proven to be a useful tool in particle physics [START_REF] Arkani-Hamed | Scattering amplitudes and the positive Grassmannian[END_REF].

Our second family of parametrizations arises from Deodhar's decompositions of F (n) [START_REF] Deodhar | On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells[END_REF]. Each Deodhar decomposition of F (n) refines the Richardson decomposition. Richardson varieties are indexed by intervals [u, w] in Bruhat order on the symmetric group S n . To define a Deodhar decomposition, choose a reduced word w for each w ∈ S n . For each chosen w, and each u ≤ w in Bruhat order, we can express the (open) Richardson variety Xw u indexed by [u, w] as a disjoint union of Deodhar components. The Deodhar components of Xw u are indexed by distinguished subexpressions for u in w; that is, by subwords for u in w which satisfy a technical condition.

Let Π ⊂ Gr(k, n) be a positroid variety, and fix a Deodhar decomposition of F (n). We have a family of Deodhar components D ⊂ F (n) such that the natural projection from F (n) to Gr(k, n) maps each D isomorphically to a dense subset of Π. These are precisely the top-dimensional Deodhar components of the Richardson varieties Xw u which project birationally to Π. For each such Xw u , the desired component is indexed by a special choice of subexpression for u in w called a positive distinguished subexpression, or PDS. Marsh and Rietsch defined matrix parametrizations for each Deodhar component of F (n) [START_REF] Marsh | Parametrizations of flag varieties[END_REF]. Composing with π k gives a family of parametrizations for the positroid variety Π, which we call projected Deodhar parametrizations or simply Deodhar parametrizations (Talaska and [START_REF] Lam | Network parametrizations for the Grassmannian[END_REF].

We will show that these two ways of parametrizing positroid varieties-via bridge graphs, and via pro-jected Deodhar parametrizations-are essentially the same. This result was first conjectured by Thomas Lam (Lam, 2013a). Our main result is the following.

Theorem 1.1. Let Π be a positroid variety in Gr(k, n). For each Deodhar parametrization of Π, there is a bridge graph which yields the same parametrization. Conversely, any bridge graph parametrization of Π agrees with some Deodhar parametrization.

t 1 t 2 t 3 t 4 4 3 2 1
Fig. 1: A bridge network. All unlabeled edges have weight 1.

To convey the flavor of this result, we briefly sketch an example; the details will appear later. Take k = 2 and n = 4. Let u = 2143 and w = 4321. The Richardson variety Xw u projects birationally to the positroid Πu,w . Fix the reduced word w = s 1 s 2 s 3 s 2 s 1 s 2 for w. The PDS u for u in w comprises the bolded entries in w, so we have Deodhar parametrization

(t 1 , t 2 , t 3 , t 4 ) → 1 0 0 0 0 1 0 0 x 2 (t 1 ) ṡ1 -1 x 2 (t 2 ) ṡ3 -1 x 2 (t 3 )x 1 (t 4 ) = 0 1 t 3 t 2 -1 -t 4 0 t 1 (1.1)
We claim that we can obtain the same map from a bridge graph. Indeed, The bridge graph in Figure 1 yields the parametrization:

(t 1 , t 2 , t 3 , t 4 ) → 1 t 4 0 -t 1 0 1 t 3 t 2 (1.2)
Note that the two parametrizations send the point (t 1 , t 2 , t 3 , t 4 ) to representative matrices which have the same row space, and hence correspond to the same point in Gr(2,4).

This work builds on a number of earlier results. Postnikov's Le-diagrams, which index positroid varieties, provided the first link between planar networks and PDS's. A Le-diagram is a Young diagram filled with 0's and +'s according to certain rules. There is a beautiful bijection between Le-diagrams and PDS's of Grassmannian permutations, permutations with a single descent at position k. Moreover, Postnikov constructed a planar network from each Le-diagram, which yields a parametrization of the corresponding positroid variety [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF].

Talaska and Williams explored the link between distinguished subexpressions and network parametrizations further in [START_REF] Lam | Network parametrizations for the Grassmannian[END_REF]. They considered Deodhar components of F (n) indexed by all distinguished subexpressions of Grassmannian permutations, not just PDS's. These Deodhar components project isomorphically to subsets of Gr(k, n), and the projections give a decomposition of Gr(k, n). Marsh and Rietsch's work yields a unique parametrization for each component [START_REF] Marsh | Parametrizations of flag varieties[END_REF].

Talaska and Williams proved that each of these parametrizations arises from a network, which they constructed explicitly. For components indexed by PDS's, they recovered the planar networks corresponding to Postnikov's Le diagrams; for the remaining components, their networks are nonplanar.

Here, we relax the requirement that our Deodhar components be indexed by subexpressions of Grassmannian permutations. Instead, we restrict our attention to Deodhar components which correspond to PDS's, and which project isomorphically to a subset of Gr(k, n). There is a family of such components for each positroid variety, which in turn gives a family of parametrizations. We construct a planar network for each such parametrization. The Le-diagrams defined by Postnikov, and recovered by Talaska and Williams, are a special case of this result. This is an extended abstract for a longer paper, which may be found at arXiv:1411.2997 [math.CO].

Background

Notation

Let S n denote the symmetric group in n letters, with simple generators s 1 , . . . , s n-1 , and let denote the standard length function on S n . For u, w ∈ S n , we write u ≤ w to denote a relation in the (strong

) Bruhat order. A factorization u = vw ∈ S n is length additive if (u) = (v) + (w). We write [a] for the set of integers {1, . . . , a}. If a < b, let [a, b] = {a, a + 1, . . . , b}. Otherwise, let [a, b] = ∅. Let w([a]) be the set {w(1), . . . , w(a)}. By S k × S n-k , we mean the subgroup of S n which fixes the sets [k] and [k + 1, n].
We denote the set of all k-elements subsets of n by [n] k . All functions and permutations act on the left. For a ≤ b, we let x (a,b) (t) denote the elementary matrix with 1's along the main diagonal, a single nonzero entry t in position (a, b), and 0's everywhere else. Let

x i (t) denote x (i,i+1) (t).

Bruhat intervals and bounded affine permutations

Fix k ≤ n. The k-Bruhat order on S n , introduced by Bergeron and Sottile in [START_REF] Bergeron | Schubert polynomials, the Bruhat order, and the geometry of flag manifolds[END_REF], is defined as follows. For u, w ∈ S n , we say that w is a k-cover of u, written w k u, if w u in Bruhat order and w([k]) = u([k]). To obtain the k-Bruhat order on S n , we take the transitive closure of these cover relations. We use ≤ k to denote k-Bruhat order, and write [u, w]

k for the interval {v | u ≤ k v ≤ k w}.
Following (Knutson et al., 2013, Section 2.3), we define an equivalence relation on k-Bruhat intervals by setting [u, w] k ∼ [x, y] k if there is some z ∈ S k × S n-k such that x = uz and y = wz, with both factorizations length additive. We write u, w k for the equivalence class of [u, w] k , and denote the set of all such classes by Q(k, n). There is a partial order on Q(k, n), defined by setting u,

w k ≤ x, y k if there exist representatives [u , w ] k of u, w k and [x , y ] k of x, y k with [x , y ] k ⊆ [u , w ] k . The poset Q(k, n) is anti-isomorphic to
a special case of the posets that appeared in [START_REF] Brown | Poisson structures on affine spaces and flag varieties. I. Matrix affine Poisson space[END_REF] and [START_REF] Rietsch | Closure relations for totally nonnegative cells in G/P[END_REF].

Definition 2.1. A bounded affine permutation of type (k, n) is a bijection f : Z → Z which satisfies the following criteria: 1. f (i + n) = f (i) + n for all i ∈ Z. 2. i ≤ f (i) ≤ i + n for all i ∈ Z. 3. 1 n k i=1 (f (i) -i) = k
We write Bound(k, n) for the set of bounded affine permutations of type (k, n). Let t (i,j) : Z → Z be the map which interchanges i + rn and j + rn for all r ∈ Z. The Bruhat ordering on Bound(k, n) is the transitive closure of the relations given by f → g if f, g ∈ Bound(k, n) and there exists i < j ∈ Z such that f (i) < f (j) and g = f t (i,j) . The poset Bound(k, n) is anti-isomorphic to Postnikov's poset of decorated permutations. For further discussion, see [START_REF] Knutson | Positroid varieties: juggling and geometry[END_REF].

For J ∈ [n] k , define t J ∈ Bound(k, n) by setting

i → i + n i ∈ J i i ∈ [n]\J (2.1)
and extending periodically. Let u, w k ∈ Q(k, n). The function et al., 2013, Section 3.4). Essentially the same isomorphism appears in [START_REF] Williams | Shelling totally nonnegative flag varieties[END_REF].

f u,w = ut [k] w -1 (2.2) lies in Bound(k, n). The map u, w k → f u,w gives a well-defined isomorphism of posets from Q(k, n) to Bound(k, n) (Knutson

Grassmannians, flag varieties, and Richardson varieties

Let Gr(k, n) denote the Grassmannian of k-dimensional linear subspaces of the vector space C n . We realize Gr(k, n) as the space of full-rank k × n matrices modulo row operations; a matrix M represents the space spanned by its rows. We number the rows of our matrices from top to bottom, and the columns from left to right. The Plücker embedding, denoted p, maps Gr(k, n) into the projective space P ( n k )-1 (C) with homogeneous coordinates x J indexed by elements of [n] k . For J ∈ [n] k , and M a k × n matrix, let ∆ J (M ) denote the minor of M with columns indexed by J. Let V be a k-dimensional subspace of C n with representative matrix M . Then p(V ) is the point defined by x J = ∆ J (M ). The homogeneous coordinates ∆ J are known as Plücker coordinates on Gr(k, n). The totally nonnegative Grassmannian Gr ≥0 (k, n) is the subset of Gr(k, n) whose Plücker coordinates are all nonnegative real numbers, up to multiplication by a common scalar.

The flag variety F (n) is an algebraic variety whose points correspond to flags

V • = {0 ⊂ V 1 ⊂ V 2 ⊂ • • • ⊂ V n = C n } (2.3)
where V i is a linear subspace of C n of dimension i. We realize F (n) as the quotient of GL(n) by the left action of B, the group of n × n lower triangular matrices. The projection π k :

F (n) → Gr(k, n) carries a flag V • to the k-plane V k .
We recall the definitions of Schubert and Richardson varieties, following the conventions of (Knutson et al., 2013, Section 4). For a subset J of [n], let Project J : C n → C J be projection onto the coordinates indexed by J. For a permutation w ∈ S n , we define the Schubert cell corresponding to w by

Xw = {V • ∈ F (n) | dim(Project [j] (V i )) = |w([i]) ∩ [j]| for all i} (2.4)
Similarly, we define the opposite Schubert cell by

Xw = {V • ∈ F (n) | dim(Project [n-j+1,n] (V i )) = |w([i]) ∩ [n -j + 1, n]| for all i} (2.5)
We define the open Richardson variety Xw u to be the transverse intersection Xu ∩ Xw . The variety Xw u is empty unless u ≤ w, in which case it has dimension (w) -(u) [START_REF] Kazhdan | Schubert varieties and Poincaré duality[END_REF]. Open Richardson varieties form a stratification of F (n) which refines the Schubert stratification.

Positroid varieties

Let V ∈ Gr ≥0 (k, n). The indices of the non-vanishing Plücker coordinates of V give a set J ⊆ [n] k called the matroid of V . We define the matroid cell M J as the locus of points V ∈ Gr ≥0 (k, n) with matroid J . The nonempty matroid cells in Gr ≥0 (k, n) are the positroid cells defined by Postnikov.

Positroid cells form a stratification of Gr ≥0 (k, n), and each cell is homeomorphic to (R + ) d for some d (Postnikov, 2006, Theorem 3.5).

The positroid stratification of Gr ≥0 (k, n) extends to the complex Grassmannian Gr(k, n). Taking the Zariski closure of a positroid cell of Gr ≥0 (k, n) in Gr(k, n) gives a closed positroid variety. For a closed positroid variety Π ⊆ Gr(k, n), we define the open positroid variety Π ⊂ Π by taking the complement in Π of all lower-dimensional positroid varieties. These open positroid varieties give a stratification of Gr(k, n) [START_REF] Rietsch | An algebraic cell decomposition on the nonnegative part of a flag variety[END_REF][START_REF] Knutson | Positroid varieties: juggling and geometry[END_REF]. Positroid varieties in Gr(k, n) may be defined in numerous other ways. For instance, there is is a beautiful description of positroid varieties as intersections of cyclically permuted Schubert varieties [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF][START_REF] Knutson | Positroid varieties: juggling and geometry[END_REF].

Positroid varieties in Gr(k, n) coincide with projected Richard varieties (Knutson et al., 2013, Section 5.4). Indeed, let u ≤ k w. The projection π k maps Xw u isomorphically onto its image, which is an open positroid variety Πu,w . If u , w k = u, w k then Πu,w = Πu ,w , so each class in u, w k ∈ Q(k, n) corresponds to a unique positroid variety. This correspondence gives a poset isomorphism between Q(k, n) and the poset of positroid varieties, ordered by reverse inclusion (Knutson et al., 2013, Section 5.4).

Since Q(k, n) is isomorphic to the poset of positroid varieties, so is Bound(k, n). We write Π f for the positroid variety corresponding to a bounded affine permutation f . There are numerous other combinatorial objects that index positroid varieties; see [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF][START_REF] Knutson | Positroid varieties: juggling and geometry[END_REF].

Plabic graphs and bridge graphs

A plabic graph is a planar graph embedded in a disk, with each vertex colored black or white. (Plabic is short for "planar bicolored.") The boundary vertices are numbered 1, 2, . . . , n in clockwise order, and all boundary vertices have degree one. We call the edges adjacent to boundary vertices legs of the graph, and a leaf adjacent to a boundary vertex a lollipop.

Postnikov introduced plabic graphs in (Postnikov, 2006, Section 11.5), where he used them to construct parametrizations of positroid cells in the totally nonnegative Grassmannian. In this paper, we follow the more restrictive conventions of [START_REF] Postnikov | Matching polytopes, toric geometry, and the totally nonnegative Grassmannian[END_REF]. In particular, we require our plabic graphs to be bipartite, with the black and white vertices forming the partite sets. Further, we restrict our attention to reduced, perfectly orientable plabic graphs, which satisfy some additional combinatorial conditions. See (Postnikov, 2006, Section 12).

Postnikov associates a decorated permutation σ G to each plabic graph G with n boundary vertices; that is, a permutation with each fixed point colored black or white. If G is a reduced graph, each fixed point of σ G corresponds to a boundary leaf [START_REF] Postnikov | Total positivity, Grassmannians and networks[END_REF]. Let

k = |{a ∈ [n] | σ G (a) < a or σ G (a) = a and G has a white boundary leaf at a}| (2.6)
Then there is a unique son et al., 2013). Thus we have a correspondence between plabic graphs and positroid varieties, with Π G = Π f G , which assigns a family of reduced plabic graphs to each positroid variety. We describe a way to build plabic graphs inductively by adding new edges, called bridges. The resulting graphs are called bridge graphs. Versions of this construction appear in [START_REF] Arkani-Hamed | Scattering amplitudes and the positive Grassmannian[END_REF] and (Lam, 2013b).

f G ∈ Bound(k, n) corresponding to G such that f G (i) ≡ σ G (i) (mod n) (Knut
Begin with a plabic graph G. To add a bridge, we choose a pair of boundary vertices a < b such every

c ∈ [a + 1, b -1] is a lollipop, and f G (a) > f G (b).
Our new edge has one vertex on the leg at a, and one on the leg at b. If a (respectively b) is a lollipop, then the leaf at a must be white (black), and we use that boundary leaf as one endpoint of the bridge. If a (respectively b) is not a lollipop, we instead insert a white (black) vertex in the middle of the leg at a (respectively, b). After adding the bridge, we insert additional vertices of degree two or change the color of boundary vertices as needed to obtain a bipartite graph. (See Figure 2.) The following is straightforward. The zero-dimensional positroid varieties correspond to the points in Gr(k, n) which have a single nonzero Plücker coordinate J. There is a unique reduced plabic graph for each J ∈ [n] k , which has n lollipops. The k lollipops corresponding to elements of J are white; the rest are black. We call a plabic graph consisting only of lollipops a lollipop graph.

Proposition 2.2. Suppose G is reduced. Choose 1 ≤ a < b ≤ n such that f G (a) > f G (b),
Let u ≤ k w. Then by (2.2), together with the fact that ut

[k] = t u([k]) u, we have f u,w = t u([k]) uw -1
To construct a bridge graph for Π u,w k we begin with the lollipop graph corresponding to u([k]), and successively add bridges, making sure the hypotheses of Proposition 2.2 are satisfied at each step, until we have a graph with bounded affine permutation f u,w .

Parametrizations from plabic graphs

Let G be a reduced plabic network with e edges, and assign weights t 1 , . . . , t e to the edges of G. Postnikov defined a surjective map from the space of positive real edge weights of G to the positroid cell ΠG ≥0 in Gr ≥0 (k, n), called the boundary measurement map (Postnikov, 2006, Section 11.5). Postnikov, Speyer and Williams re-cast this construction in terms of certain matchings (Postnikov et al., 2009, Section 4-5), an approach Lam developed further in (Lam, 2013b). Muller and Speyer showed that we can extend the boundary measurement map to the space of nonzero complex edge weights, and obtain a regular map; specializing all but an appropriate set of edges to 1 gives a birational map to a dense subset of ΠG [START_REF] Muller | The twist for positroid varieties[END_REF]. If G is a bridge graph, we have a simple procedure for constructing such a parametrization.

Note that for a bridge graph G, we have Π G = Π u,w for some u ≤ k w. Let d = dim(Π G ). Assign weights t 1 , . . . , t d to each bridge, in the order the bridges were added, and set all other edge weights to 1. Begin with a k × n matrix which has a single nonzero Plücker coordinate indexed by the columns u([k]), and whose remaining columns consist of all 0's. Say the r th bridge is from a to b, with a < b, and let

θ = |u([k]) ∩ [a + 1, b -1]|
When we add the r th bridge to the graph, we multiply our matrix on the right by x (a,b) ((-1) θ t r )

Example

Let n = 4, k = 2. Let w = 4321 and u = 2143. Then u ≤ 2 w, and u, w 2 corresponds to the big cell in Gr(2, 4). We have u([2]) = {1, 2}. The bounded affine permutation corresponding to u, w 2 is given by f u,w = 3456. Starting with the plabic graph corresponding to t u([2]) = 5634 we successively add bridges

(1, 4) → (2, 4) → (2, 3) → (1, 2).
(2.7)

The corresponding bridge graph is shown in Figure 1.

We next construct the corresponding matrix parametrization. Since u([2]) = {1, 2}, we start with the k × n matrix which has a copy of the identity in its first two columns, and multiply on the right by the factors x (a,b) (±t r ) as in (2.6). So we have

1 0 0 0 0 1 0 0     1 0 0 -t 1 0 1 0 0 0 0 1 0 0 0 0 1         1 0 0 0 0 1 0 t 2 0 0 1 0 0 0 0 1         1 0 0 0 0 1 t 3 0 0 0 1 0 0 0 0 1         1 t 4 0 0 0 1 0 0 0 0 1 0 0 0 0 1     = 1 t 4 0 -t 1 0 1 t 3 t 2
(2.8)

Positive distinguished subexpressions

Let w = s i1 • • • s im be a reduced word for w ∈ S n . A subexpression u of w is obtained by replacing some of the factors s ij of w with the identity permutation, which we denote by 1. Following [START_REF] Marsh | Parametrizations of flag varieties[END_REF], we write u w to indicate that u is a subexpression of w. We denote the t th factor of u, which may be either 1 or a simple transposition, by u t , and write u (t) for the product u 1 u 2 . . . u t . Set

u 0 = u (0) = 1.
Given a subexpression u w, we say u is a subexpression for

u = u 1 u 2 • • • u r .
Definition 2.3. A subexpression u of w is called positive distinguished if for all 1 ≤ j ≤ m, we have u (j-1) < u (j-1) s ij .

(2.9)

We will abbreviate the phrase "positive distinguished subexpression" to PDS.

Wiring diagrams, subexpressions, and bridge diagrams

Wiring represent words in S n visually. Let w in S n , and fix a word w of w. For an example, see Figure 3b. Each crossing between the wires represents a transposition s i , where i -1 is the number of wires in the diagram which pass directly above the crossing. However, the crossings in the diagram for w appear in the opposite order as the corresponding generators in the word w. If w(s) = t, the wire with left endpoint s has right endpoint t.

We now define bridge diagrams, which represent subexpressions of reduced words. To draw the bridge diagram for a subexpression u w we take a wiring diagram for u, and draw dashed crosses between adjacent wires to represent the additional crossings from w. We call these dashed crosses bridges, by analogy with bridge graphs. For an example, see Figure 3a. If u w is a bridge diagram, we label wires in the underlying diagram for u by their right endpoints. A wire is isolated if there are no bridges on that wire.

Deodhar parametrizations of positroid varieties

We review Deodhar's decompositions of the flag variety, as well as Marsh and Rietsch's parametrizations of Deodhar components, and their projections to the Grassmannian [START_REF] Deodhar | On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells[END_REF][START_REF] Marsh | Parametrizations of flag varieties[END_REF]. Our discussion follows (Talaska and Williams, 2013, Section 4), but with slightly different conventions.

To construct a Deodhar decomposition of F (n), we first fix a reduced word w for each w ∈ S n . We have a Deodhar component R u,w for each distinguished subexpression u w with

Xw u = u w distinguished R u,w .
(2.10)

To define a Deodhar decomposition of the Grassmannian, fix a Deodhar decomposition of F (n), and choose a representative u, w k for each class in Q(k, n). For each of the selected u ≤ k w, and each distinguished subexpression u w, the Deodhar component of Gr(k, n) corresponding to u w is given by D u,w := π k (R u,w ).

We give the explicit matrix parametrization for D u,w in the case where u w is a PDS. We write ṡi for the matrix obtained from the n × n identity by replacing the 2 × 2 block whose upper left corner is at position (i, i) with the block matrix 0

-1 1 0 (2.11) Let w = s i1 • • • s im . Then we define g j for 1 ≤ i ≤ m by g j = x ij (t j ) if s ij is not in u ṡ ij -1 if s ij is in u (2.12)
where the t j are parameters, and define the set [START_REF] Marsh | Parametrizations of flag varieties[END_REF]. Composing with π k , we have a parametrization of D u,w . Let j 1 , . . . , j d be the indices j

G u,w := {g m g m-1 . . . g 1 ∈ GL(n) | t j ∈ C × }. (2.13) Let d = (w) -(u). The obvious map (C × ) d → G u,w gives a parametrization of R u,w
such that s ij ∈ For 1 ≤ r ≤ d, set r = d + 1 -r and define a r = u (jr-1) (i jr ) b r = u (jr-1) (i jr + 1) θ r = |u([k]) ∩ [a r + 1, b r -1])| (2.14)
β r = x (ar,br) ((-1) θr t jr ).

(2.15)

Using the properties of PDS's and the commutation relations between the matrices ṡi and x (a,b) , we may write each G ∈ G u,w in the form

G = ( u-1 m u-1 2 • • • u-1 1 )(β 1 β 2 • • • β d ).
(2.16)

For convenience, we renumber our parameters so that β r = x (ar,br) ((-1) θr t r ).

Example continued

As before, let n = 4, k = 2. Let w = s 1 s 2 s 3 s 2 s 1 s 2 ∈ S 4 , and let u = 2143. The PDS u for u in w is comprised of the generators in bold, so we have a parametrization of R u,w by

G = x 2 (t 1 ) ṡ1 -1 x 2 (t 2 ) ṡ3 -1 x 2 (t 3 )x 1 (t 4 ).
(2.17)

Rewriting this in the form (2.16) and projecting to Gr(2, 4), we obtain

1 0 0 0 0 1 0 0 ṡ1 -1 ṡ3 -1 x (1,4) (-t 1 )x (2,4) (t 2 )x 2 (t 3 )x 1 (t 4 ) = 0 1 t 3 t 2 -1 -t 4 0 t 1 (2.18)
Note that this matrix has the same row span as the one obtained from the bridge graph above.

Sketch of the main proof

We sketch the proof of the forward direction of Theorem 1.1: every Deodhar parametrization corresponds to a bridge graph. The reverse direction also has a constructive proof, but the procedure is less visually elegant. Let u w be a PDS with u ≤ k w. We construct a bridge graph G from the bridge diagram u w, as follows. For an example, see Figure 3.

Think of the right endpoints of the wires as boundary vertices of a bicolored graph embedded in a disk; the wires as paths with one endpoint on the boundary; and the new crossings as white-black bridges between these paths. Erase the tail of each wire from the left endpoint to the first bridge on that wire. If wire t is isolated, add a black lollipop at t if u -1 (t) > k, and a white lollipop if u -1 (t) ≤ k. Finally, color the boundary vertices and add degree-two vertices as needed to obtain a bipartite graph. Remarkably, this process yields a planar embedding of a plabic graph whenever u w is a PDS with u ≤ k w. Proving this requires a careful analysis of the possible configurations of bridge diagrams, using the properties of k-Bruhat order.

The parametrization arising from G is precisely the projected Deodhar parametrization corresponding to u w. Indeed, we construct the parametrization corresponding to G by taking a k × n matrix which has a single non-zero Plücker coordinate u([k]), and multiplying on the right by the matrices β 1 , . . . , β d , where the β r are defined as in (2.9). To see this, note that in the diagram, the r th bridge from the left lies between wires a r and b r in the diagram for u, where (a r , b r ) is as in (2.14).

  into open positroid varieties Π whose intersections with Gr ≥0 (k, n) are precisely Postnikov's totally nonnegative cells Π≥0 . Remarkably, open positroid varieties are the images of open Richardson varieties in the flag variety F (n) under the natural projection π k : F (n) → Gr(k, n).

  and each c ∈ [a + 1, b -1] is a lollipop. Let G be the graph obtained by adding an (a, b)-bridge to G. Then G is a reduced plabic graph, and f G = f • (a, b) ∈ Bound(k, n).

  Adding a bridge between legs which are not boundary leaves. Note that after adding the bridge, we add additional vertices of degree 2 to create a bipartite graph.

Fig. 2 :

 2 Fig. 2: Adding bridges to a plabic graph.

  Replacing each bridge at left with a crossing gives the wiring diagram for w. To construct the bridge graph corresponding to u w, we first replace each bridge with a dimer, as shown above.

  Next, we delete the tail of each wire up to the first dimer on that wire. Adding degree-2 vertices as needed yields the desired plabic graph.

Fig. 3 :

 3 Fig. 3: Constructing a bridge graph from a bridge diagram. In this example, we have k = 2, n = 4, w = s 1 s 2 s 3 s 2 s 1 s 2 , and u = s 3 s 1 . Compare the figure at lower right with the bridge graph in Figure 1.

Résumé. Soit Π une variété positroïde. Nous appellerons paramétrisation toute application régulière (C ×d ) → Π qui est un isomorphisme birégulier sur un sous-ensemble dense de Π. On sait que plusieurs constructions combinatoires donnent des paramétrisations intéressantes. Le but du présent article est d'investiguer deux familles de telles paramétrisations et de montrer, essentiellement, qu'elles coïncident. La première famille trouve son origine dans la fonction de mesure des bords de Postnikov. Le domaine de chaque paramétrisation est en ce cas-ci l'ensemble de poids des arêtes d'un réseau planaire pondéré. Nous nous concentrons sur une classe particulière de réseaux planaires, les graphes de ponts, ayant des applications à la physique subatomique. La deuxième famille provient des paramétrisations de Marsh et de Rietsch des composantes de Deodhar (indexées par certaines sous-expressions de mots réduits de permutations) de la variété de drapeaux. On obtient alors des paramétrisations de cellules de positroïdes en appliquant la projection à la grassmannienne. Nous montrons que chaque paramétrisation de Deodhar corresponde à un graphe de ponts; d'autre part, chaque paramétrisation provenant d'un graphe de ponts s'accorde avec quelque paramétrisation de Deodhar.

Acknowledgements

I would like to thank Thomas Lam for introducing me to his conjecture about the relationship between bridge graphs and Deodhar parametrizations, and for many helpful conversations. My thanks also to Greg Muller and David E Speyer, for sharing their manuscript (Muller and Speyer, 2014). I am grateful to Greg Muller, David E Speyer and Timothy M. Olson for productive discussions, and to Jake Levinson for the French translation of the abstract.

This research was supported by NSF grant number DGE 1256260. 1365-8050


Yue Cai
email: yue.cai@uky.edu.

Margaret Readdy
email: readdy@ms.uky.edu.

Negative q-Stirling numbers

Keywords: q-analogues, discrete Morse Theory, poset decomposition, algebraic complex, homology, orthogonality

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The idea of q-analogues can be traced back to Euler in the 1700's who was studying q-series, especially specializations of theta functions. The Gaussian polynomial is given by n k q =

[n]q!

[k]q![n-k]q! , where

[n] q = 1 + q + • • • + q n-1 and [n] q ! = [1] q • [2] q • • • [n] q .
A combinatorial interpretation due to MacMahon in 1916 [START_REF] Macmahon | Two applications of general theorems in combinatory analysis[END_REF]Page 315] is π∈S(0 n-k ,1 k ) q inv(π) = n k q . Here S(0 n-k , 1 k ) denotes the number of 0-1 bit strings consisting of n -k zeroes and k ones, and for π = π 1 • • • π n ∈ S(0 n-k , 1 k ) the number of inversions is inv(π) = |{(i, j) : i < j and π i > π j }|. The inversion statistic goes back to work of Cramer (1750), Bézout (1764) and Laplace (1772). See the discussion in [START_REF] Netto | Lehrbuch der Combinatorik[END_REF]Page 92]. Netto enumerated the elements of the symmetric group by the inversion statistic in 1901 [START_REF] Netto | Lehrbuch der Combinatorik[END_REF]Chapter 4,Sections 54,57], and in 1916 MacMahon [START_REF] Macmahon | Two applications of general theorems in combinatory analysis[END_REF]Page 318] gave the q-factorial expansion π∈Sn q inv(π) = [n] q !.

The notion of the negative q-binomial has been recently introduced by Fu, Reiner, Stanton and Thiem [START_REF] Fu | The negative q-binomial[END_REF]. It is defined by substituting -q for q in the Gaussian coefficient and adjusting the sign: n k q = (-1) k(n-k) • n k -q . The negative q-binomial enjoys properties similar to that of the q-binomial: (i) it can be expressed as a generalized inversion number of a subset Ω(n, k) of 0-1 bit strings in S(0 n-k , 1 k ):

n k q = ω∈Ω(n,k)
q a(ω) • (q -1) p(ω) , (

for statistics a(ω) and p(ω) [5, Theorem 1], (ii) it counts a certain subset of the k-dimensional subspaces of F n q [5, Section 6.2], (iii) it reveals a representation theory connection with unitary subspaces and a two-variable version exhibits a cyclic sieving phenomenon [START_REF] Fu | The negative q-binomial[END_REF]Sections 4,[START_REF] Fu | The negative q-binomial[END_REF].

An important consequence of (1.1) is the classical Gaussian polynomial can be expressed as sum over a subset of 0-1 bit strings in terms of powers of q and 1 + q using the same statistics:

n k q = ω∈Ω(n,k) q a(ω) • (1 + q) p(ω) . (1.2)
It is from this result that we springboard our work. More precisely,

Goal 1.1 Given a q-analogue f (q) = w∈S q σ(w) ,
for some statistic σ(•), find a subset T ⊆ S and statistics A(•) and B(•) so that the q-analogue may be expressed as

f (q) = w∈T q A(w) • (1 + q) B(w) .
The overall goal is not only to discover more compact encodings of classical q-analogues, but to also understand them via enumerative, poset theoretic and topological viewpoints. In this paper we do exactly this for the q-Stirling numbers of the first and second kinds.

RG-words

Recall a set partition on the n elements {1, 2, . . . , n} is a decomposition of this set into mutually disjoint nonempty sets called blocks. Unless otherwise indicated, throughout all set partitions will be written in standard form, that is, a partition into k blocks will be denoted by

π = B 1 /B 2 / • • • /B k ,
where the blocks are ordered so that min(B 1 )

< • • • < min(B k ).
We denote the set of all partitions of {1, . . . , n} by Π n . Given a partition π ∈ Π n , we encode it using a restricted growth word w(π) = w 1 • • • w n , where w i = j if the element i occurs in the jth block B j of π. For example, the partition π = 14/236/57 has RG-word w = w(π) = 1221323. Restricted growth words are also known as restricted growth functions. They have been studied by Hutchinson [9] and Milne [START_REF] Milne | Restricted growth functions and incidence relations of the lattice of partitions of an n-set[END_REF][START_REF] Milne | A q-analog of restricted growth functions, Dobinski's equality, and Charlier polynomials[END_REF].

Two facts about RG-words follow immediately from using the standard form for set partitions.

Proposition 2.1 The following properties are satisfied by RG-words:

1. Any RG-word begins with the element 1.

2. For an RG-word ω let (j) be the smallest index such that ω (j) = j. Then (1)

< (2) < • • • .
The q-Stirling numbers of the second kind are defined by

S q [n, k] = S q [n -1, k -1] + [k] q • S q [n -1, k], for 1 ≤ k ≤ n, (2.1)
with boundary conditions S q [n, 0] = δ n,0 and S q [0, k] = δ 0,k , where δ i,j is the usual Kronecker delta function. Setting q = 1 gives the familiar Stirling number of the second kind S(n, k) which enumerates the number of partitions π ∈ Π n with exactly k blocks. There is a long history of studying set partition statistics [START_REF] Garsia | Q-counting rook configurations and a formula of Frobenius[END_REF][START_REF] Leroux | Reduced matrices and q-log-concavity properties of q-Stirling Numbers[END_REF][START_REF] Rota | The number of partitions of a set[END_REF]] and q-Stirling numbers [START_REF] Carlitz | On abelian fields[END_REF][START_REF] Readdy | A user's Morse theory[END_REF][START_REF] Gould | The q-Stirling numbers of the first and second kinds[END_REF][START_REF] Milne | A q-analog of restricted growth functions, Dobinski's equality, and Charlier polynomials[END_REF][START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF]. We begin by presenting a new statistic on RG-words which generate the q-Stirling numbers of the second kind. Let R(n, k) denote the set of all RG-words of length n with maximum letter k. For w ∈ R(n, k), let m i = max(w 1 , . . . , w i ). Form the weight wt(w) = n i=1 wt i (w) where wt 1 (w) = 1 and for 2 ≤ i ≤ n, let

wt i (w) = q wi-1 if m i-1 ≥ w i , 1 if m i-1 < w i . (2.2)
For example, wt(1221323

) = 1 • 1 • q 1 • q 0 • 1 • q 1 • q 2 = q 4 .
In terms of set partitions, the weight of 1) . Lemma 2.2 The q-Stirling number of the second kind is given by

π = B 1 /B 2 / • • • /B k is wt(π) = n j=1 q (j-1)•(|Bj |-
S q [n, k] = w∈R(n,k)
wt(w).

Allowable RG-words

Mirroring the negative q-binomial, in this section we define a subset of RG-words and two statistics A(•) and B(•) which generate the classical q-Stirling number of the second kind as a polynomial in q and 1 + q. We will see in Sections 4 through 6 that this has poset and topological implications. Definition 3.1 An RG-word w ∈ R(n, k) is allowable if every even entry appears exactly once. Denote by A(n, k) the set of all allowable RG-words in R(n, k).

Another way to state that w ∈ R(n, k) is an allowable RG-word is that it is an initial segment of the infinite word

w = u 1 • 2 • u 3 • 4 • u 5 • • •
, where u 2i-1 is a word on the alphabet of odd integers {1, 3, . . . , 2i -1}. In terms of set partitions, an RG-word is allowable if in the corresponding set partition every even indexed block is a singleton block.

For an RG-word w = w 1 • • • w n , let m i = max(w 1 , . . . , w i ). Define wt (w) = n i=1 wt i (w), where

wt i (w) =    q wi-1 • (1 + q) if m i-1 > w i , q wi-1 if m i-1 = w i , 1 if m i-1 < w i or i = 1. (3.1)
We decompose this weight statistic wt into two statistics on RG-words. Let

A i (w) = w i -1 if m i-1 ≥ w i , 0 if m i-1 < w i or i = 1, and
B i (w) = 1 if m i-1 > w i , 0 otherwise. (3.2) Define A(w) = n i=1 A i (w) and B(w) = n i=1 B i (w).
Theorem 3.2 The q-Stirling numbers of the second kind can be expressed as a weighting over the set of allowable RG-words as follows:

S q [n, k] = w∈A(n,k) wt (w) = w∈A(n,k) q A(w) • (1 + q) B(w) . (3.3) Proposition 3.3
The number of allowable words satisfies the recurrence

|A(n, k)| = |A(n -1, k -1)| + k/2 • |A(n -1, k)| for n ≥ 1 and 1 ≤ k ≤ n, with the boundary conditions |A(n, 0)| = δ n,0 .
Topological implications of Theorem 3.2 will be discussed in Section 6.

The Stirling poset of the second kind

In order to understand the q-Stirling numbers more deeply, we give a poset structure on R(n, k), which we call the Stirling poset of the second kind, denoted by

Π(n, k), as follows. For v, w ∈ R(n, k) let v = v 1 v 2 • • • v n ≺ w if w = v 1 v 2 • • • (v i + 1) • • • v n for some index i. It is clear that if v ≺ w then wt(w) = q • wt(v)
, where the weight is as defined in (2.2). The Stirling poset of the second kind is graded by the degree of the weight wt. Thus the rank of the poset Π(n, k) is (n -k)(k -1) and its rank generating function is given by S q [n, k]. For basic terminology regarding posets, we refer the reader to Stanley's treatise [START_REF] Stanley | Enumerative Combinatorics[END_REF]Chapter 3]. See Figure 1 for an example of the Stirling poset of the second kind.

We next review the notion of a Morse matching [START_REF] Kozlov | Combinatorial Algebraic Topology[END_REF]. This will enable us to find a natural decomposition of the Stirling poset of the second kind, and to later be able to draw homological conclusions. A partial matching on a poset P is a matching on the underlying graph of the Hasse diagram of P , that is, a subset M ⊆ P × P satisfying (i) the ordered pair (a, b) ∈ M implies a ≺ b, and (ii) each element a ∈ P belongs to at most one element in M . When (a, b) ∈ M , we write u(a) = b and d(b) = a. A partial matching on P is acyclic if there does not exist a cycle

a 1 ≺ u(a 1 ) a 2 ≺ u(a 2 ) • • • a n ≺ u(a n ) a 1
with n ≥ 2, and the elements a 1 , a 2 , . . . , a n distinct.

We define a matching M on the Stirling poset Π(n, k) in the following manner. Let w i be the first entry

in w = w 1 w 2 • • • w n ∈ R(n, k) such that w is weakly decreasing, that is, w 1 ≤ w 2 ≤ • • • ≤ w i-1 ≥ w i
and where we require the inequality w i-1 ≥ w i to be strict unless both w i-1 and w i are even. We have two subcases. If

w i is even then let d(w) = w 1 w 2 • • • w i-1 (w i -1)w i+1 • • • w n . Immediately we have wt(d(w)) = q -1 • wt(w). Otherwise, if w i is odd then let u(w) = w 1 w 2 • • • w i-1 (w i + 1)w i+1 • • • w n
and we have wt(u(w)) = q • wt(w). If w is an allowable word which is weakly increasing, then w is unmatched in the poset. Again, we refer to Figure 1.

w = u 1 • 2 • u 3 • 4 • u 5 • 6 • • • u k-1 • k for k even, u 1 • 2 • u 3 • 4 • u 5 • 6 • • • k -1 • u k for k odd, (4.1)
where u 2i-1 = (2i -1) ji , that is, u 2i-1 is a word consisting of j i ≥ 1 copies of the odd integer 2i -1.

As an example, the unmatched words in Π(5, 3) are 12333, 11233 and 11123, and their total weight is 1 + q 2 + q 4 . See Figure 1. From Lemma 4.2 we have the following result.

Theorem 4.3 The matching M described for Π(n, k) is an acyclic matching, that is, it is a discrete Morse matching.

Decomposition of the Stirling poset

We next decompose the Stirling poset Π(n, k) into Boolean algebras indexed by the allowable words. This gives a poset explanation for the factorization of the q-Stirling number S q [n, k] in terms of powers of q and 1 + q. To state this decomposition, we need two definitions. For w ∈ A(n, k) an allowable word let Inv r (w) = {i : w j > w i for some j < i} be the set of all indices in w that contribute to the right-hand element of an inversion pair. For i ∈ Inv r (w) such an entry w i must be odd since in a given allowable word any entry occurring to the left of an even entry must be strictly less than it.

= 1 + 2(1 + q) + 3(1 + q) 2 + q 2 + 3q 2 (1 + q) + q 4 .
w ∈ A(n, k) let α(w) be the word formed by incrementing each of the entries indexed by the set Inv r (w) by one. Additionally, for w ∈ A(n, k) and any I ⊆ r (w), the word formed by incrementing each of the entries indexed by the set I by one are elements of R(n, k) since if i ∈ Inv r (w) then there is an index h < i with w h = w i . This follows from Proposition 2.1 part (ii). Furthermore, if an allowable word w ∈ A(n, k) has weight wt (w) = q i • (1 + q) j , then the rank of the element w is i and the interval [w, α(w)] is isomorphic to the Boolean algebra on j elements.

See Figure 2 for an example of this decomposition.

6 Homological q = -1 phenomenon Stembridge's q = -1 phenomenon [START_REF] Stembridge | Some hidden relations involving the ten symmetry classes of plane partitions[END_REF][START_REF] Stembridge | Canonical bases and self-evacuating tableaux[END_REF], and the more general cyclic sieving phenomenon of Reiner, Stanton and White [START_REF] Reiner | The cyclic sieving phenomenon[END_REF] counts symmetry classes in combinatorial objects by evaluating their q-generating series at a primitive root of unity. Recently Hersh, Shareshian and Stanton [START_REF] Hersh | The q = -1 phenomenon via homology concentration[END_REF] have given a homological interpretation of the q = -1 phenomenon by viewing it as an Euler characteristic computation on a chain complex supported by a poset. In the best scenario, the homology is concentrated in dimensions of the same parity and one can identify a homology basis. For further information about algebraic discrete Morse theory, see [START_REF] Welker | Minimal resolutions via algebraic discrete Morse theory[END_REF][START_REF] Kozlov | Discrete Morse theory for free chain complexes[END_REF][START_REF] Öldberg | Morse theory from an algebraic viewpoint[END_REF].

We will see the graded poset Π(n, k) supports an algebraic complex (C, The aforementioned matching for k) (Theorem 4.3) is a Morse matching for this complex. Hence using standard discrete Morse theory [4], we can give a basis for the homology.

We now review the relevant background. We follow [START_REF] Hersh | The q = -1 phenomenon via homology concentration[END_REF] here. See also [START_REF] Welker | Minimal resolutions via algebraic discrete Morse theory[END_REF][START_REF] Öldberg | Morse theory from an algebraic viewpoint[END_REF]. Let P be a graded poset and W i denote the rank i elements. We say the poset P supports a chain complex (C, ∂) of F-vector spaces C i if each C i has basis indexed by the rank i elements W i and ∂ i : W i → W i-1 is a boundary map. Furthermore, for x ∈ W i and y ∈ W i-1 the coefficient ∂ x,y of y in ∂ i (x) is zero unless y < P x.

For w ∈ Π(n, k), let E(w) = {i : w i is even and w j = w i for some j < i} be the set of all indices of repeated even entries in the word w. Define the boundary map ∂ on the elements of Π(n, k) by

∂(w) = r j=1 (-1) j-1 • w 1 • • • w ij -1 • (w ij -1) • w ij +1 • • • w n , where E(w) = {i 1 < i 2 < • • • < i r }.
(n, k) in Π(n, k) is given by the q 2 -binomial coefficient u∈U (n,k) wt(u) = n -1 -k 2 k-1 2 q 2 .
Notice that when we substitute q 2 = 1, the q 2 -binomial coefficient reduces to the number of unmatched words.

We will need a lemma due to Hersh, Shareshian and Stanton [START_REF] Hersh | The q = -1 phenomenon via homology concentration[END_REF]Lemma 3.2]. This is part (ii) of the original statement of the lemma. Lemma 6.3 (Hersh-Shareshian-Stanton) Let P be a graded poset supporting an algebraic complex (C, ∂) and assume P has a Morse matching M such that for all matched pair(y, x) with y < x, one has ∂ x,y ∈ F * . If all unmatched poset elements occur in ranks of the same parity, then dim(H i (C, d)) = |P unM i |, that is, the number of unmatched elements of rank i. Theorem 6.4 For the algebraic complex (C, ∂) supported by the Stirling poset Π(n, k), a basis for the integer homology is given by the increasing allowable RG-words in A(n, k). Furthermore, we have

i≥0 dim(H i (C, ∂; Z)) • q i = n -1 -k 2 k-1 2 q 2 .
7 q-Stirling numbers of the first kind: Combinatorial interpretation

The (unsigned) q-Stirling number of the first kind is defined by the recurrence formula

c q [n, k] = c q [n -1, k -1] + [n -1] q • c q [n -1, k], (7.1)
where c q [n, 0] = δ n,0 and [m] q = 1 + q + • • • + q m-1 . When q = 1, the Stirling number of the first kind c(n, k) enumerates permutations in the symmetric group S n having exactly k disjoint cycles. A combinatorial way to express q-Stirling numbers of the first kind is via rook placements; see de Médicis and Leroux [START_REF] De | A unified combinatorial approach for q-(and p, q-) Stirling numbers[END_REF]. Throughout a staircase chessboard of length m is a board with m -i squares in the ith row for i = 1, . . . , m -1 and each row of squares is left-justified.

q 2 q 2 (1 + q) (1 + q) 2 (1 + q) (1 + q)
Fig. 3: Computing the q-Stirling number of the first kind cq[4, 2] using Q(4, 2).

Definition 7.1 Let P(m, n) be the set of all ways to place n rooks onto a staircase chessboard of length m so that no two rooks are in the same column. For any rook placement T ∈ P(m, n), denote by s(T ) the number of squares to the south of the rooks in T .

Theorem 7.2 (de Médicis-Leroux) The q-Stirling number of the first kind is given by

c q [n, k] = T ∈P(n,n-k)
q s(T ) .

We now define a subset Q(n, n -k) of rook placements in P(n, n -k) so that the q-Stirling number of the first kind c q [n, k] can be expressed as a statistic on the subset involving q and 1 + q. Definition 7.3 Given any staircase chessboard, assign it a chequered pattern such that every other antidiagonal strip of squares is shaded, beginning with the lowest antidiagonal. Let Q(m, n) = {T ∈ P(m, n) : all rooks are placed in shaded squares}. For any T ∈ Q(m, n), let r(T ) denote the number of rooks in T that are not in the first row. For T ∈ Q(m, n), define the weight to be wt(T ) = q s(T ) • (1 + q) r(T ) . Theorem 7.4 The q-Stirling number of the first kind is given by

c q [n, k] = T ∈Q(n,n-k) wt(T ) = T ∈Q(n,n-k) q s(T ) • (1 + q) r(T ) .
See Figure 3 for the computation of c q [4, 2] using allowable rook placements on length 4 shaded staircase boards. When we substitute q = -1 into the q-Stirling number of the first kind, the weight wt(T ) of a rook placement T will be 0 if there is a rook in T that is not in the first row. Hence the Stirling number of the first kind c q [n, k] evaluated at q = -1 counts the number of rook placements in Q(n, n -k) such that all of the rooks occur in the first row. Corollary 7.5 The q-Stirling number of the first kind c q [n, k] evaluated at q = -1 gives the number of rook placements in Q(n, n -k) where all of the rooks occur in the first row, that is,

c q [n, k] q=-1 = n/2 n -k .
8 Structure and topology of Stirling poset of the first kind

We define a poset structure on rook placements on a staircase shape board. For rook placements T and T in P(m, n), let T ≺ T if T can be obtained from T by either moving a rook to the left (west) or up (north) by one square. We call this poset the Stirling poset of the first kind and denote it by Γ(m, n). It is straightforward to check that the poset

Γ(m, n) is graded of rank (m -1) + (m -2) + • • • + (m -n) = m • n -n+1 2
and its rank generating function is c q [m, m -n]. See Figure 4 as an example. We wish to study the topological properties of the Stirling poset of the first kind. To do so, we define a matching M on the poset as follows. Given any rook placement T ∈ Γ(m, n), let r be the first rook (reading from left to right) that is not in a shaded square of the first row. Match T to T where T is obtained from T by moving the rook r one square down if r is not in a shaded square, or one square up if r is in a shaded square but not in the first row. It is straightforward to check that the unmatched rook placements are the ones with all of the rooks occur in the shaded squares of the first row.

As an example, the matching for Γ(4, 2) is shown in Figure 4, where an upward arrow indicates a matching and other edges indicate the remaining cover relations. Observe the unmatched rook placements are the ones with all the rooks occurring in the shaded squares of the first row. By the way a chessboard is shaded, the unmatched rook placements only appear in even ranks in the poset.

We have the q-analogue of Corollary 7.5

Theorem 8.1 For the Stirling poset of the first kind Γ(m, n), the generating function for unmatched rook placements is

T ∈P(m,n) T unmatched wt(T ) = q n(n-1) • m+1 2 n q 2 .
Using a similar gradient path argument as for Π(n, k), we have the following result. Furthermore, if T ∈ Q(m, n) has weight wt(T ) = q i • (1 + q) j , then the rank of the element T is i and the interval [T, α(T )] is isomorphic to the Boolean algebra on j elements.

Given a rook placement T ∈ Γ(m, n), let N (T ) = {r 1 , r 2 , . . . , r s } be the set of all rooks in T that are not in shaded squares, where the rooks r i are labeled from left to right. Then (-1) i-1 • T ri defined on the algebraic complex supported by the Stirling poset of the first kind Γ(m, n), is a boundary map, where T ri is the rook placement obtained by moving the rook r i in T down by one square.

Applying Theorem 8.1, Theorem 8.2 and Lemma 8.4 to Lemma 6.3, we have the following result. Theorem 8.5 For the algebraic complex (C, ∂) supported by the Stirling poset of the first kind Γ(m, n), a basis for the integer homology is given by the rook placements in P(m, n) having all of the rooks occur in shaded squares of the first row. Furthermore,

i≥0 dim(H i (C, ∂; Z)) • q i = q n(n-1) • m+1 2 n q 2 .

Generating function and orthogonality

In [START_REF] Viennot | A combinatorial theory for general orthogonal polynomials with extensions and applications[END_REF] Viennot has some beautiful results in which he gave combinatorial bijections for orthogonal polynomials and their moment generating functions. One well-known relation between the ordinary signed Stirling numbers of the first kind and Stirling numbers of the second kind is their orthogonality. A bijective proof of the orthogonality of their q-analogues via 0-1 tableaux was given by de Médicis and Leroux [2, Proposition 3.1].

There are a number of two-variable Stirling numbers of the second kind using bistatistics on RG-words and rook placements. See [START_REF] Wachs | q-Stirling numbers and set partition statistics[END_REF] and the references therein. Letting t = 1 + q we define (q, t)-analogues of the Stirling numbers of the first and second kind. We show orthogonality holds combinatorially for the (q, t)-version of the Stirling numbers via a sign-reversing involution on ordered pairs of rook placements and RG-words. Definition 9.1 Define the (q, t)-Stirling numbers of the first and second kind by s q,t [n, k] = (-1) n-k • T ∈Q(n-1,n-k) q s(T ) • t r(T ) and S q,t [n, k] = w∈A(n,k) q A(w) • t B(w) .

For what follows, let (q + even, q k-1 + (q k-3 + q k-5 + • • • + 1) • t when k is odd.

(9.1)

Corollary 9.2 The (q, t)-analogue of Stirling numbers of the first and second kind satisfy the following recurrences:

s q,t [n, k] = s q,t [n -1, k -1] -[n -1] q,t • s q,t [n -1, k] for n ≥ 1 and 1 ≤ k ≤ n, (9.2)
and S q,t [n, k] = S q,t [n -1, k -1] + [k] q,t • S q,t [n -1, k] for n ≥ 1 and 1 ≤ k ≤ n (9.3) with initial conditions s q,t [n, 0] = δ n,0 and S q,t [n, 0] = δ n,0 .

Recall the generating polynomials for q-Stirling numbers are (x) n,q = n k=0 s q [n, k] • x k and x n = n k=0 S q [n, k] • (x) k,q , where (x) k,q = k-1 m=0 (x -[m] q ). We can generalize these to (q, t)-polynomials.

Theorem 9.3 The generating polynomials for the (q, t)-Stirling numbers are (x) n,q,t = n k=0 s q,t [n, k] • x k and x n = n k=0 S q,t [n, k] • (x) k,q,t , where (x) k,q,t = k-1 m=0 (x -[m] q,t ).

Theorem 9.4 The (q, t)-Stirling numbers are orthogonal, that is, for m ≤ n, Furthermore, this orthogonality holds bijectively.

Fig. 1 :

 1 Fig. 1: The matching of the Stirling poset Π(5, 3). The matched elements are indicated by arrows. The rank generating function for this poset is Sq[5, 3] = 6 + 8q + 7q 2 + 3q 3 + q 4 .

Lemma 4. 2

 2 Let a and b be two distinct elements in the Stirling poset of the second kind Π(n, k) such that a ≺ u(a) b ≺ u(b). Then the element a is lexicographically larger than the element b.

Fig. 2 :

 2 Fig.2: The decomposition of the Stirling poset Π(5, 3) into Boolean algebras B0, B1 and B2. Based on the ranks of the minimal elements in each Boolean algebra, one can read the weight of the poset as Sq[5, 3] = 1 + 2(1 + q) + 3(1 + q) 2 + q 2 + 3q 2 (1 + q) + q 4 .

Theorem 5 . 1

 51 The Stirling poset of the second kind Π(n, k) can be decomposed as the disjoint union of Boolean intervals Π(n, k) = w∈A(n,k) [w, α(w)].

Lemma 6 . 1

 61 For example, if w = 122344 then E(122344) = {3, 6} and ∂(122344) = 121344 -122343. With this definition of the boundary operator ∂, we have the following lemma. The map ∂ is a boundary map on the algebraic complex (C, ∂) with the poset Π(n, k) as support. Lemma 6.2 The weighted generating function of the unmatched words U

Fig. 4 :

 4 Fig.4: The matching on Γ(4, 2). There is one unmatched rook placement on rank 2.

Theorem 8 . 2

 82 The matching M on the Stirling poset of the first kind Γ(m, n) is an acyclic matching. Next we give a decomposition of the Stirling poset of the first kind Γ(m, n) into Boolean algebras indexed by the allowable rook placements. This will lead to a boundary map on the algebraic complex with Γ(m, as support. placement obtained by shifting is not in the first row up by one. Then we have Theorem 8.3 The Stirling poset of the first kind Γ(n, k) can be decomposed as disjoint union of Boolean intervals Γ(m, n) = T ∈Q(m,n) [T, α(T )].

Lemma 8 . 4

 84 The map ∂(T ) = ri∈N (T )

  t [n, k] • S q,t [k, m] = δ m,n and n k=m S q,t [n, k] • s q,t [k, m] = δ m,n .

Acknowledgements

The authors thank Dennis Stanton for conversations when this project was being initiated. They also thank Richard Ehrenborg, who provided many helpful comments on the write-up.

Partially supported by National Security Agency grant H98230-13-1-0280. The second author would like to thank Princeton University where this research was completed. This work was partially supported by a grant from the Simons Foundation (#206001 to Margaret Readdy).

1365-8050


Mikael Hansson
email: mikael.hansson@liu.se

The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

Keywords: Bruhat order, symmetric group, involution, conjugacy class, graded poset, EL-shellability

Introduction

Partially ordered by the Bruhat order, the symmetric group S n is a graded poset whose rank function is given by the number of inversions, and Edelman [START_REF] Edelman | The Bruhat order of the symmetric group is lexicographically shellable[END_REF] proved that it is EL-shellable. Richardson and Springer [START_REF] Richardson | The Bruhat order on symmetric varieties[END_REF] proved that the set I n of involutions in S n and the set F 0 n of fixed point-free involutions are graded. Incitti [START_REF] Incitti | The Bruhat order on the involutions of the symmetric group[END_REF] proved that the rank function of I n can be expressed as the average of the number of inversions and the number of exceedances, and that I n is EL-shellable. Hultman [START_REF] Hultman | Twisted identities in Coxeter groups[END_REF] studied (in a more general setting, which we shall describe shortly) F 0 n and F 1 n , the set of involutions with exactly one fixed point. It follows that F 0 n is graded and Hultman conjectured that the same is true for F 1 n . Can, Cherniavsky, and Twelbeck [START_REF] Can | Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions[END_REF] recently proved that F 0 n is EL-shellable. We consider the following generalisation. For a ∈ {0, 1, . . . , n}, let F a n be the conjugacy class in S n consisting of the involutions with a fixed points, and for A ⊆ {0, 1, . . . , n}, let

F A n = a∈A F a n .
Both I n and F A n are regarded as posets with the order induced by the Bruhat order on S n . Note that

F A n = {σ ∈ I n | σ has a fixed points for some a ∈ A}.
Also note that for all elements in I n , the number of fixed points is congruent to n modulo 2. Hence, we may assume that all members of A have the same parity as n.

Depicted in Figures 1 and2, are the Hasse diagrams of I 4 , F 0 4 , and F 2 4 .

•

• • • • • • • • Figure 2: Hasse diagrams of F 0 4 (left) and F 2 4 (right).
Our main result is a complete characterisation of the sets A for which F A n is graded. In particular, we prove that F 1 n is graded. Informally, F A n is graded precisely when A -{n} is empty or an "interval," which may consist of a single element if it is 0, 1, or n -2. The following theorem, which is our main result, makes the above precise. It also gives the rank function of F A n when it exists.

Theorem 1 The poset F A n is graded if and only if A -{n} = ∅ or A -{n} = {a 1 , a 1 + 2, . . . , a 2 } with a 1 ∈ {0, 1}, a 2 = n -2, or a 2 -a 1 ≥ 2. Furthermore, when F A n is graded, its rank function ρ is given by

ρ(σ) = inv(σ) + exc(σ) -n + ã 2 + 1 if n ∈ A 0 otherwise,
where inv(σ) and exc(σ) denote the number of inversions and exceedances, respectively, of σ, and ã = max(A -{n}). In particular, F A n has rank

ρ(F A n ) = n 2 -a 2 -2n + 2ã 4 + 1 if n ∈ A 0 otherwise,
where a = min A.

The following result is direct consequence of Theorem 1.

Corollary 2

The posets

F 0 n , F 1 n , F n-2 n
, and F n n are the only graded conjugacy classes of involutions in S n . Furthermore, the rank function ρ of F 0 n and F 1 n is given by

ρ(σ) = inv(σ) -n/2 2 ,
and the rank function ρ of F n-2 n is given by

ρ(σ) = inv(σ) -1 2 .
It is well known that F n-2 n is graded (in fact, it coincides with the root poset of the Weyl group A n-1 ∼ = S n ). As was mentioned above, the gradedness of F 0 n was proved by Richardson and Springer, and that of F 1 n was conjectured by Hultman. These two posets are special cases of a more general construction from Hultman's paper [START_REF] Hultman | Twisted identities in Coxeter groups[END_REF], which we now describe. (i) Given a finitely generated Coxeter system (W, S) and an involutive automorphism θ of (W, S) (i.e., a group automorphism θ of W such that θ(S) = S and θ 2 = id), let

ι(θ) = {θ(w -1 )w | w ∈ W } and I(θ) = {w ∈ W | θ(w) = w -1 }
be the sets of twisted identities and twisted involutions, respectively. Clearly, ι(θ) ⊆ I(θ) ⊆ W . Note that when θ = id, ι(θ) and I(θ) reduce to the sets of the (ordinary) identity and (ordinary) involutions in W . Each subset of W is regarded as a poset with the order induced by the Bruhat order on W . When W is the symmetric group S n , there is a unique non-trivial automorphism of (W, S), mapping s i = (i, i + 1) to s n-i .

We say that θ has the no odd flip property if the order of sθ(s) is even or infinite for all s ∈ S with s = θ(s). If W is finite and irreducible, then θ has the no odd flip property, unless W is of type A 2n ∼ = S 2n+1 or I 2 (2n + 1) for some n ≥ 1, and θ is the unique non-trivial automorphism. The poset I(θ) is always graded. Furthermore, we have the following result, from which it follows that F 0 n is graded, as we shall see.

Theorem A ([8, Theorem 4.6 and Proposition 6.7]) If θ has the no odd flip property, then ι(θ) is graded with the same rank function as I(θ).

If W is finite, it contains a greatest element w 0 , and θ(w) = w 0 ww 0 defines an involutive automorphism of (W, S). Since ι(θ)

= {w 0 w -1 w 0 w | w ∈ W } and I(θ) = {w ∈ W | w 0 ww 0 = w -1 }, w 0 • ι(θ) = {w -1 w 0 w | w ∈ W } and w 0 • I(θ) = {w 0 w | w 0 ww 0 = w -1 } = {w 0 w | (w 0 w) 2 = e}.
Since left (as well as right) multiplication by w 0 is a poset anti-automorphism (i.e., an order-reversing bijection whose inverse is order-reversing), ι(θ) is isomorphic to the dual of [w 0 ], where [w 0 ] is the conjugacy class of w 0 , and I(θ) is isomorphic to the dual of I(W ), where I(W ) is the set of involutions in W . When W is the symmetric group S n , this θ is the unique non-trivial automorphism of (W, S), and I(W ) = I n . For n even, [w 0 ] = F 0 n , and for n odd, [w 0 ] = F 1 n . Thus, it follows from Theorem A that F 0 n is graded. It was conjectured by Hultman [8, Conjecture 6.1] that ι(θ) is graded when W = A 2n . As we have seen, this is equivalent to F 1 n being graded, which is the case (see Corollary 2). Since ι(θ) is graded whenever W is dihedral, as is easily seen, it therefore follows that ι(θ) is graded whenever W is finite and irreducible. From this, we get the following (we omit the proof):

Theorem 3 If W is finite, then ι(θ) is graded.
Let us also mention a connection to work by Richardson and Springer [START_REF] Richardson | The Bruhat order on symmetric varieties[END_REF][START_REF] Richardson | Complements to: The Bruhat order on symmetric varieties[END_REF], who studied a graded poset V of orbits of certain symmetric varieties (depending on, inter alia, a group G). They did so by defining an order-preserving function ϕ : V → I(θ) ⊆ W (where the Weyl group W depends on, inter alia, G).

When W = S n , I(θ) is the image of an injective ϕ (for details, see [START_REF] Richardson | The Bruhat order on symmetric varieties[END_REF]Example 10.2]). When n is even, the same is true for ι(θ) (see [START_REF] Richardson | The Bruhat order on symmetric varieties[END_REF]Example 10.4] or [8, Example 3.1]). Thus, I n and F 0 n are isomorphic to the duals of such posets V . Hence, I n and F 0 n are graded. However, these are not the only F A n that occur as the image of a ϕ. To describe these sets, and for later purposes, define

F ≤a n = i≥0 F a-2i n and F ≥a n = i≥0 F a+2i n ,
and for a 2 = a 1 + 2m, where m is a positive integer, let

F a1:a2 n = F ≥a1 n ∩ F ≤a2 n .
As described in [START_REF] Richardson | The Bruhat order on symmetric varieties[END_REF], the image of ϕ can be read off from the corresponding Satake diagram. It follows from Satake diagrams A III and A IV in Helgason [START_REF] Helgason | Differential geometry, Lie groups, and symmetric spaces[END_REF]Table VI] that for each a ≤ n -2, F ≥a n is the image of a ϕ. (From Satake diagrams A I and A II, it follows that I(θ) and ι(θ), respectively, are the images of such functions).

The remainder of this extended abstract is organised as follows. In Section 2, we agree on notation and gather the necessary definitions and previous results. Then, in Section 3, we sketch the proof of our main result (Theorem 1). Finally, in Section 4, we give a short new proof of the following result, which was recently proved by Can, Cherniavsky, and Twelbeck.

Theorem B ([3, Theorem 1]) The poset F 0 n is EL-shellable.

Notation and preliminaries

Poset notation and terminology will follow [START_REF] Stanley | Enumerative combinatorics[END_REF]. In particular, if P is a poset and x ≤ y in P , then [x, y] = {z ∈ P | x ≤ z ≤ y} and (x, y) = {z ∈ P | x < z < y}. Furthermore, in a finite poset P , denotes the covering relation, a chain

x 0 < x 1 < • • • < x k is saturated if x i-1 x i for all i ∈ [k],
P is bounded if it has a minimum (denoted by 0) and a maximum (denoted by 1), and P is graded of rank n if every maximal chain has length n. In this case, there is a unique rank function ρ : P → {0, 1, . . . , n} such that ρ(x) = 0 if x is a minimal element of P , and ρ(y) = ρ(x) + 1 if x y in P ; x has rank i if ρ(x) = i. An x-y-chain is a saturated chain from x to y.

Let P be a finite, bounded, and graded poset. An edge-labelling of P is a function λ : {(x, y)

∈ P 2 | x y} → Q, where Q is a totally ordered set. If λ is an edge-labelling of P and x 0 x 1 • • • x k is a saturated chain, let λ(x 0 , x 1 , . . . , x k ) = (λ(x 0 , x 1 ), λ(x 1 , x 2 ), . . . , λ(x k-1 , x k )). The chain is said to be increasing if λ(x i-1 , x i ) ≤ λ(x i , x i+1 ) for all i ∈ [k -1], and decreasing if λ(x i-1 , x i ) > λ(x i , x i+1 ) for all i ∈ [k -1].
An edge-labelling λ of P is an EL-labelling if, for all x < y in P , there is exactly one increasing x-y-chain, say x 0

x 1 • • • x k , and this chain is lexicographically minimal, or lex-minimal, among the x-y-chains in P (i.e., if y 0 y 1 • • • y k is any other x-y-chain, then λ(x j-1 , x j ) < λ(y j-1 , y j ), where j = min{i ∈ [k] | λ(x i-1 , x i ) = λ(y i-1 , y i )}; this is known as the lexicographic order). If P has an EL-labelling, P is said to be EL-shellable. The reason for this is the following result, due to Björner.

Theorem C ([1, Theorem 2.3]) Let P be a finite, bounded, and graded poset. If P is EL-shellable, then its order complex ∆(P ) is shellable.

For σ ∈ S n and (k, l) ∈ [n] 2 , let σ[k, l] = |{i ≤ k | σ(i) ≥ l}|.
The Bruhat order on S n may be defined as follows (see, e.g., [2, Theorem 2.1.5]):

Definition 4 Let σ, τ ∈ S n . Then σ ≤ τ if and only if σ[k, l] ≤ τ [k, l] for all (k, l) ∈ [n] 2 .
Let us turn to involutions in the symmetric group. Here, notation will follow [START_REF] Incitti | The Bruhat order on the involutions of the symmetric group[END_REF]. Let σ ∈ S n . A rise of σ is a pair (i, j) ∈ [n] 2 such that i < j and σ(i) < σ(j). A rise (i, j) is called free if there is no i < k < j such that σ(i) < σ(k) < σ(j). An inversion is a pair (i, j) ∈ [n] 2 such that i < j and σ(i) > σ(j). An element i ∈ [n] is a fixed point of σ if σ(i) = i, an exceedance if σ(i) > i, and a deficiency if σ(i) < i. Let inv(σ) and exc(σ) denote the number of inversions and exceedances, respectively, of σ.

Let σ ∈ I n . A free rise (i, j) of σ is suitable if it is an f f -rise (Type 1), an f e-rise (Type 2), an ef -rise (Type 3), a non-crossing ee-rise (Type 4), a crossing ee-rise (Type 5), or an ed-rise (Type 6). Here f e, e.g., means that i is a fixed point of σ while j is an exceedance, and an ee-rise is crossing if σ(i) < j and non-crossing otherwise.

The following definition is very important.

Definition 5 Let σ ∈ I n and let (i, j) be a suitable rise of σ. We define a new involution ct (i,j) (σ) as follows:

If (i, j) is of Type 1, then ct (i,j) (σ) = σ(i, j). If (i, j) is of Type 2, then ct (i,j) (σ) = σ(i, j, σ(j)). If (i, j) is of Type 3, then ct (i,j) (σ) = σ(i, j, σ(i)). If (i, j) is of Type 4, then ct (i,j) (σ) = σ(i, j)(σ(i), σ(j)). If (i, j) is of Type 5, then ct (i,j) (σ) = σ(i, j, σ(j), σ(i)). If (i, j) is of Type 6, then ct (i,j) (σ) = σ(i, j)(σ(i), σ(j)).
See [9, Table 1] for pictures describing the action of ct (i,j) on the diagram of σ.

Incitti characterised the covering relation in I n as follows.

Lemma 6 ([9, Theorem 5.1]) Let σ, τ ∈ I n . Then σ τ in I n if and only if τ = ct (i,j) (σ) for some (necessarily unique) suitable rise (i, j) of σ.

If τ = ct (i,j) (σ) for some suitable rise (i, j) of σ, let λ(σ, τ ) = (i, j). By Lemma 6, this defines an edge-labelling of I n (with {(i, j) ∈ [n] 2 | i < j} totally ordered by the lexicographic order, i.e., (i 1 , j 1 ) < (i 2 , j 2 ) if and only if i 1 < i 2 , or i 1 = i 2 and j 1 < j 2 ). Whenever we consider an edge-labelling of I n , it is this one. If λ(σ, τ ) = (i, j), then (i, j) is the label on the cover σ τ ; (i, j) is a label on a chain if it is the label on some cover of the chain.

Let τ ∈ I n and let (i, j) be an inversion of τ . If (i, j) is a suitable rise of some σ ∈ I n and ct (i,j) (σ) = τ , then σ is unique, and we write σ = ict (i,j) (τ ).

For σ < τ in I n , let di(σ, τ ) = min{i ∈ [n] | σ(i) = τ (i)}.

We shall need the following results, due to Incitti:

Lemma 7 ([9, Theorem 5.2]) The poset I n is graded with rank function ρ given by ρ(σ) = inv(σ) + exc(σ) 2 .

Lemma 8 ([9, Theorem 6.2]) Let σ < τ in I n . Then there is exactly one increasing σ-τ -chain, and it is lex-minimal.

Lemma 9 ([9, Theorem 7.3]) Let σ < τ in I n . Then there is exactly one decreasing σ-τ -chain.

Remark 1 Since ct (i,j) (σ)(i) > ct (i,j) (σ)(j), there is also exactly one "weakly" decreasing σ-τ -chain. This fact is used in Section 4.

Figure 1 :

 1 Figure 1: Hasse diagram of I4 with the involutions with zero (•), two (•), and four ( ) fixed points indicated.

(i) The results below are taken from[START_REF] Hultman | Fixed points of involutive automorphisms of the Bruhat order[END_REF][START_REF] Hultman | The combinatorics of twisted involutions in Coxeter groups[END_REF][START_REF] Hultman | Twisted identities in Coxeter groups[END_REF]. In general, we do not indicate which results are from which paper. For general Coxeter group terminology and results, see[START_REF] Björner | Combinatorics of Coxeter groups[END_REF].

Acknowledgements

The author thanks Axel Hultman for helpful comments and fruitful discussions.

Sketch of the proof of the main result

In this section, we prove, sketch the proofs of, or simply state, a number of lemmas and propositions, from which Theorem 1 easily follows.

The strategy for proving that a poset F A n is graded is as follows. We first prove that F A n has a maximum and that all its minimal elements have the same rank in I n (see Propositions 11 and 12). We then prove that if σ, τ ∈ F A n , then σ τ in F A n if and only if σ τ in I n (one implication is obvious). This is done in Lemmas 15, 16, and 17. Since I n is graded, it thus follows that F A n is graded. In particular, when F A n ∈ {F ≤a n , F ≥a n }, to prove that σ τ in I n if σ τ in F A n , we assume that σ τ in I n , and consider the increasing and the decreasing σ-τ -chains in I n . We then prove that either the element in the increasing chain that covers σ, or the element in the decreasing chain that is covered by τ , has to belong to F A n . This contradicts the fact that σ τ in F A n . To prove that a poset F A n is not graded, we consider an interval [σ, τ ], and then construct two

In the next two results, we describe the maximal and minimal elements of F A n . The proofs are not given here.

Proposition 11 For all n and all

, where a = min A. Proposition 12 For all n and all A, all minimal elements of F A n have rank (n -max A)/2 in I n . Recall that

where a 2 = a 1 + 2m for some positive integer m. Note that F a1:a2 n is not defined for a 1 = a 2 . The following lemma will eventually allow us to conclude that F ≤a n , F ≥a n , and F a1:a2 n are graded.

Lemma 13 If every cover in F A n is a cover in I n , then F A n is graded.

Proof: This follows from Lemma 7 and Propositions 11 and 12. 2

The next lemma is used in the proofs of Lemmas 15, 16, and 17, which, together with Lemma 13, show that F ≤a n , F ≥a n , and F a1:a2 n are graded.

Lemma 14 Let σ < τ in I n . Then the label (i, j) on any cover in [σ, τ ] satisfies i ≥ di(σ, τ ).

Proof: Suppose i < di(σ, τ ) for the label (i, j) on σ π ≤ τ . Then π(k) = τ (k) for k < i and σ(i) = τ (i). However, it follows from Definition 5 that π

By Definition 4, this contradicts the fact that π ≤ τ . Thus i ≥ di(σ, τ ). The result follows by induction. 2

Lemma 15 Let σ τ in F ≤a n . Then σ τ in I n .

Proof: Assume that σ τ in I n , and let

, and let (i σ , j σ ) and (i τ , j τ ) be the labels on σ σ 1 and τ 1 τ , respectively. Since σ(h) = τ (h), it follows from Lemma 14 that h is in some label on C I and some label on

. By Definition 4, this contradicts the fact that σ ≤ τ 1 .

2

Proof: Assume that σ τ in I n , and let

, and let (i σ , j σ ) and (i τ , j τ ) be the labels on σ σ 1 and τ 1 τ , respectively. Since σ(h) = τ (h), it follows from Lemma 14 that h is in some label on C I and some label on C D . Since C I is increasing, i σ = h, and since σ 1 / ∈ F ≥a n , h is a fixed point of σ (Type 1). Since C D is decreasing, i τ = h, and since τ 1 / ∈ F ≥a n , h is an exceedance of τ 1 (Type 5). Let m be such that h is an exceedance of τ 1 , . . . , τ m-1 and a fixed point of τ m (with τ k+1 = σ). Then the labels on τ τ

However, since the cover τ 1 τ is of Type 5, τ 1 (h) < j 1 , which is a contradiction.

2

Lemma 17 Let σ τ in F a1:a2 n . Then σ τ in I n .

The proof, which is omitted here, is largely a combination of the proofs of Lemmas 15 and 16.

Proposition 18 The posets F ≤a n , F ≥a n , and F a1:a2 n are graded.

Proof: This follows from Lemmas 13, 15, 16, and 17. 2

In the following two results, we consider the sets A for which

∈ A, then F A n is not graded. The proof, which is not given here, is similar to, but easier than, the proof of Proposition 20.

Proposition 20 If there is an i / ∈ A and a positive integer m such that i -

1, and consider the interval [σ, τ ]. We obtain a σ-τ -chain C in I k by k -2 f e-rises with labels (k -2, k -1), (k -3, k -2), . . . , (1, 2) (from σ to τ ). We also obtain a σ-τ -chain in I n by (k -2)/2 f f -rises with labels (1, 2), [START_REF] Can | Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions[END_REF][START_REF] Edelman | The Bruhat order of the symmetric group is lexicographically shellable[END_REF], . . . , (k -3, k -2), followed by (k -2)/2 crossing ee-rises with labels (k -3, k -1), (k -5, k -3), . . . , [START_REF] Björner | Shellable and Cohen-Macaulay partially ordered sets[END_REF][START_REF] Can | Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions[END_REF].

Let π be the fixed point-free involution obtained after the f f -rises. Since each f f -rise decreases the number of fixed points and I k is graded, (σ, π) ∩ F {0,k-2} k = ∅, and since each crossing ee-rise increases the number of fixed points and , and the involutions marked by a • belong to I6 -F {0,4} 6

. On the edges (covers in I6) are the labels (i, j).

We are now ready to prove our main result:

Proof of Theorem 1: The first claim follows from Lemma 10 and Propositions 18, 19, and 20. (It is readily checked that if F A-{n} n does not belong to {∅, F ≤a n , F ≥a n , F a1:a2 n }, then either there is an i ∈ [2, n -4] such that i ∈ A but i -2, i + 2 / ∈ A, or there are an i / ∈ A and a positive integer m such that i -2, i + 2m ∈ A -{n}.) The second claim follows from Lemma 7, Proposition 12, and Lemmas 15, 16, and 17. The third claim follows from the second claim and Proposition 11. 2

4 EL-shellability of F 0 n In this section, we give a new proof of Theorem B, due to Can, Cherniavsky, and Twelbeck [START_REF] Can | Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions[END_REF]. Our proof is largely based on the same main idea as their proof, together with the technique used in the proof of Lemma 15. The proof in [START_REF] Can | Lexicographic shellability of the Bruhat-Chevalley order on fixed-point-free involutions[END_REF] goes as follows:

Let σ < τ in F 0 n . It follows from, e.g., Theorem A and the paragraphs following it, that there exists a σ-τ -chain in I n that is contained in F 0 n . Let C be the lex-maximal such chain. The idea of the proof is to show that C is decreasing. Then, by reversing the lexicographic order on the set {(i, j) ∈ [n] 2 | i < j} (i.e., by letting (i 1 , j 1 ) < (i 2 , j 2 ) if and only if i 1 > i 2 , or i 1 = i 2 and j 1 > j 2 ), one obtains an edgelabelling of F 0 n such that in each interval, there is an increasing σ-τ -chain which is lex-minimal. By Lemma 9 and the remark following it, this is an EL-labelling of F 0 n .

We use the same main idea, namely, to show that the decreasing σ-τ -chain in I n is contained in F 0 n , and then reverse the lexicographic order. However, we give a direct proof of this fact. By using the same technique as in the proof of Lemma 15, we get a very short argument.

Lemma 21 Let σ < τ in F 0 n and let

be the increasing σ-τ -chain in I n , and let (i σ , j σ ) and (i τ , j τ ) be the labels on σ σ 1 and τ 1 τ , respectively. Since σ(h) = τ (h), it follows from Lemma 14 that h is in some label on C I and some label on C D . Since C I is increasing, i σ = h, and since σ has no fixed points, h is an exceedance of σ (Type 4, 5, or 6). Since C D is decreasing, i τ = h, and were τ 1 / ∈ F 0 n , h would be a fixed point of τ 1 (Type 1). Hence, by Definition 4,

We can now complete the proof of Theorem B:

Proof of Theorem B: Let σ < τ in F 0 n . By Lemma 21, the decreasing σ-τ -chain in I n is contained in F 0 n . If we can show that this chain is lex-maximal, then by reversing the lexicographic order and invoking Lemma 9, we are done.

In order to obtain a contradiction, let C = σ 1 • • • σ k be the lex-maximal σ-τ -chain in I n , and assume that it is not decreasing; say that λ(σ 1 , σ 2 ) ≤ λ(σ 2 , σ 3 ). By Lemma 8, σ 1 σ 2 σ 3 is lexminimal among the σ 1 -σ 3 -chains in I n . Hence, σ 1 σ 2 σ 3 • • • σ k , where σ 1 σ 2 σ 3 is the decreasing σ 1 -σ 3 -chain, is lex-larger than C, which is a contradiction.

2

Is it possible to use the same idea to prove that every interval in F A n ⊂ I n is EL-shellable for some A = {0}? Unfortunately, the answer is no, since for all A = {0} (except the trivial cases A = ∅ and A = {n}), it is possible to find σ 1 < τ 1 and σ 2 < τ 2 in F A n , such that the increasing σ 1 -τ 1 -chain and the decreasing σ 2 -τ 2 -chain in I n , are of length 2 and are not contained in F A n .