Printer Friendly

EL-labelings and canonical spanning trees for subword complexes.

Subword complexes on Coxeter groups were defined and studied by A. Knutson and E. Miller in the context of Grobner geometry of Schubert varieties [KM04, KM05]. Type A spherical subword complexes can be visually interpreted using pseudoline arrangements on primitive sorting networks. These were studied by V. Pilaud and M. Pocchiola [PP12] as combinatorial models for pointed pseudotriangulations of planar point sets [RSS08] and for multitriangulations of convex polygons [PS09]. These two families of geometric graphs extend in two different ways the family of triangulations of a convex polygon.

The greedy flip algorithm was initially designed to generate all pointed pseudotriangulations of a given set of points or convex bodies in general position in the plane [PV96, BKPS06]. It was then extended in [PP12] to generate all pseudoline arrangements supported by a given primitive sorting network. The key step in this algorithm is to construct a spanning tree of the flip graph on the combinatorial objects, which has to be sufficiently canonical to be visited in polynomial time per node and polynomial working space.

In the present paper, we study natural edge lexicographic labelings of the increasing flip graph of a subword complex on any finite Coxeter group. As a first line of applications of these EL-labelings, we obtain canonical spanning trees of the flip graph of any subword complex. We provide alternative descriptions of these trees based on their close relations to greedy facets, which are defined and studied in this paper. Moreover, searching these trees provides an efficient algorithm to generate all facets of the subword complex. For type A spherical subword complexes, the resulting algorithm is precisely that of [PP12], although the presentation is quite different.

The second line of applications of the EL-labelings concerns combinatorial properties ensuing from EL-shellability [Bjo80, BW96]. Indeed, when the increasing flip graph is the Hasse diagram of the increasing flip poset, this poset is EL-shellable, and we can compute its Mobius function. These results extend recent work of M. Kallipoliti and H. Muhle [KM12] on EL-shellability of N. Reading's Cambrian lattices [Rea06, Rea07], which are, for finite Coxeter groups, increasing flip posets of specific subword complexes studied by C. Ceballos, J.-P. Labbe and C. Stump [CLS13] and by the authors in [PS11].

This extended abstract presents the results and the main ideas of the paper [PS12]. We refer the reader to this paper for further details, examples, and all proofs which we omit here due to limited space.

1 Edge labelings of graphs and posets

In [Bjo80], A. Bjorner introduced EL-labelings of partially ordered sets to study topological properties of their order complexes. These labelings are edge labelings of the Hasse diagrams of the posets with certain combinatorial properties. In this paper, we consider edge labelings of finite, acyclic, directed graphs which might differ from the Hasse diagrams of their transitive closures.

1.1 ER-labelings of graphs and associated spanning trees

Let [member of] := (V, E) be a finite, acyclic, directed graph. For u, [upsilon] [member of] V, we write u [right arrow] [upsilon] if there is an edge from u to [upsilon] in G, and u [right arrow] [upsilon] if there is a path u = [x.sub.1] [right arrow] [x.sub.2] [right arrow] ... [right arrow] [x.sub.l] [right arrow] [x.sub.l+1] = [upsilon] from u to [upsilon] in G (this path has length l). The interval [u, [upsilon]] in G is the set of vertices w [member of] V such that u [right arrow] w [right arrow] [upsilon].

An edge labeling of G is a map [lambda]: E [right arrow] N. It induces a labeling of any path p: [x.sub.1] [right arrow] [x.sub.2] [right arrow] ... [right arrow] [x.sub.l] [right arrow] [x.sub.l+1] given by [lambda](p) := [lambda]([x.sub.1] [right arrow] [x.sub.2]) ... [lambda] ([x.sub.l] [right arrow] [x.sub.l+1]). The path p is [lambda]-rising (resp. [lambda]-falling) if [lambda](p) is strictly increasing (resp. weakly decreasing). The labeling [lambda] is an edge rising labeling of G (or ER-labeling for short) if there is a unique [lambda]-rising path p between any vertices u, [upsilon] [member of] V with u [right arrow] [upsilon].

Remark 1.1 (Spanning trees) Let u, [upsilon] [member of] V, and [lambda]: E [right arrow] N be an ER-labeling of G. Then the union of all [lambda]-rising paths from u to any other vertex of the interval [u, [upsilon]] forms a spanning tree of [u, [upsilon]], rooted at and directed away from u. We call it the [lambda]-source tree of [u, [upsilon]] and denote it by [T.sub.[lambda]] ([u, [upsilon]]). Similarly, the union of all [lambda]-rising paths from any vertex of the interval [u, [upsilon]] to [upsilon] forms a spanning tree of [u, [upsilon]], rooted at and directed towards [upsilon]. We call it the [lambda]-sink tree of [u, [upsilon]] and denote it by [T.sub.[lambda]] ([u, [upsilon]]). In particular, if G has a unique source and a unique sink, this provides two canonical spanning trees [T.sub.[lambda]] (G) and [T.sup.*.sub.[lambda]] (G) for the graph G itself.

Example 1.2 (Cube) Consider the 1-skeleton [[??].sub.d] of the d-dimensional cube [[0,1].sup.d], directed from vertex 0 := (0, ..., 0) to vertex 1 := (1, ..., 1). Its vertices are the elements of [{0,1}.sup.d] and its edges are the pairs of vertices which differ in a unique position. Note that [epsilon] := ([[epsilon].sub.1], ..., [[epsilon].sub.d]) [right arrow] [epsilon]' := ([[epsilon]'.sub.1], ..., [[epsilon]'.sub.d]) if and only if [[epsilon].sub.k] [less than or equal to] [[epsilon]'.sub.k] for all k [member of] [d].

For any edge [epsilon] [right arrow] [epsilon]' of [[??].sub.d], let [lambda]([epsilon] [right arrow] [epsilon]') denote the unique position in [d] where [epsilon] and [epsilon]' differ. Then the map [lambda] is an ER-labeling of [[??].sub.d]. If [epsilon] [member of] [{0,1}.sup.d]\0, then the father of [epsilon] in [T.sub.[lambda]] ([[??].sub.d]) is obtained from [epsilon] by changing its last 1 into a 0. Similarly, if [epsilon] [member of] [{0,1}.sup.d]\1, then the father of [epsilon] in [T.sup.*.sub.[lambda]] ([[??].sub.d]) is obtained from [epsilon] by changing its first 0 into a 1. See Figure 1.

1.2 EL-labelings of graphs and posets

Although ER-labelings of graphs are sufficient to produce canonical spanning trees, we need the following extension for further combinatorial properties. The labeling [lambda]: E [right arrow] N is an edge lexicographic labeling of G (or EL-labeling for short) if for any vertices u, [upsilon] [member of] V with u [right arrow] [upsilon],

(i) there is a unique [lambda]-rising path p from u to [upsilon], and

(ii) its labeling [lambda](p) is lexicographically first among the labelings [lambda](p') of all paths p' from u to [upsilon].

For example, the ER-labeling of the 1-skeleton of the cube [[??].sub.d] presented in Example 1.2 is in fact an EL-labeling. Remember now that one can associate a finite poset to a finite acyclic directed graph and vice versa. Namely,

(i) the transitive closure of a finite acyclic directed graph G = (V, E) is the finite poset (V, [right arrow]);

(ii) the Hasse diagram of a finite poset P is the finite acyclic directed graph whose vertices are the elements of P and whose edges are the cover relations in P, i.e. u [right arrow] [upsilon] if u [<.sub.P] [upsilon] and there is no w [member of] P such that u [<.sub.P] w [<.sub.P] [upsilon].

The transitive closure of the Hasse diagram of P always coincides with P, but the Hasse diagram of the transitive closure of G might as well be only a subgraph of G. An EL- labeling of the poset P is an EL-labeling of the Hasse diagram of P. If such a labeling exists, then the poset is called EL-shellable.

As already mentioned, A. Bjorner [Bjo80] originally introduced EL-labelings of finite posets to study topological properties of their order complex. In particular, they provide a tool to compute the Mobius function of the poset. Recall that the Mobius function of the poset P is the map [mu]: P x P [right arrow] Z defined recursively by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

When the poset is EL-shellable, this function can be computed as follows.

Proposition 1.3 ([BW96, Proposition 5.7]) Let [lambda] be an EL-labeling of the poset P. For every u, [upsilon] [member of] P with u [[less than or equal to].sub.P] [upsilon], we have

[mu](u, [upsilon]) = [even.sub.[lambda]] (u, [upsilon]) - [odd.sub.[lambda]] (u, [upsilon]),

where [even.sub.[lambda]] (u, [upsilon]) (resp. [odd.sub.[lambda]] (u, [upsilon])) denotes the number of even (resp. odd) length [lambda]-falling paths from u to [upsilon] in the Hasse diagram of P.

Example 1.4 (Cube) The directed 1-skeleton [[??].sub.d] of the d-dimensional cube [[0,1].sup.d] is the Hasse diagram of the boolean poset. The edge labeling [lambda] of [[??].sub.d] of Example 1.2 is thus an EL-labeling of the boolean poset. Moreover, for any two vertices [epsilon] [right arrow] [epsilon]' of [[??].sub.d], there is a unique [lambda]- falling path between [epsilon] and [epsilon]', whose length is the Hamming distance [delta]([epsilon], [epsilon]') := [absolute value of {k [member of] [d]|[[epsilon].sub.k] = [[epsilon]'.sub.k]}]. The Mobius function is thus given by [mu]([epsilon], [epsilon]') = [(-1).sup.[delta]([epsilon],[epsilon]')] if [epsilon] [right arrow] [epsilon]' and [mu]([epsilon], [epsilon]') = 0 otherwise. In particular, [mu](0,1) = [(- 1).sup.d].

2 Subword complexes on Coxeter groups

2.1 Subword complexes

We consider a finite Coxeter system (W,S), with root system [PHI] and simple roots {[[alpha].sub.1], ..., [[alpha].sub.n]}. We fix a word Q := [q.sub.1][q.sub.2] ... [q.sub.m] on the generators of S, and an element [rho] [member of] W. Background on Coxeter groups can be found in [Hum90].

A. Knutson and E. Miller [KM04] define the subword complex SC (Q, [rho]) to be the simplicial complex of those subwords of Q whose complements contain a reduced expression for [rho] as a subword. A vertex of SC (Q, [rho]) is a position of a letter in Q. We denote by [m] := {1,2, ..., m} the set of positions in Q. A facet of SC (Q, [rho]) is the complement of a set of positions which forms a reduced expression for [rho] in Q. We denote by F(Q, [rho]) the set of facets of SC (Q, [rho]).

Example 2.1 Consider the type A Coxeter group [[??].sub.4] generated by {[[tau].sub.1], [[tau].sub.2], [[tau].sub.3]}, where [[tau].sub.i] := (i i + 1). Consider [Q.sup.ex] := [[tau].sub.2][[tau].sub.3][[tau].sub.1][[tau].sub.3][[tau].sub.2][[tau].sub.1][[ tau].sub.2][[tau].sub.3][[tau].sub.1] and [[rho].sup.ex] := [4, 1, 3, 2]. The reduced expressions of [[rho].sup.ex] are [[tau].sub.2][[tau].sub.3][[tau].sub.2][[tau].sub.1], [[tau].sub.3][[tau].sub.2][[tau].sub.3][[tau].sub.1], and [[tau].sub.3][[tau].sub.2][[tau].sub.1][[tau].sub.3]. Therefore, the facets of the subword complex SC([Q.sup.ex], [[rho].sup.ex]) are {1, 2, 3, 5, 6}, {1, 2, 3, 6, 7}, {1, 2, 3, 7, 9}, {1, 3, 4, 5, 6}, {1, 3, 4, 6, 7}, {1, 3, 4, 7, 9}, {2, 3, 5, 6, 8}, {2, 3, 6, 7, 8}, {2, 3, 7, 8, 9}, {3, 4, 5, 6, 8}, {3, 4, 6, 7, 8}, and {3, 4, 7, 8, 9}. We will use this example throughout this paper to illustrate further notions.

Remark 2.2 There is a natural reversal operation on subword complexes. Namely,

SC ([q.sub.m] ... [q.sub.1], [[rho].sup.-1]) = {{m + 1 - i|i [member of] I}|I [member of] SC ([q.sub.1] ... [q.sub.m], [rho])}.

We will use this operation to relate positive and negative labelings, facets and trees.

2.2 Inductive structure

We denote by [Q.sub.[??]] = [q.sub.2] ... [q.sub.m] and [Q.sub.[??]] := [q.sub.1] ... [q.sub.m-1] the words on S obtained from Q = [q.sub.1] ... [q.sub.m] by deleting its first and last letters respectively. We denote by X * z := {X [union] z|X [member of] X} the join of a collection X of subsets of Z with an element z [member of] Z. We let l([rho]) denote the length of [rho] [member of] W and we write [rho] [??] Q when Q contains a reduced expression of [rho], i.e. when SC(Q,[rho]) is non-empty.

We can decompose inductively the facets of the subword complex SC(Q, [rho]) according on whether or not they contain the last letter of Q. Denoting by [epsilon] the empty word and by e the identity of W, we have F([epsilon], e) = {0} and F([epsilon], [rho]) = 0 if [rho] [not equal to] e. For a non-empty word Q on S, the set F(Q, [rho]) is given by

(i) F([Q.sub.[??]], [rho][q.sub.m]) if m appears in none of the facets of SC(Q, [rho]) (equivalently if [rho] [??] [Q.sub.[??]]);

(ii) F([Q.sub.[??]], [rho]) * m if m appears in all the facets of SC(Q, [rho]) (equivalently if l([rho][q.sub.m]) > l([rho]));

(iii) F([Q.sub.[??]], [rho][q.sub.m]) [union] (F ([Q.sub.[??]], [rho]) * m) otherwise.

By reversal (see Remark 2.2), there is also a similar inductive decomposition of the facets of the subword complex SC(Q, [rho]) according on whether or not they contain the first letter of Q. Although we will only use these decompositions for the facets F(Q, [rho]), they extend to the whole subword complex SC(Q, [rho]) and are used to obtain the following result.

Theorem 2.3 ([KM04, Corollary 3.8]) The subword complex SC (Q, [rho]) is either a simplicial sphere or a simplicial ball.

2.3 Flips and roots

Let I be a facet of SC(Q, [rho]) and i be a position in I. If there exists a facet J of SC(Q, [rho]) and a position j [member of] J such that I \ i = J \ j, we say that I and J are adjacent facets, that i is flippable in I, and that J is obtained from I by flipping i. Note that, if i is flippable, then J and j are unique by Theorem 2.3. We denote by G(Q, p) the graph of flips, whose vertices are the facets of SC(Q, [rho]) and whose edges are pairs of adjacent facets. That is, G(Q, [rho]) is the ridge graph of the simplicial complex SC(Q, [rho]). This graph is connected by Theorem 2.3. It can moreover be naturally oriented by the direction of the flips as follows. Let I and J be two adjacent facets of SC(Q, [rho]) with I \ i = J \ j. We say that the flip from I to J is increasing if i < j. We then orient the corresponding edge of G(Q, [rho]) from I to J.

