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.


2 Answers 2


(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)$.

  • $\begingroup$ I think the last letter is easier. $\endgroup$ Nov 11, 2015 at 13:31
  • $\begingroup$ Okay, I will try to clarify that now... $\endgroup$ Nov 11, 2015 at 14:00
  • $\begingroup$ Done, finally... Let me know whether something is unclear or plainly wrong :-) $\endgroup$ Nov 11, 2015 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$ Nov 11, 2015 at 19:11
  • $\begingroup$ Is this the exchange condition you meant? $\endgroup$ Nov 11, 2015 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.

  • $\begingroup$ Should that map in #3 be to $(Q\setminus (S\setminus T), w, T)$? $\endgroup$ Nov 10, 2015 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$ Nov 10, 2015 at 12:18
  • $\begingroup$ Do you happen to see whether the decomposition in #2 always exists? $\endgroup$ Nov 10, 2015 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$ Nov 10, 2015 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$ Nov 10, 2015 at 16:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .