Abstract An involution in a Coxeter group has an associated set of involution words, a variation on reduced words. These words are saturated chains in a partial order first considered by Richardson and Springer in their study of symmetric varieties. In the symmetric group, involution words can be enumerated in terms of tableaux using appropriate analogues of the symmetric functions introduced by Stanley to accomplish the same task for reduced words. We adapt this approach to the group of signed permutations. We show that involution words for the longest element in the Coxeter group C n are in bijection with reduced words for the longest element in A n = S n+1 , which are known to be in bijection with standard tableaux of shape (n, n − 1, . . . , 2, 1). Introduction Let W be a Coxeter group with simple generating set S. A reduced word for w ∈ W is a minimallength sequence (r 1 , r 2 , . . . , r ℓ ) of simple generators r i ∈ S with w = r 1 r 2 · · · r ℓ . Let R(w) be the set of reduced words for w. Introduction Of primary interest are the finite Coxeter groups of classical types A and C, given as follows. Fix a positive integer n and let [n] = {1, 2, . . . , n} and [±n] = {±1, ±2, . . . , ±n}. Let A n = S n+1 be the group of permutations of [n + 1] . Let C n be the group of permutations w of [±n] with w(−i) = −w(i) for all i. Define s 1 , s 2 , . . . , s n ∈ A n and t 0 , t 1 , . . . , t n−1 ∈ C n by s i = (i, i + 1), t 0 = (−1, 1), and t i = (−i − 1, −i)(i, i + 1) for i = 0. Introduction (1.1) Introduction Then A n is a Coxeter group relative to the generating set S = {s 1 , s 2 , . . . , s n } while C n is a Coxeter group relative to the generating set S = {t 0 , t 1 , . . . , t n−1 }. We refer to elements of C n as signed permutations. Introduction Each finite Coxeter group contains a unique element of maximal length, where the length of an element w refers to the common length of any word in R(w). Let w A n and w C n denote the longest elements of A n and C n . Then w A n is the permutation given in one-line notation by (n + 1)n · · · 321 while w C n is the signed permutation given by the negation map i → −i. There are attractive product formulas for the number of reduced words for both of these permutations: Introduction Stanley proved the first of these identities [30, Corollary 4.3] and conjectured the second, which was later shown by Haiman [8, Theorem 5.12] . Let SYT(λ) be the set of standard Young tableaux of shape λ. Define δ n = (n, n−1, . . . , 2, 1) and write (n n ) for the partition with n parts of size n. The identities (1.2) are equivalent to R w A n = | SYT(δ n )| and R w C n = | SYT((n n ))| via the hook-length formula [29, Corollary 7.21.6] . As one would expect from this formulation, there are natural bijective proofs of the identities (1.2), due to Edelman and Greene [6] in type A and to Haiman [8] and Kraśkiewicz [20] in type C. Introduction The main result of this paper is a product formula similar to (1.2) for the cardinality of a set of reduced-word-like objects associated to w C n . Write ℓ : W → N for the length function of the Coxeter system (W, S). There exists a unique associative product • : W × W → W with s • s = s for any s ∈ S and u • v = uv for any u, v ∈ W such that ℓ(uv) = ℓ(u) + ℓ(v) [19, Theorem 7.1] . This is sometimes called the Demazure product or Hecke product of (W, S). The pair (W, •) is sometimes called the 0-Hecke monoid of (W, S). Introduction Let I(W ) def = {y ∈ W : y = y −1 } be the set of involutions in W . This set is preserved by the conjugation action w : y → w −1 • y • w of the 0-Hecke monoid (W, •). Indeed, it is a straightforward exercise from the exchange principle for Coxeter systems (see [4, §1.5] which is equivalent to [18, Lemma 3.4 ]. An involution word for y ∈ I(W ) is a minimal-length sequence (r 1 , r 2 , . . . , r ℓ ) of simple generators r i ∈ S such that y = r ℓ • (· · · • (r 2 • (r 1 • 1 • r 1 ) • r 2 ) • · · · ) • r ℓ . Introduction The parentheses make clear how to evaluate the right hand expression using (1.3), but are actually superfluous since • is associative. LetR(y) be the set of involution words for y ∈ I(W ). This set is always nonempty, withR(1) = {∅} where ∅ is the empty word. Definel(y) for y ∈ I(W ) to be the common length of any word inR(y). Introduction Example 1.1. Let s i ∈ A n = S n+1 and t i ∈ C n be as in (1.1 and it holds that w A 2 = s 1 s 2 s 1 = s 2 s 1 s 2 andR(w A 2 ) = {(s 1 , s 2 ), (s 1 , s 2 )}. In C 2 , we have Introduction Involution words first appeared in work of Richardson and Springer [27, 28] , and have since been studied by various authors: Can, Joyce and Wyser [5] , the authors and Hamaker [9, 10, 11, 12, 13] , Hu and Zhang [16, 17] , Hultman [18] , and Hansson and Hultman [15] . In [9] , the authors and Hamaker showed that Introduction where p = ⌊ n 2 ⌋ and q = ⌈ n 2 ⌉, and conjectured the following theorem, which is our main result. Introduction There is an algebraic approach to enumerating R(w A n ), R(w C n ),R(w A n ), andR(w C n ) by means of certain generating functions called Stanley symmetric functions. We write [x 1 x 2 · · · ]f for the coefficient of a square-free monomial in a homogeneous symmetric function f . The Stanley symmetric functions of interest, which will be defined in Section 2.2. have the following properties: Introduction • The (type A) Stanley symmetric function F w of w ∈ A n has [x 1 x 2 · · · ]F w = |R(w)|. Introduction • The (type C) Stanley symmetric function G w of w ∈ C n has [x 1 x 2 · · · ]G w = 2 ℓ(w) |R(w)|. Introduction • The (type A) involution Stanley symmetric functionF y of y ∈ I(A n ) is a multiplicity-free sum of certain instances of F w , and has [x 1 x 2 · · · ]F y = |R(y)|. Introduction • The (type C) involution Stanley symmetric functionĜ y of y ∈ I(C n ) is a multiplicity-free sum of certain instances of G w , and has [x 1 x 2 · · · ]Ĝ y = 2l (y) |R(y)|. Introduction There are expressions for F w A n , G w C n , andF w A n as Schur functions s λ , Schur Q-functions Q λ , and Schur S-functions S λ . For the definitions of these symmetric functions, see Section 2. Introduction ..,3,1) = S (n n ) . Theorem 1.5 (Hamaker, Marberg, and Pawlowski [12, Corollary 1.14] ). It holds that F w A n = 2 −q Q (n,n−2,n−4,... ) = s δp s δq where p = ⌊ n 2 ⌋ and q = ⌈ n 2 ⌉. Introduction We prove Theorem 1.2 enumeratingR(w C n ) by adding an entry forĜ w C n to this list. Theorem 1.6. It holds thatĜ w C n = G w A n = S δn . Our proof in Section 5 of this result proceeds as follows. One can defineĜ w C n as a sum v∈An G v indexed by a certain set A n of signed permutations v ∈ C n , the atoms of w C n . The transition formula of Lascoux-Schützenberger [21] as adapted by Billey [1] generates various identities between sums of type C Stanley symmetric functions. Work of Lam implies that G w A n = S δn [23] , and we apply Billey's transition formula iteratively to rewrite G w A n as the sum v∈An G v . The fact that this is possible is somewhat miraculous. Our arguments rely heavily on a recent characterization of the atoms of w C n by the first author and Hamaker [14] . Preliminaries Symmetric functions Fix a partition λ = (λ 1 ≥ λ 2 ≥ · · · ≥ λ k > 0). The Young diagram of λ is the set of pairs Symmetric functions and j ∈ [λ i ]}, which we envision as a collection of left-justified boxes oriented as in a matrix. A semistandard tableau of shape λ is a filling of the boxes of the Young diagram D λ by positive integers, such that each row is weakly increasing from left to right and each column is (strictly) increasing from top to bottom. Such a tableau is standard if its boxes contain exactly the numbers 1, 2, . . . , |λ|. Symmetric functions Similarly, a marked semistandard tableau of shape λ is a filling of the Young diagram of λ by numbers from the alphabet of primed and unprimed positive integers {1, 2, 3, . . . } ⊔ {1 ′ , 2 ′ , 3 ′ , . . . } such that (i) the rows and columns are weakly increasing under the order 1 ′ < 1 < 2 ′ < 2 < · · · , (ii) no unprimed letter i appears twice in the same column, and (iii) no primed letter i ′ appears twice in the same row. Symmetric functions Assume λ is a strict partition, i.e., has all distinct parts. A marked semistandard shifted tableau of shape λ is a filling of the shifted Young diagram {(i, i + j − 1) : (i, j) ∈ D λ } with primed and unprimed positive integers satisfying properties (i)-(iii) from the previous paragraph. A semistandard marked (shifted) tableau T of shape λ is standard if exactly one of i or i ′ appears in T for each i = 1, 2, . . . , |λ|. Symmetric functions Given a (marked) semistandard (shifted) tableau T , write x T for the monomial formed by replacing the boxes in T containing i or i ′ by x i and then multiplying the resulting variables. then T is semistandard, U is marked and semistandard, and V is marked, semistandard, and shifted. Symmetric functions We have x T = x 3 2 x 3 3 x 4 x 5 and x U = x 4 1 x 2 3 x 4 x 5 and x V = x 1 x 2 2 x 2 3 x 4 x 5 x 6 . Symmetric functions Definition 2.2. Let λ be a partition and let µ be a strict partition. The Schur function of λ, the Schur S-function of λ, and the Schur Q-function of µ are then the respective sums Symmetric functions where T runs over all semistandard tableaux of shape λ, U runs over all semistandard marked tableaux of shape λ, and V runs over all marked semistandard shifted tableaux of shape µ. Symmetric functions The power series s λ , S λ , and Q µ are all symmetric functions. For example, we have Symmetric functions The Schur functions s λ , with λ ranging over all partitions, form a basis for the algebra Λ of symmetric functions. Similarly, the Schur Q-functions Q µ , with µ ranging over all strict partitions, form a basis for the subalgebra Γ ⊂ Λ generated by the odd-indexed power sum symmetric functions. Each Schur Q-function is itself Schur-positive, i.e., a linear combination of Schur functions with positive integer coefficients. Symmetric functions The set of Schur S-functions, with λ ranging over all partitions, is not linearly independent, but also spans the subalgebra Γ. The set {S λ : λ is a strict partition} is a second basis for Γ. For more properties of these functions, see [ Stanley symmetric functions We review the definitions of the Stanley symmetric functions (see [1, 2, 7, 30] ) and involution Stanley symmetric functions (see [9, 12] ) mentioned in the introduction. Stanley symmetric functions where for a reduced word a = (s a 1 , s a 2 , · · · , s a l ), the set C(a) consists of all weakly increasing sequences of positive integers i 1 ≤ i 2 ≤ · · · ≤ i l such that if a j > a j+1 then i j < i j+1 . Stanley symmetric functions Each F w is a linear combination of Schur functions with positive integer coefficients [6] . For example, Stanley symmetric functions where for a reduced word a = (t a 1 , t a 2 , · · · , t a l ), the set D(a) consists of all weakly increasing sequences of positive integers i 1 ≤ i 2 ≤ · · · ≤ i l such that if a j−1 < a j > a j+1 for some j ∈ [l − 1] then either i j−1 < i j ≤ i j+1 or i j−1 ≤ i j < i j+1 . Stanley symmetric functions Each G w is a linear combination of Schur Q-functions with positive integer coefficients [23, Theorem 3.12] . It is an instructive exercise to check that G w C 2 = Q (3,1) = S (2, 2) as predicted by Theorem 1.4; the details are more involved than in our calculation of F w A 2 , however. Stanley symmetric functions Remark. The finite Coxeter groups of classical type B are the same as the groups C n , but there is a distinct notion of type B Stanley symmetric functions. These only differ from G w by a scalar factor, however: the type B Stanley symmetric function of w ∈ C n is 2 −ℓ 0 (w) G w where ℓ 0 (w) is the number of indices i ∈ [n] with w(i) < 0; see [1, 2, 7] . Stanley symmetric functions Notation. The symbols for Stanley symmetric functions are somewhat inconsistent across the literature. The use of F w for type A Stanley symmetric functions, following [30] , is fairly widespread. Nevertheless, these functions are denoted G w in [2, 3] , while in [1, 3] the type C Stanley symmetric functions are denoted F w . Some authors have also used F w [2] and G w [1, 22, 23] for the type B Stanley symmetric functions mentioned in the previous remark. Stanley symmetric functions There is a unique injective group homomorphism ι : Stanley symmetric functions Although s i → t i induces a bijection R(w) → R(ι(w)), it is not obvious from the definitions how to relate F w and G w for w ∈ A n−1 . There is a simple connection, however. Define Stanley symmetric functions where the first span is over all partitions λ and the second two are over all strict partitions µ. Stanley symmetric functions The superfication map φ : Λ → Γ is the linear map with φ(s λ ) = S λ for all partitions λ. This is well-defined since each S λ is a linear combination of S µ 's with µ strict. Stanley symmetric functions We turn to involution Stanley symmetric functions. Let (W, S) be a Coxeter system with length function ℓ. Recall the definition of the Demazure product • : W × W → W from the introduction. Stanley symmetric functions The elements of this set are the atoms of y. Stanley symmetric functions The associativity of • implies that the set of involution wordsR(y) for y ∈ I(W ) is the disjoint union w∈A(y) R(w). The involution length of y isl(y) = ℓ(w) for any w ∈ A(y). Stanley symmetric functions Since F w is Schur-positive and G w is Schur-Q-positive, it holds by construction thatF y andĜ z are respectively Schur-positive and Schur-Q-positive. ForF y , a stronger statement holds: if κ(y) is the number of 2-cycles in y ∈ I(A n ), then 2 κ(y)F y is also Schur-Q-positive [12, Corollary 4.62]. We do not know ifĜ z has any stronger positivity property along these lines; see Section 6.2. Stanley symmetric functions DefineĜ y def =Ĝ ι(y) for y ∈ I(A n−1 ). Since A(ι(y)) = ι(A(y)), the following holds: Transition formulas We use the term word to refer to a finite sequence of nonzero integers. The one-line representation of a signed permutation w ∈ C n is the word w 1 w 2 · · · w n where we set w i = w(i). We usually write m in place of −m so that, for example, the eight elements of C 2 are 12, 12, 12, 1 2, 21, 21, 21, and 2 1. In this notation, the longest element of C n is Transition formulas The map w 1 w 2 · · · w n → w 1 w 2 · · · w n (n+1) is an inclusion C n ֒→ C n+1 . We do not distinguish between w and its image under this map. If w ∈ C n then the words w 1 w 2 · · · w n and w 1 w 2 · · · w n (n+ 1)(n + 2) · · · (n + m) represent the same signed permutation for all m ∈ N. Transition formulas A reflection in a Coxeter group is an element conjugate to a simple generator. With our notation as in [1, §3] , the reflections in C n are the following elements: Transition formulas Observe that t 0 = s 11 and t i = t i,i+1 and s ij = s ii t ij s ii = s jj t ij s jj for i, j ∈ [n] with i < j. If u, v ∈ C n are any elements and t ∈ C n is a reflection such that v = ut and ℓ(v) = ℓ(u) + 1, then we write u ⋖ v, so that ⋖ is the covering relation of the Bruhat order of C n . Transition formulas For example, it holds that 1243 ⋖ 1243 · t 14 = 3241 while 1243 ⋖ 1243 · t 14 = 3241, and it holds that 3241 ⋖ 3241 · s 14 = 1243 while 3241 ⋖ 3241 · s 14 = 1243. Lemma 2.11(c) says that w ⋖ wt ij if and only if w i < w j and no entry in w 1 w 2 · · · w n between positions i and j is between w i and w j in value. Lemma 2.11(a) can be described in the same way using "symmetric" one-line notation: one has w ⋖ ws ii if and only if w i < w i and no number between w i and w i appears in the word w i−1 · · · w 2 w 1 w 1 w 2 · · · w i−1 . One can express Lemma 2.11(b) similarly. We frequently only need the following special cases of these conditions: Transition formulas For w ∈ C n and j ∈ [n], we define three sets: Transition formulas The next theorem, which is analogous to the transition formulas of Lascoux and Schützenberger [21] , is the main technical tool we require to work with type C Stanley symmetric functions. Transition formulas This result leads to an effective algorithm for computing the Schur Q-expansion of G w . Transition formulas The theorem gives a recursion for G w which terminates when w is strictly increasing. Billey shows that this recursion always terminates in a finite number of steps [1, Theorem 4] . by Theorem 2.14(a). It follows that the number of involution words for 8 7 6 5 4 3 2 1 times 2 8+6+4+2 is equal to the number of marked standard shifted tableaux of shape (8, 6, 4, 2) . This example generalizes in a straightforward way from C 8 to any C n . The graph on the left, illustrating Theorem 2.14, is constructed as follows: from each unboxed vertex w which is not increasing (starting with 321), draw an arrow to the boxed vertex v = wt rs and underline the letter of v in position r. In reading these graphs one should keep in mind that we identify Transition formulas (using Theorem 2.14(a)) and Suppose − → G is a directed graph with x a vertex. Write sdeg(x) for the indegree of x minus its outdegree, and deg(x) for the indegree of x plus its outdegree. Atoms The atoms of the longest element w C n ∈ I(C n ) have a number of special properties, which we review in this section. Let S ⊂ Z be a set of integers. A perfect matching on a set S is a set M of pairwise disjoint 2-element subsets {i, j}, referred to as blocks, whose union is In general, |NCSP(n)| = n ⌊n/2⌋ ; see [26, A001405] . We emphasize the following basic observation: Atoms Fact. If M ∈ NCSP(n) and {i, j} ∈ M , then i and j have the same sign or i = −j. Atoms If M ∈ NCSP(n), then α min (M ) and α max (M ) contain exactly one letter from {±i} for each i ∈ [n], so may be interpreted as elements of C n . If u and v are words, both with n ≥ i + 2 letters, then we write u ⊳ i v to mean that Atoms for some numbers a < b < c. Define < A as the transitive closure of the relations ⊳ i for all i ≥ 1. Equivalently, < A is the transitive closure of the relation on words with · · · cab · · · < A · · · bca · · · (3.2) whenever a < b < c and the corresponding ellipses mask identical subsequences. This relation is a partial order since it is a sub-relation of lexicographic order. We apply < A to signed permutations via their one-line representations. Define Fix an atom w ∈ A n . We define the shape of w to be the unique matching M (w) ∈ NCSP(n) with w ∈ A M (w) . It is helpful to understand how the shape of w can be extracted from the one-line representation w 1 w 2 · · · w n . This can be done as follows. Atoms From w ∈ A n , we produce a sequence of words w 0 , w 1 , . . . , w l . Start by letting w 0 = w 1 w 2 · · · w n . For each i > 0, form w i by removing an arbitrary descent from w i−1 , where a descent in a word a 1 a 2 · · · a n is a consecutive subword a i a i+1 with a i > a i+1 . The sequence terminates when we obtain an increasing word w l . Let {c 1 , c 2 , . . . , c k } be the set of letters in w l and suppose q i p i is the descent removed from w i−1 to form w i . We then define Atoms We refer to NNeg(w) and NDes(w) as the nested negated set and nested descent set of w. Atoms Theorem 3.4 (See [14] ). No matter how the words w 0 , w 1 , . . . , w l are constructed, we have: The preceding theorem has several implications, starting with the following observation. Atoms The word w 1 w 2 · · · w n therefore contains no consecutive subwords of the form ba where 0 < a < b or a < b < 0, or of the form cba where a < b < c. Atoms Subwords in the following lemma need not be consecutive. Let w ∈ A n . If 1 ≤ i < j ≤ n are indices such that 0 < w i < −w j and {w i , −w j } ∈ M (w), then we say that i and j are complementary indices in w. If i ∈ [n] is such that w i < 0 and {±w i } ∈ M (w), then we say that i is a symmetric index in w. (a) If w j < e < −w i < 0, then e / ∈ {w 1 , w 2 , . . . , w j , w j+1 }. Atoms (b) If 0 < w i < e < −w j , then e / ∈ {w 1 , w 2 , . . . , w j }. Atoms Proof. We have {w i , −w j } ∈ M (w), so if e ∈ {w 1 , w 2 , . . . , w n } and w i < |e| < −w j , then the noncrossing matching M (w) must contain a block {a, b} with |e| ∈ {a, b} and w i < a < b < −w j , and in this case w i w j ab must be a subword of w 1 w 2 . . . w n by Lemma 3.7(a). Proof. This is immediate from Lemmas 2.11(b) and 3.9. Quasi-atoms Given a word w = w 1 w 2 · · · w n such that |w 1 |, |w 2 |, . . . , |w n | are distinct and nonzero, define fl ± (w) ∈ C n to be the signed permutation whose one-line representation is formed by replacing each letter of w by its image under the order-preserving bijection {±w 1 , ±w 2 , . . . , ±w n } → [±n]. For example, we have fl ± (3257) = 2134 ∈ C 4 . If M is a partition of a symmetric 2n-element subset X = −X ⊂ [±m], then define fl ± (M ) to be the partition of [±n] formed by replacing each element of each block of M by its image under the order-preserving bijection X → [±n]. Quasi-atoms Suppose w ∈ C n and v = fl ± (w 2 w 3 · · · w n ) ∈ A n−1 . Define M ′ (w) to be the unique perfect matching on [n] \ {±w 1 } with fl ± (M ′ (w)) = M (v). Since M (v) is symmetric and noncrossing, M ′ (w) is symmetric and noncrossing. Quasi-atoms The matching M ′ (w) may be read off directly from the one-line representation of w by the following procedure. Let w 0 , w 1 , w 2 , . . . , w l be any sequence of words whose first term is w 0 = w 2 w 3 · · · w n (note the deliberate omission of w 1 ) and whose final term is strictly increasing, in which w i for i > 0 is formed from w i−1 by removing a single descent q i p i . Let {c 1 , c 2 , . . . , c k } be the set of letters in w l . Then M ′ (w) is the matching whose blocks consist of {p, −q}, {−p, q}, and {±c} for each descent (q, p) ∈ {(q 1 , p 1 ), (q 2 , p 2 ), . . . , (q l , p l )} and each c ∈ {c 1 , c 2 , . . . , c k }. This construction is independent of the choices of descents by Theorem 3.4. Quasi-atoms Example 4.1. Let w = 316745 2. One sequence of words w 0 , w 1 , . . . , w l as described above is Quasi-atoms We define A 0 to be the singleton set containing just the empty word ∅. (a) One has w 1 > 0 and fl ± (w 2 w 3 · · · w n ) ∈ A n−1 , so M ′ (w) is defined. Quasi-atoms We write Q + n and Q − n for the sets of even and odd quasi-atoms in C n , and define Q n In rank two we have: Quasi-atoms In rank three we have: do not match any existing entries in [26] . Quasi-atoms It can happen that w ∈ A n and fl ± (w 2 w 3 · · · w n ) ∈ A n−1 , in which case M (w) and M ′ (w) are both defined but unequal. For quasi-atoms, however, this ambiguity does not arise: Proof. Suppose w ∈ A n ∩ Q n . Since w 1 > 0, the index 1 must be complementary to some j ∈ [2, n], but then 0 < w 1 < −w j and necessarily {±w j } ∈ M ′ (w), contradicting the definition of Q n . Quasi-atoms Define < Q as the transitive closure of the relations ⊳ i from (3.1) for i ≥ 2. This is the partial order with v < Q w if and only if v 1 = w 1 and v 2 v 3 · · · v n < A w 2 w 3 · · · w n , or equivalently the transitive closure of the relation on words with Quasi-atoms x · · · cab · · · < Q x · · · bca · · · whenever a, b, c, x are integers with a < b < c and the corresponding ellipses mask identical subsequences. Each interval A M ⊂ A n is preserved by < A , so Q + n and Q − n are preserved by < Q . Let e ∈ [n] and suppose M is a perfect matching on [±n] \ {±e} which is symmetric and noncrossing. Assume M has no blocks {±c} with 0 < e < c. Define NCSQ + (n, e) as the set of such matchings with exactly one block {a, b} such that 0 < a < e < b; define NCSQ − (n, e) as the set of such matchings with no blocks {a, b} such that 0 < a < e < b. Let NCSQ − (n, e). Let w ∈ Q n be a quasi-atom. Mimicking our terminology in the previous section, define indices 2 ≤ i < j ≤ n to be complementary in w if 0 < w i < −w j and {w i , −w j } ∈ M ′ (w), and define an index 2 ≤ i ≤ n to be symmetric for w if w i < 0 and {±w i } ∈ M ′ (w). In view of Proposition 4.4, there is no risk of these notions conflicting with our earlier definitions for atoms. Quasi-atoms With minor changes, the technical properties of atoms in the previous section remain true for quasi-atoms. The following summarizes the main facts we will need. Quasi-atoms i. If {a, d}, {b, c} ∈ M ′ (w) then adbc is a subword of w 2 w 3 · · · w n . Quasi-atoms ii. If {a, b}, {±c} ∈ M ′ (w) then cab is a subword of w 2 w 3 · · · w n . Quasi-atoms iii. If {±a}, {±b} ∈ M ′ (w) then ba is a subword of w 2 w 3 · · · w n . i. If w j < e < −w i < 0 then e / ∈ {w 2 , w 3 , . . . , w j , w j+1 }. Quasi-atoms ii. If 0 < w i < e < −w j then e / ∈ {w 2 , w 3 , . . . , w j }. Quasi-atoms Proof. Since fl ± (w 2 w 3 · · · w n ) is required to belong to A M for some matching M ∈ NCSP(n−1), and since M ′ (w) is defined to be the matching on [±n] \ {±w 1 } with fl ± (M ′ (w)) = M , these properties just restate Corollary 3.6, Lemma 3.7, Corollary 3.8, and Lemma 3.9. Quasi-atoms If w ∈ Q + n is an even quasi-atom then there exists a unique pair of complementary indices 2 ≤ i < j ≤ n with 0 < w i < w 1 < −w j . We call these the distinguished indices of w. Transition graphs We define a directed bipartite graph − → L n with vertex set A n ⊔ Q n . We use the letter L to denote this graph since it will later serve as one "layer" in a larger graph of interest. Each edge − → L n will pass either from an even quasi-atom to an odd quasi-atom, from an odd quasi-atom to an even quasi-atom, or from an odd quasi-atom to an atom. The atoms of w C n = 1 2 3 · · · n will each have a unique incoming edge, and all even quasi-atoms will have one incoming and one outgoing edge. These properties will not be immediately clear from the following definition. Transition graphs First suppose v ∈ Q n is an even quasi-atom. Transition graphs and a unique outgoing edge v → w where Figure 1 shows − → L n for n = 1, 2, 3, 4 and Figure 2 shows a part of − → L 5 . Transition graphs Proof. First suppose v, v ′ ∈ A n and v ⊳ i v ′ . Let u → v and u ′ → v ′ be the unique edges incident to v and v ′ in − → L n . If v 1 < 0 then u = vt 0 and u ′ = v ′ t 0 and clearly u ⊳ i u ′ . Assume b = v 1 > 0 and suppose {b, c} ∈ M (v) is the unique block with 0 < b < c, so that u = t bc v and u ′ = t bc v ′ . We can write v i v i+1 v i+2 = zxy where x < y < z. By Corollary 3.6, it must hold that 0 < z < −x. Since u 2 u 3 · · · u n is given by replacing c by b in v 2 v 3 · · · v n , the only way we can fail to have Transition graphs Our argument is similar to the previous case. We can write v i v i+1 v i+2 = zxy where x < y < z, and 0 < z < −x by Lemma 4.7(b). Since u 2 u 3 · · · u n is given by replacing c by b in v 2 v 3 · · · v n , the only way we can fail to have Finally suppose v ′ ⊳ i v and w ′ = t ab v ′ so that v ′ → w ′ is an edge in − → L n . We can write v i v i+1 v i+2 = yzx where x < y < z, and 0 < z < −x by Lemma 4.7(b). Since w 2 w 3 · · · w n is given by replacing a by b in v 2 v 3 · · · v n , the only way we can fail to have w ′ ⊳ i w is if v i = a and a < v i+1 < b. But this is impossible by Lemma 4.7(d). Transition graphs Assume v is maximal with respect to < Q . Using Theorem 3.4, it is not hard to show that v = v 1 c 1 c 2 · · · c k a 1 b 1 a 2 b 2 · · · a l b l for some numbers where k, l ∈ N and c 1 < c 2 < · · · < c k < a 1 < a 2 < · · · < a l and a i < −b i for i ∈ [l]. If v 1 < 0 then vt 0 → v is the unique edge incident to v in − → L n , and it follows from Theorem 3.4 that either k = 0 or v 1 < c 1 , and in turn that v = α max (M ) and vt 0 = α ′ max (M ′ ). The following theorem confirms that − → L n is indeed a bipartite graph on the vertex set A n ⊔ Q n . If v is maximal with respect to < Q then v = α ′ max (M ) and evidently u = α ′ max (P ). If v is minimal with respect to < Q then v = α ′ min (M ) and w = α ′ min (Q). Lemma 5.1 therefore implies that u ≤ Q α ′ max (P ) ∈ Q − n and w ≥ Q α ′ min (Q) ∈ Q − n so u, w ∈ Q − n . Transition graphs Let S(w) = S 1 (w) and T (w) = T + 1 (w) for w ∈ C n , where S j (w) and T ± j (w) are as in (2.1). If b = w 1 > 0 then we can also write S(w) = {t ab w : a ∈ [b − 1] and w ⋖ t ab w} ⊔ {wt 0 } and T (w) = {t bc w : c ∈ [b + 1, n + 1] and w ⋖ t bc w}. Transition graphs Proof. Suppose w ⊳ i w ′ and w ⋖ t ab w. Then for some j ∈ [2, n] we have w j = −a and no e ∈ {w 2 , w 3 , . . . , w j−1 } has a < −e < b. We can write w i w i+1 w i+2 = zxy where x < y < z and 0 < z < −x. The only way we can fail to have t ab w ⊳ i t ab w ′ is if −b < w i+1 < −a = w i+2 , but this would contradict w ⋖ t ab w. Since the relation ⊳ i is length-preserving, we also have w ′ ⋖ t ab w ′ . Transition graphs Suppose w ′ ⊳ i w and w ⋖ t bc w. Then for some j ∈ [2, n] we have w j = c and no e ∈ {w 2 , w 3 , . . . , w j−1 } has b < e < c. We can write w i w i+1 w i+2 = yzx where x < y < z and 0 < z < −x. The only way we can fail to have t bc w ′ ⊳ i t bc w is if w i+1 = c > w i > b, but this would contradict w ⋖ t bc w. Since the relation ⊳ i is length-preserving, we have w ′ ⋖ t bc w ′ . Proof. Since u ⋖ t ab u, we must have u j = −a for some j ∈ [2, n] , and no numbers between −b and −a can appear in u 2 u 3 · · · u j−1 . There can be no blocks {x, y} ∈ P with x < a < y: since P ∈ NCSQ − (n, b), such a block necessarily satisfies x = −y < a < y < b, and then Lemma 4.7(c)(iii) contradicts the previous sentence. This is enough to conclude that M ∈ NCSP(n), and that e = a is the largest number with {±e} ∈ P . Assume u = α ′ max (P ) is maximal under < Q . We must then have j = 2 and we can write Transition graphs are the blocks in P with 0 < a i < b i , and where −a < c 1 < · · · < c k < 0 < a 1 < · · · < a l . Hence Transition graphs and it is easy to see that Transition graphs with a i < a as P is noncrossing. Therefore t ab u ∈ A M . If u is not maximal under < Q , then it follows from Lemma 5.4(a) that we still have t ab u ≤ A α max (M ) so again t ab u ∈ A M . Once we know that t ab u ∈ A M , the claim that u → t ab u is an edge in − → L n holds by definition. Transition graphs Theorem 5.7. Let u, w ∈ Q − n and v ∈ C n with w 1 < n. Transition graphs The previous theorem does not apply when w ∈ Q − n has w 1 = n, since then T (w) consists of the single element (n + 1)w 2 w 3 · · · w n n ∈ C n+1 but there are no edges v → w in − → L n . Transition graphs Corollary 5.8. A vertex w ∈ A n ⊔ Q n is a source in − → L n if and only if w 1 = n, in which case w ∈ Q − n . Thus the sources in − → L n are the elements nv 1 v 2 · · · v n−1 ∈ C n where v 1 v 2 · · · v n−1 ∈ A n−1 . Transition graphs Proof. By definition no element in A n ⊔ Q + n is a source in − → L n . Theorem 3.4 implies that no atom v ∈ A n has v 1 = n, and that if v ∈ Q + n then v i = −n for some i ∈ [n]. It follows that an odd quasi-atom w ∈ Q − n with w 1 = n cannot be the target of an edge v → w in Transition graphs . It remains to show that w is not a source in − → L n . By Theorem 5.7, it suffices to check that T (w) = ∅. Since M ′ (w) has no blocks {a, b} with a < w 1 < b, the interval [w 1 + 1, n] must be a non-empty union of blocks in M ′ (w). It follows that 0 < w 1 < w i for some i ∈ [2, n], and if i is minimal with these properties then wt 1i ∈ T (w), so T (w) = ∅ as desired. Proof. Since w → wt 0 is always an edge in − → L n if w ∈ Q − n , this follows from the definition of − → L n . Transition graphs For integers 0 < m < n, write ↑ n m : C m → C n for the transformation Transition graphs Recall that, by convention, C 0 is the set consisting of just the empty word ∅. We define ↑ n 0 to be the map ∅ → n · · · 321 and view − → L 0 as the graph with no edges and a single vertex ∅. First define − → L m,n for 0 ≤ m < n to be the directed graph given by replacing each vertex in − → L m by its image under ↑ n m . One may interpret ↑ n+1 n as the identity map C n → C n ֒→ C n+1 and identify − → L n,n+1 with − → L n . Next define − → G n to be the graph given by the disjoint union Transition graphs with these additional edges: for each m ∈ [n] and w ∈ A m−1 , include an edge from the sink ↑ n+1 m−1 (w 1 w 2 · · · w m−1 ) = (n + 1) · · · (m + 2)(m + 1)w 1 w 2 · · · w m−1 m (5.5) Transition graphs in − → L m−1,n+1 to the source ↑ n+1 m (mw 1 w 2 · · · w m−1 ) = (n + 1) · · · (m + 3)(m + 2)mw 1 w 2 · · · w m (m + 1) Transition graphs of an odd quasi-atom in − → L m . All other vertices in − → L m,n+1 or − → G n are even. Since every source in − → L m is an odd quasi-atom and every sink is an atom, the resulting division into even and odd vertices affords a bipartition of − → G n . Recall that w C n = 1 2 3 · · · n and w A n = (n + 1)n · · · 321 and δ n = (n, n − 1, . . . , 3, 2, 1). Transition graphs Theorem (Theorem 1.6). It holds thatĜ w C n = G w A n = S δn . Proof. Let w ∈ C n . For j ∈ [n], define T ± j (w) and S j (w) as in (1.1), and recall that T (w) = T + 1 (w) and S(w) = S 1 (w). If 0 ≤ m ≤ n and r = n − m + 1 andw = ↑ n+1 m (w) ∈ C n , then evidently G v . Transition graphs Since ↑ n+1 0 (∅) = (n + 1)n · · · 321 = w A n is the unique source in − → G n and since the set of sinks in − → G n is precisely ↑ n+1 n (A n ) = A n , we haveĜ w C n = G w A n . The latter is S δn by Theorems 1.3 and 2.5. Transition graphs Corollary (Theorem 1.2). It holds that |R(w C n )| = | SYT(δ n )| = |R(w A n )|. Transition graphs Proof. Let N = n+1 2 = deg(S δn ) =l(w C n ). Then 2 N |R(w C n )| = [x 1 x 2 · · · ]Ĝ w C n = [x 1 x 2 · · · ]S δn , which is the number of marked standard tableaux of shape δ n . Since this number is evidently 2 N | SYT(δ n )|, and since we have already seen that | SYT(δ n )| = |R(w A n )|, the result follows. Transition graphs 6 Future directions Geometry There are geometric connections in type A for which we do not know type C analogues. The type A involution Stanley symmetric functionF w is a limit of involution Schubert polynomials, which are known to represent the cohomology classes of the orbit closures of O n (C) acting on the type A complete flag variety. One can also define type C involution Schubert polynomials, which represent cohomology classes on the type C isotropic flag variety insofar as they are positive integer
{'paper_id': '119637966', 'title': 'Stanley symmetric functions for signed involutions', 's2_url': 'https://api.semanticscholar.org/CorpusID:119637966', 'source': 'S2ORC'}