Example 2.4 Figure 2 shows the increasing flip graph [member of] ([Q.sup.ex], [[rho].sup.ex]) for the subword complex SC ([Q.sup.ex], [[rho].sup.ex]) of Example 2.1. The facets of SC ([Q.sup.ex], [[rho].sup.ex]) appear in lexicographic order from left to right.

Remark 2.5 The increasing flip graph of SC (Q, [rho]) was already considered by A. Knutson and E. Miller [KM04, Remark 4.5]. It carries various combinatorial informations about the subword complex SC(Q, [rho]). In particular, since the lexicographic order on the facets of SC(Q, [rho]) is a shelling order for SC (Q, [rho]), the h-vector of the subword complex SC(Q, [rho]) is the in-degree sequence of the increasing flip graph G(Q, [rho]).

We consider flips as elementary operations on subword complexes. In practice, the necessary information to perform flips in a facet I of SC (Q, [rho]) is encoded in its root function r(I, *): [m] [right arrow] [PHI] defined by

r(I, k) := [PI][Q.sub.[k-1]\I]([[alpha].sub.qk]),

where [PI][Q.sub.X] denotes the product of the reflections [q.sub.x] [member of] Q for x [member of] X. The root function was introduced by C. Ceballos, J.-P. Labbe and C. Stump [CLS13] and its main properties can be found in [CLS13, Lemmas 3.3 and 3.6]. Essentially, an element i of a facet I is flippable if and only if r(I, i) [member of] {[+ or - ][beta]\[beta] [member of] inv([rho])}, and then i flips to the unique position j [not member of] I such that r(I,j) [member of] {[+ or -]r(I, i)}. Moreover, r(I, i) = r(I, j) [member of] [[PHI].sup.+] if i < j (increasing flip), while r(I, i) = -r(I, j) [member of] [[PHI].sup.-] if i > j (decreasing flip). The root configuration of the facet I is the multiset R(I) = {r(I, i)|i flippable in I}}. We extensively studied root configurations in [PS11] in the construction of brick polytopes for spherical subword complexes.

3 EL-labelings and spanning trees for the subword complex

3.1 EL-labelings of the increasing flip graph

We now define two natural edge labelings of the increasing flip graph G(Q, [rho]). Let I and J be two adjacent facets of SC(Q, [rho]), with I \ i = J \ j and i < j. We label the edge I [right arrow] J of G(Q, [rho]) with the positive edge label p(I [right arrow] J) = i and with the negative edge label n(I [right arrow] J) := j. We call p: E(G(Q, [rho])) [right arrow] [m] the positive edge labeling and n: E(G(Q, [rho])) [right arrow] [m] the negative edge labeling of the increasing flip graph G(Q, [rho]). The terms "positive" and "negative" emphasize the fact that the roots r(I, p (I [right arrow] J)) and r(J, n (I [right arrow] J)) are always positive and negative roots respectively. The positive and negative edge labelings are clearly reverse to one another (see Remark 2.2).

Example 3.1 Consider the subword complex SC([Q.sup.ex], [[rho].sup.ex]) of Example 2.1. We have represented on Figure 2 the positive and negative edge labelings p and n. Since we have represented the graph G([Q.sup.ex], [p.sup.ex]) such that the flips are increasing from left to right, each edge has its positive label on the left and its negative label on the right.

Our main result concerns the positive and negative edge labelings of the increasing flip graph.

Theorem 3.2 The positive edge labeling p and the negative edge labeling n are both EL-labelings of the increasing flip graph.

For Cambrian lattices, whose Hasse diagrams were shown to be particular cases of increasing flip graphs in [PS11, Section 6], a similar result was recently obtained by M. Kallipoliti and H. Muhle in [KM12].

In Sections 3.2 and 3.3, we present applications of Theorem 3.2 to the construction of canonical spanning trees and to the generation of the facets of the subword complex. Further combinatorial applications of this theorem are also discussed in Section 4.

Before going on, we want to give a very brief idea of the proof of Theorem 3.2. We refer the interested reader to the complete proof in [PS12]. To prove the existence of a p-rising path between any two comparable facets of SC(Q, [rho]), we use a procedure which improves locally a path by restriction of SC (Q, [rho]) to a dihedral parabolic subgroup. The uniqueness and lexicographic property of the p- rising are then obtained from the following proposition.

Proposition 3.3 Let [I.sub.1] [right arrow] ... [right arrow] [I.sub.l+1] be a path of increasing flips, and define [p.sub.k] := p([I.sub.k] [right arrow] [I.sub.k+1]) and [n.sub.k] := n([I.sub.k] [right arrow] [I.sub.k+1]). Then, for all k [member of] [l], we have

