Let $Q$ be a word in the generators of some Coxeter group, and consider a subword $R$ (not necessarily reduced, though I might want $Q$ to be).

Define the greedy or Demazure product of $R$ as follows: while multiplying generators left-to-right, insist on only going upward in Bruhat order; any letter in $R$ that would take you downward should be skipped over.

For abstruse geometric reasons, I want to divide the set of all $2^{|Q|}$ subwords of $Q$ into equivalence classes $\{R\}$, according to (the greedy product of $R$, the locations in $Q$ of the skipped letters). That is, for each pair $(w \in W, S\subseteq Q)$, I consider the set of $R$ with greedy product $w$ and skip locations at exactly $S$.

For example, each $(w,\emptyset)$ corresponds to the class of reduced subwords with (ordinary) product $w$, a well-studied object (e.g. in my paper with Ezra Miller on subword complexes). If $Q=121$ in $S_3$, the $2^3$ subwords break into a singleton for each $w$, except for $\{1--,--1\}$ and $\{1-\underline{1}\}$ for $w=(12)$, where the underlined $\underline{1}$ is the only skipped letter.

Has anyone studied these equivalence classes of subwords before?

If so, are standard results like the Coxeter exchange condition known for them?

EDIT: here's a larger example, hopefully to make clearer the equivalence relation. Let $Q = 1231$, a word in the generators of $S_4$. Then the classes are $$ ---- $$ $$ 1---, \quad ---1 $$ $$ -2-- $$ $$ --3- $$ $$ 12-- $$ $$ 1-3-, \quad --31 $$ $$ 1--\underline{1} $$ $$ -23- $$ $$ -2-1 $$ $$ 123- $$ $$ 12-1 $$ $$ 1-3\underline{1} $$ $$ -231 $$ $$ 1231 $$ where I've underlined the skip positions.


(in contrary to what I thought first,) here is a proof that the "exchange condition" holds in the following sense. It is based on the root configuration in http://arxiv.org/abs/1111.3349 [1].

Let $(W,S)$ be a Coxeter system, $Q \in S^*$ a word in $S$, $w \in W$, $P$ a subword of $Q$. We everywhere consider subwords as being indexed by positions in $Q$, so if $Q = ss$, then the two subwords $s{-}$ und ${-}s$ are considered to be different.

Let $(Q,w,P)$ be the set of subwords $X$ of $Q \setminus P$ such that the complement $R = Q \setminus X$ has greedy product $Dem(R) = w$ and the skips in the greedy product are in exactly the positions in $P$, we call these positions the greedy skips. (So this is the situation Allen introduced in the question, except that he did not mention the part about the complement.)

Let $D(Q,w,P)$ be the simplicial complex with facets given by $(Q,w,P)$. This complex is clearly pure since every facet contains exactly $len(Q)-\ell_S(w)-len(P)$ many letters.

Observation 1: For every facet $X$ of $D(Q,w,P)$, the disjoined union $X \cup (P\setminus P')$ is also a facet of $D(Q,w,P')$ for $P' \subseteq P$.

Construction 2: The root configuration in Definition 3.1 in [1] is given for a facet $X$ of $D(Q,w,\{\})$ as follows. Associate to each letter $q_i$ in $Q$ a root $R(X,i)$ by applying the prefix up to position $q_{i-1}$ of the word $Q \setminus X$ of $w$ to the simple root $\alpha_{q_i}$. In my example $Q = tsstst$, the element $w = sts = tst$ and the facet $t{-}s{--}t$ with complement ${-}s{-}ts{-}$ which is a reduced word for $w$, the root configuration is $$ R(X,\cdot) =\beta,\alpha,s(\alpha),s(\beta),st(\alpha),sts(\beta) $$ where $\alpha = \alpha_s, \beta = \alpha_t$ which is equal to $$ 23,12,-12,13,23,-12 $$ where I write $12$ for $\alpha$, $23$ for $\beta$, and $13$ for $\alpha+\beta$.