min {[p.sub.k], ..., [p.sub.l]} = min ([I.sub.k] \ [I.sub.l+1]) and max {[n.sub.1], ..., [n.sub.k]} = max ([I.sub.k+1] \ [I.sub.1]).

Moreover, the path is p-rising if and only if [p.sub.k] = min([I.sub.k] \ [I.sub.l+1]) for all k [member of] [l], while the path is n-rising if and only if [n.sub.k] = max ([I.sub.k+1] \ [I.sub.1]) for all k [member of] [l].

3.2 Greedy facets

We now characterize the unique source and sink of the increasing flip graph G(Q, [rho]).

Proposition 3.4 The lexicographically smallest (resp. largest) facet of SC (Q, [rho]) is the unique source (resp. sink) of G(Q, [rho]).[right arrow]

We call positive (resp. negative) greedy facet and denote by P(Q, [rho]) (resp. N(Q, [rho])) the unique source (resp. sink) of the graph G(Q, [rho]) of increasing flips. The term "positive" (resp. "negative") emphasizes the fact that P(Q, [rho]) (resp. N(Q, [rho])) is the unique facet of SC(Q, [rho]) whose root configuration is a subset of positive (resp. negative) roots, while the term "greedy" refers to the greedy properties of these facets. The greedy facets P(Q, [rho]) and N(Q, [rho]) are reverse to one another (see Remark 2.2). Namely, N ([q.sub.m] ... [q.sub.1], [[rho].sup.-1]) = {m + 1 - p|p [member of] P ([q.sub.1] ... [q.sub.m], [rho])}.

Example 3.5 The positive and negative greedy facets of the subword complex SC([Q.sup.ex], [[rho].sup.ex]) presented in Example 2.1 are respectively P([Q.sup.ex], [[rho].sup.ex]) = {1, 2, 3, 5, 6} and N([Q.sup.ex], [[rho].sup.ex]) = {3, 4, 7, 8, 9}. They appear respectively as the leftmost and rightmost facets in Figure 2.

We have seen in Theorem 3.2 that for any two facets I, J [member of] F (Q, [rho]) such that I [right arrow] J, there is a p-rising (resp. n-rising) path from I to J. In particular, there is always a p-rising (resp. n-rising) path from P(Q, [rho]) to N(Q, [rho]). It turns out that there is also at least one p-falling (resp. n- falling) path from P(Q, [rho]) to N(Q, [rho]) if the subword complex SC(Q, [rho]) is spherical.

Proposition 3.6 For any spherical subword complex SC(Q, [rho]), there is always a p-falling and an n-falling path from P(Q, [rho]) to N(Q, [rho]).

Note that this proposition fails if we drop the condition that SC(Q, [rho]) is spherical, as illustrated in the subword complex SC ([Q.sup.ex], [[rho].sup.ex]) of Example 2.1.

3.3 Spanning trees

As discussed in Remark 1.1, the edge labelings p and n automatically produce canonical spanning trees of any interval of the increasing flip graph G(Q, [rho]). Since G(Q, [rho]) has a unique source P(Q, [rho]) and a unique sink N (Q, [rho]), we obtain in particular four spanning trees of the graph G(Q, [rho]) itself. The goal of this section is to give alternative descriptions of these four spanning trees.

We call respectively positive source tree, positive sink tree, negative source tree, and negative sink tree, and denote respectively by P(Q, [rho]), [P.sup.*](Q, [rho]), N(Q, [rho]), and [N.sup.*](Q, [rho]), the p-source, p- sink, n-source, and n-sink trees of G(Q, [rho]). The tree P(Q, [rho]) (resp. N(Q, [rho])) is formed by all p-rising (resp. n-rising) paths from the positive greedy facet P(Q, [rho]) to all the facets of SC(Q, [rho]). Both [P.sup.*] (Q, [rho]) and [N.sup.*] (Q, [rho]) are rooted at and directed away from the positive greedy facet P(Q, [rho]). The tree [P.sup.*] (Q, [rho]) (resp. [N.sup.*] (Q, [rho])) is formed by all p-rising (resp. n-rising) paths from all the facets of SC(Q, [rho]) to the negative greedy facet N(Q, [rho]). Both [P.sup.*](Q, [rho]) and [N.sup.*] (Q, [rho]) are rooted at and directed towards the negative greedy facet N (Q, [rho]). Note that the positive source and negative sink trees (resp. the positive sink and the negative source trees) are reverse to one another (see Remark 2.2).

Example 3.7 Consider the subword complex SC([Q.sup.ex], [[rho].sup.ex]) of Example 2.1. Figure 3 represents the trees P([Q.sup.ex], [[rho].sup.ex]), [P.sup.*] ([Q.sup.ex], [[rho].sup.ex]), N ([Q.sup.ex], [[rho].sup.ex]), and [N.sup.*] ([Q.sup.ex], [[rho].sup.ex]). Observe that these four canonical spanning trees of G(Q, [rho]) are all different in general.

We now give a direct description of the father of a facet I in [P.sup.*] (Q, [rho]) and N(Q, [rho]).

Proposition 3.8 Let I be a facet of SC (Q, [rho]). If I [not equal to] N (Q, [rho]), then the father of I in [P.sup.*] (Q, [rho]) is obtained from I by flipping the smallest position in I \ N(Q, [rho]). Similarly, if I [not equal to] P(Q, [rho]), then the father of I in N (Q, [rho]) is obtained from I by flipping the largest position in I P(Q, [rho]).

We now focus on the positive source tree P(Q, [rho]) and on the negative sink tree [N.sup.*] (Q, [rho]), and provide two different descriptions of them. The first is an inductive description of P(Q, [rho]) and [N.sup.*] (Q, [rho]) (see Proposition 3.10). The second is a direct description of the father of a facet I in P(Q, [rho]) and [N.sup.*] (Q, [rho]) in terms of greedy prefixes and suffixes of I (see Proposition 3.11). These descriptions mainly rely on the following property of the greedy facets.

Proposition 3.9 If m is a flippable position of N(Q, [rho]), then N([Q.sub.[??]], [rho][q.sub.m]) is obtained from N(Q, [rho]) by flipping m. Similarly, if 1 is a flippable position of P(Q, [rho]), then P([Q.sub.[??]], [q.sub.1][rho]) is obtained from P(Q, [rho]) by flipping 1 and shifting to the left.

Using Proposition 3.9, we can describe inductively the two trees P(Q, [rho]) and [N.sup.*] (Q, [rho]). The induction follows the induction formulas for the facets F(Q, [rho]) presented in Section 2.2. Remember that we denote the deletion of the first or last letter in Q = [q.sub.1] ... [q.sub.m] by [Q.sub.[??]] = [q.sub.2] ... [q.sub.m] and [Q.sub.[??]] := [q.sub.1] ... [q.sub.m-1] respectively. For a tree T whose vertices are subsets of Z and for an element z [member of] Z, we denote by T * z the tree with a vertex X [union] z for each vertex X of T and an edge X [union] z [right arrow] Y [union] z for each edge X [right arrow] Y of T.

The inductive description of the negative sink tree [N.sup.*] (Q, [rho]) is based on the right induction formula. For the empty word [epsilon], the tree [N.sup.*] ([epsilon], e) is formed by the unique facet 0 of SC([epsilon], e), and the tree [N.sup.*] ([epsilon], [rho]) is empty if [rho] [not equal to] e. Otherwise, [N.sup.*] (Q, [rho]) is obtained as follows.

Proposition 3.10 For a non-empty word Q, the tree [N.sup.*] (Q, [rho]) equals

(i) [N.sup.*] ([Q.sub.[??]], [rho][q.sub.m]) if m appears in none of the facets of SC(Q, [rho]);

(ii) [N.sup.*] ([Q.sub.[??]], [rho]) * m if m appears in all the facets of SC (Q, [rho]);

(iii) the disjoint union of [N.sup.*] ([Q.sub.[??]], [rho][q.sub.m]) and [N.sup.*]([Q.sub.[??]], [rho]) * m, with an additional edge from N ([Q.sub.[??]], [rho][q.sub.m]) to N(Q, [rho]) = N([Q.sub.[??]], [rho]) [union] m, otherwise.[right arrow]

A similar inductive description of the positive source tree P(Q, [rho]) can be obtained from the left induction formula. See [PS12].

We now give a direct characterization of the father of a facet I of SC(Q, [rho]) in the positive source and negative sink trees P(Q, [rho]) and [N.sup.*] (Q, [rho]). This description can be understood in terms of the longest greedy prefix or suffix of I.

Proposition 3.11 Let I be a facet of SC(Q, [rho]). If I [not equal to] N(Q, [rho]), then the father of I in [N.sup.*] (Q, [rho]) is obtained from I by flipping the smallest position x [member of] [m] such that I [intersection] [x] [not equal to] N([q.sub.1] ... [q.sub.x], [PI][Q.sub.[x]\I]). Similarly, if I [not equal to] P(Q, [rho]), then the father of I in P (Q, [rho]) is obtained from I by flipping the largest position x [member of] [m] such that {i - x|i [member of] I \ [x]} = P([q.sub.x+1] ... [q.sub.m], [PI][Q.sub.[x+1,m]\I]).

3.4 Greedy flip algorithm

The initial motivation of this paper was to find efficient algorithms for the exhaustive generation of the set F (Q, [rho]) of facets of the subword complex SC(Q, [rho]). The properties of the subword complex described in Sections 2.2 and 2.3 already provide two immediate enumeration algorithms. First, the inductive structure of F(Q, [rho]) yields an inductive algorithm whose running time per facet is polynomial. The second option is an exploration of the flip graph G(Q, [rho]), whose running time is still polynomial per facet. The problem of a naive exploration is that we would need to store all facets of F(Q, [rho]) during the algorithm, which may require an exponential working space. Using the canonical spanning trees constructed in this paper, we can bypass this difficulty: we avoid to store all visited facets while preserving the same running time. The greedy flip algorithm generates all facets of the subword complex SC (Q, [rho]) by a depth first search procedure on one of the four canonical spanning trees described in Section 3.3. The preorder traversal of the tree also provides an iterator on the facets of SC(Q, [rho]). We refer to [PS12] for a discussion on the complexity and on an implementation of this algorithm. This algorithm is similar to that of [BKPS06] for pointed triangulations and that of [PP12] for primitive sorting networks.