Observation 3: The collections of roots of the root configuration of the complement of $X$ is exactly the inversion set of $w$ (in particular, that's all positive roots).

Observation 4: The negative roots in the root configuration could be used as greedy skips. This also means that picking a a facet $X$ of $D(Q,w,\{\})$, and a subset $P$ of the letters for which the root configuration is negative results in a facet $X \setminus P$ of $D(Q,w,P)$.

Observation 5: If a root in the root configuration is negative, than all appearances of the same root "to the right" are also negative. Analogously, if a root there is positive then all appearances "to the left" are positive.

Statement 6: The simplicial complex $D(Q,w,P)$ is vertex-decomposable has the exchange property in the following sense.

Let $q_1$ be the first letter in $Q$ If $\ell_S(q_1w) < \ell_S(w)$, then for any facet $X$ of $D(Q,w,P)$, there exists a facet $Y$ of $D(Q,w,P)$ containing $X \setminus q_1$.


Consider $X' = X \cup P$ as a facet of $D(Q,w,\{\})$ as in Observation 1. We now know from Observation 4 that $P$ is a subset of the negative roots in the root configuration of $X'$. We know from $\ell_S(q_1w) < \ell_S(w)$ that $\alpha_{q_1}$ is in the inversion set of $w$ which is by Observation 3 equal to the root configuration of the complement of $X$. This provides to obtain $Y'$ by "flipping" $q_1$ in $X'$ to the unique position not in $X'$ for which the root configuration is given by the same simple root $\alpha_{q_1}$. Call this position $q_i$ and we have $Y' = (X' \setminus q_1 ) \cup q_i$.

It remains to show that $Y'$ contains $P$ and that all roots in the root configuration of $Y'$ at positions in $P$ are negative, since Observation 1 then tells us that $Y = Y' \setminus P$ is the desired facet of $D(Q,w,P)$.

Lemma 3.3(3) in [1] tells us how the root configuration changes when doing the flip $X'$ to $Y'$. This is indeed easy to see: the roots in the root configuration after $q_i$ are not changed, while we apply $s_{q_1}$ to all the roots before that, $R(Y',j) = R(X',j)$ for $j>i$, and $R(Y',j) = s_{q_1}\big(R(X',j)\big)$ for $j \leq i$.

Since we only care about the signs, observe that $s_{q_1}$ does only affect the sign of $\alpha_{q_1}$, while all other signs are unchanged. But since $R(X',i)$ is positive (and ind.eed in equal to $\alpha_{q_1}$), Observations 4 and 5 finally tell us that $P$ is a subset of the letters for which the root configuration of $Y'$ is negative. As desired, we conclude that $Y=Y' \setminus P$ is a facet of $D(Q,w,P)$.

| cite | improve this answer | |
  • $\begingroup$ I think the last letter is easier. $\endgroup$ – Allen Knutson Nov 11 '15 at 13:31
  • $\begingroup$ Okay, I will try to clarify that now... $\endgroup$ – Christian Stump Nov 11 '15 at 14:00
  • $\begingroup$ Done, finally... Let me know whether something is unclear or plainly wrong :-) $\endgroup$ – Christian Stump Nov 11 '15 at 15:15
  • $\begingroup$ I think this may likely count as an answer saying "no, these weren't considered before, and no, the exchange condition wasn't known for them." $\endgroup$ – Allen Knutson Nov 11 '15 at 19:11
  • $\begingroup$ Is this the exchange condition you meant? $\endgroup$ – Christian Stump Nov 11 '15 at 19:13

These are several comments rather than an answer:

As you write, let $(Q,w,S)$ denote all subwords of $Q$ whose greedy product is $w$ with positions $S$ skipped. I moreover write $(Q,w)$ for w in the Artin group to be all subwords of $Q$ that are words for $w$.

  1. In the terminology of http://arxiv.org/abs/1111.3349, $(Q,w,S)$ consists of all subwords in $(Q,w,\{\})$ for which the root configurations at positions $S$ are negative.

  2. In our paper http://arxiv.org/abs/1503.00710, we briefly mention subword complexes for Artin groups around Example 2.6.14. Observe that in this example, the Artin subword complex $(Q,ssts=stst=tstt)$ is the union $(Q,sts=tst,\{6\}) \cup (Q,sts=tst,\{3\})$ for $Q=tsstst$ and $s = (12), t = (23)$ in $\mathcal{S}_3$. The subwords we consider are then indexed by positions $$--sts\underline{t}$$ $$-s-ts\underline{t}$$ $$-s\underline{s}ts-$$ $$t-st-\underline{t}$$ $$ts-t-\underline{t}$$

    where I underlined the skips in the different words for $w$ when applying the greedy product to it. One then gets that elements number 1,2,4,5 form your class $(Q,sts=tst,\{6\})$, while element number 3 is your class $(Q,sts=tst,\{3\})$.

  3. There is an injective map $\iota$ from $(Q,w,S)$ to $(Q,w,T)$ for a subset $T \subseteq S$ which is "forget about the letters in $S\setminus T$". Given on the other hand a subword in $(Q,w,\{\})$, you can compute the root configuration and check which roots are negative. For any subset of those, this element is then in the image of the above map.

| cite | improve this answer | |
  • $\begingroup$ Should that map in #3 be to $(Q\setminus (S\setminus T), w, T)$? $\endgroup$ – Allen Knutson Nov 10 '15 at 11:04
  • $\begingroup$ You can also do that if you prefer. But since $(Q \setminus(S \setminus T),w,T)$ is "contained" in $(Q,w,T)$, you can as well send it to $(Q,w,T)$. I wanted to use the latter to emphasize that you can embedd everything into $(Q,w,\{\})$, and for an element in $(Q,w,\{\})$, you can recover all $S$ mapping onto this element. (Or am I overseeing some obvious problem?) $\endgroup$ – Christian Stump Nov 10 '15 at 12:18
  • $\begingroup$ Do you happen to see whether the decomposition in #2 always exists? $\endgroup$ – Christian Stump Nov 10 '15 at 12:19
  • $\begingroup$ So in this theory, you look at subwords that are Artin-reduced but not necessarily Coxeter-reduced? Is it clear that they should all have the same greedy product? I guess you can always decompose according to (greedy product, skip locations), but maybe the pieces won't be balls? I don't understand what "exists" means. $\endgroup$ – Allen Knutson Nov 10 '15 at 15:53
  • $\begingroup$ There is no reduction for Artin words. I believe that the greedy product only depends on a word up to braid relations (as I think it only depends on the "colored inversion sequence" r1,s1(r2),s1s2(r3),... for a word s1,s2,s3,... with corresponding simple roots r1,r2,r3,...). $\endgroup$ – Christian Stump Nov 10 '15 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.