4 Further combinatorial properties of the EL-labelings

In this section, we discuss some implications of the EL-labelings of the increasing flip graph presented in Section 3.1. These results concern combinatorial properties of the increasing flip poset [GAMMA](Q, [rho]), defined as the transitive closure of the increasing flip graph G(Q, [rho]). The key property for the validity of these results is that the increasing flip graph G(Q, [rho]) coincides with the Hasse diagram of the increasing flip poset [GAMMA](Q, [rho]) (see the discussion in the beginning of Section 1.2). We first characterize and study the subword complexes which fulfill this property.

We say that the subword complex SC(Q, [rho]) has a double root if there is a facet I [member of] SC(Q, [rho]) and two distinct positions i [not equal to] j [member of] [m] both flippable in I such that r(I, i) = r(I, j). Otherwise, we say that the subword complex SC(Q, [rho]) is double root free. We focus on double root free subword complexes due to the following characterization.

Proposition 4.1 The subword complex SC(Q, [rho]) is double root free if and only if its increasing flip graph G (Q, p) coincides with the Hasse diagram of its increasing flip poset [GAMMA] (Q, [rho]).

Intervals in the increasing flip graph of a double root free subword complex have the following property.

Proposition 4.2 Let I and J be two facets of a double root free subword complex SC (Q, [rho]). Then the intersection I [intersection] J is contained in all facets of the interval [I, J] in the increasing flip graph G (Q, [rho]).

Corollary 4.3 There is at most one p-falling (resp. n-falling) path between any two facets I and J of a double root free subword complex SC(Q, [rho]). If it exists, its length is given by [absolute value of I \ J] = [absolute value of J \ I].

Corollary 4.4 Let I and J be two facets of a double root free subword complex such that I [right arrow] J. The unique p-rising (resp. n-rising) path from I to J has maximal length among all path from I to J. Moreover, ifthere is a p-falling (resp. n-falling) path from I to J it has minimal length.

Remark 4.5 Note that the conclusions of Proposition 4.2, Corollary 4.3, and Corollary 4.4 do indeed not hold if SC (Q, [rho]) has double roots. This situation reduces to the situation of type [A.sub.1] with generator s for the word Q = sss and the element [rho] = s, which contradicts the three statements.

Corollary 4.6 The Mobius function on the increasing flip poset [GAMMA](Q, p) of a double root free subword complex SC(Q, [rho]) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By this corollary, we can compute the Mobius function of an interval [I, J] of the increasing flip poset as soon as we can decide whether or not there is a p-falling path from I to J. According to Proposition 3.6, there is always a p-falling path from the positive greedy facet to the negative greedy facet of a spherical subword complex. We therefore obtain the following statement.

Corollary 4.7 In a spherical double root free subword complex SC(Q, [rho]), we have

[mu](P(Q, [rho]), N(Q, [rho])) = [(-1).sup.[absolute value of Q]-l(p)].

Observe again that this result fails if we drop the condition that SC(Q, [rho]) is spherical. The subword complex SC ([Q.sup.ex], [[rho].sup.ex]) of Example 2.1 provides a counter- example.

Example 4.8 (Cambrian lattices) We finally want to recall that cluster complexes of finite types are particular examples of subword complexes, see [CLS13]. This implies that Cambrian lattices of finite types are indeed increasing flip graphs, see [PS11]. Our construction thus proves that Cambrian lattices of finite types are EL-shellable. This result was as well obtained by M. Kallipoliti and H. Muhle in [KM12]. We want to emphasize that the two resulting labelings differ, as do the two resulting spanning trees. We refer to the long version of this paper [PS12] for further details.

Example 4.9 (Duplicated words) Fix an element [rho] [member of] W and a reduced expression of it. Consider a word [Q.sup.dup] obtained by duplicating d [less than or equal to] l(p) letters in this reduced expression. Any facet of the subword complex SC([Q.sup.dup], [rho]) contains precisely one position among each pair of duplicated letters, and no other position. Therefore, the subword complex SC ([Q.sup.dup], [rho]) is the boundary complex of a d- dimensional cross-polytope, its increasing flip graph G([Q.sup.dup], [rho]) is the directed 1-skeleton [[??].sub.d] of a d- dimensional cube, and the increasing flip poset [GAMMA]([Q.sup.dup], [rho]) is a boolean poset. Let [phi]: [[??].sub.d] [right arrow] [GAMMA] ([Q.sup.dup], [rho]) be the natural graph isomorphism which sends 0 to P ([Q.sup.dup], [rho]) and 1 to N ([Q.sup.dup], [rho]). It sends the edge labeling [lambda] of [[??].sub.d] (see Example 1.2) to the positive and negative edge labelings p and n of the subword complex SC ([Q.sup.dup], [rho]). More precisely, [lambda]([epsilon] [right arrow] [epsilon]') = p([phi]([epsilon]) [right arrow] [phi]([epsilon]')) = n([phi]([epsilon]) [right arrow] [phi]([epsilon]')) - 1. Thus, [phi] sends the [lambda]-source tree of [[??].sub.d] to the source trees P([Q.sup.dup], [rho]) = [N.sup.*] ([Q.sup.dup], [rho]), and the [lambda]-sink tree of [[??].sub.d] to the sink trees [P.sup.*] ([Q.sup.dup], [rho]) = [N.sup.*] ([Q.sup.dup], [rho]). See Example 1.2 and Figure 1. Finally, the Mobius function on the increasing flip poset [GAMMA] ([Q.sup.dup], [rho]) is given by [mu] ([phi]([epsilon]), [phi]([epsilon]')) = [(- 1).sup.[delta]([epsilon],[epsilon]')] if [epsilon] [right arrow] [epsilon]' (where [delta] denotes the Hamming distance on the vertices of the cube) and [mu]([phi]([epsilon]), [phi]([epsilon]')) = 0 otherwise. See Example 1.4.

References

[Bjo80] Anders Bjorner. Shellable and Cohen-Macaulay partially ordered sets. Trans. Amer. Math. Soc., 260(1):159-183, 1980.

[BKPS06] Herve Bronnimann, Lutz Kettner, Michel Pocchiola, and Jack Snoeyink. Counting and enumerating pointed pseudotriangulations with the greedy flip algorithm. SIAM J. Comput., 36(3):721-739 (electronic), 2006.

[BW96] Anders Bjorner and Michelle L. Wachs. Shellable nonpure complexes and posets. I. Trans. Amer. Math. Soc., 348(4):1299-1327, 1996.

[CLS13] Cesar Ceballos, Jean-Philippe Labbe, and Christian Stump. Subword complexes, cluster complexes, and generalized multi-associahedra. J. Algebraic Combin., 2013.

[Hum90] James E. Humphreys. Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1990.

[KM04] Allen Knutson and Ezra Miller. Subword complexes in Coxeter groups. Adv. Math., 184(1): 161-176, 2004.

[KM05] Allen Knutson and Ezra Miller. Grobner geometry of Schubert polynomials. Ann. of Math. (2), 161(3): 1245-1318, 2005.

[KM12] Myrto Kallipoliti and Henri Muhle. On the EL-shellability of the cambrian semilattices. Preprint arXiv: 1206.6248, 2012.

[PP12] Vincent Pilaud and Michel Pocchiola. Multitriangulations, pseudotriangulations and primitive sorting networks. Discrete Comput. Geom., 48(1):142-191, 2012.

[PS09] Vincent Pilaud and Francisco Santos. Multitriangulations as complexes of star polygons. Discrete Comput. Geom., 41(2):284-317, 2009.

[PS11] Vincent Pilaud and Christian Stump. Brick polytopes of spherical subword complexes: A new approach to generalized associahedra. Preprint, arXiv: 1111.3349, 2011.

[PS12] Vincent Pilaud and Christian Stump. EL-labelings and greedy flip trees for subword complexes. Preprint, arXiv: 1210.14 35, 2012.

[PV96] Michel Pocchiola and Gert Vegter. Topologically sweeping visibility complexes via pseudo-triangulations. Discrete Comput. Geom., 16(4):419-453, 1996.

[Rea06] Nathan Reading. Cambrian lattices. Adv. Math., 205(2):313-353, 2006.

[Rea07] Nathan Reading. Sortable elements and Cambrian lattices. Algebra Universalis, 56(3-4): 411-437, 2007.

[RSS08] Gunter Rote, Francisco Santos, and Ileana Streinu. Pseudo- triangulations--a survey. In Surveys on discrete and computational geometry, volume 453 of Contemp. Math., pages 343-410. Amer. Math. Soc., Providence, RI, 2008.

Vincent Pilaud (1) ([dagger]) and Christian Stump (2)

(1) CNRS & LIX, EEcole Polytechnique, Palaiseau, France

(2) Institut fur Algebra, Zahlentheorie, Diskrete Mathematik, Universitat Hannover, Germany

([dagger]) Partially supported by the spanish MICINN grant MTM2011-22792, by the French ANR grant EGOS 12 JS02 002 01, and by the European Research Project ExploreMaps (ERC StG 208471).

V.P. is grateful to M. Pocchiola for uncountable inspiring discussions on the subject. We thank M. Kallipoliti and H. Muhle for mentioning our construction in [KM12].
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Pilaud, Vincent; Stump, Christian
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUFR
Date:Jan 1, 2013
Words:6598
Previous Article:Asymptotic properties of some minor-closed classes of graphs.
Next Article:A q, t-analogue of Narayana numbers.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters