Séminaire Lotharingien de Combinatoire 63 (2010), Article B63b

NONCROSSING PARTITIONS, CLUSTERS AND THE COXETER PLANE

NATHAN READING

Abstract. When W is a finite Coxeter group of classical type (A, B, or D), noncrossing partitions associated to W and compatibility of almost positive roots in the associated root system are known to be modeled by certain planar diagrams. We show how the classical-type constructions of planar diagrams arise uniformly from projections of small W -orbits to the Coxeter plane. When the construction is applied beyond the classical cases, simple criteria are apparent for noncrossing and for compatibility for W of types H_{3} and I_{2}(m) and less simple criteria can be found for compatibility in types E_{6}, F_{4} and H_{4}. Our construction also explains why simple combinatorial models are elusive in the larger exceptional types.

1. Introduction

1.1. W -Catalan combinatorics. The “classical” noncrossing partitions are set partitions Π of [n + 1] := {1, 2, … n + 1} such that when the elements of [n + 1] are placed in cyclic order on a circle, the convex hulls of the blocks of Π are disjoint. Thus, for example, every partition of [4] is noncrossing except {{1, 3}, {2, 4}}, which is “crossing” because the line segment defined by {1, 3} intersects the line segment defined by {2, 4}. Noncrossing partitions were first studied by Kreweras [16] in 1972 and since then their rich combinatorial and enumerative structure has been widely studied. (Surveys include [2, Chapter 4] and [20].) Noncrossing partitions are counted by the Catalan number. Recently, through the merger of lines of research in algebraic combinatorics [1, 19] and geometric group theory [4, 5, 10] it became apparent that the classical noncrossing partitions are a special case (the case W = S_{n+1}) of a construction valid for any finite Coxeter group W. The W -noncrossing partitions are counted by the W -Catalan number Cat(W).

The general definition of noncrossing partitions is not phrased in terms of planar diagrams. Rather, the parabolic subgroups of W play the part of partitions, and an algebraic construction produces a set of parabolic subgroups which are to be considered “noncrossing.” When W is the symmetric group, drawing the set partitions in the plane as described above, the noncrossing criterion of Kreweras and the algebraic criterion agree. Similarly, when W is one of the other classical finite Coxeter groups (B_{n} or D_{n}) there exist planar diagrams which can be used to determine whether a parabolic subgroup is crossing or noncrossing.

2000 Mathematics Subject Classification. Primary 20F55; Secondary 05A18.

Key words and phrases. associahedron, cluster, noncrossing partition, Coxeter plane, W -Catalan number.

This project began while the author was partially supported by NSF grant DMS-0202430 and was completed while the author was partially supported by NSA grant H98230-09-1-0056.

Another set of objects counted by the Catalan number has also recently been generalized to the context of finite Coxeter groups: triangulations of a convex polygon. Fomin and Zelevinsky [13] showed that a cluster algebra satisfies a certain finiteness condition if and only if the underlying combinatorics of the cluster algebra is governed by a finite Coxeter group W (or more precisely, a finite crystallographic root system associated to W). The combinatorial structure of the cluster algebra is a simplicial complex whose vertex set is a subset (the almost positive roots) of the root system. The facets of the complex are clusters: sets of almost positive roots that are pairwise “compatible.” The complex is dual to a simple polytope called the generalized associahedron. The number of clusters, or equivalently the number of vertices of the generalized associahedron, is Cat(W).

When W is the symmetric group, the almost positive roots can be put in bijection with the diagonals of a convex polygon such that two almost positive roots are compatible if and only if the corresponding diagonals do not cross. Thus a maximal set of compatible roots (or cluster) corresponds to a maximal set of noncrossing diagonals of a polygon. The latter is equivalent to a triangulation of the polygon. When W is a Coxeter group of type B_{n} or D_{n}, there are planar models which encode compatibility and which are only slightly more complicated.

Both the generalized associahedron and the noncrossing partition lattice have natural dihedral symmetry. The planar models in types A, B and D realize these symmetries as dihedral symmetries acting geometrically on the plane.

1.2. The main construction. This paper explains the planar diagrams in types A, B, and D by giving a Coxeter-theoretically uniform construction of planar diagrams for parabolic subgroups and for almost-positive roots. To the extent possible, we also give criteria for noncrossing and for compatibility (but not compatibility degree) in other types. We also suggest a simple explanation for why planar diagrams are easy in types A, B, and D, but problematic in many exceptional types.

The definitions of clusters and noncrossing partitions involve the choice of a Coxeter element for W: an element of W which can be expressed as the product of some permutation of the set S of simple generators of W. The order of a Coxeter element is the Coxeter number h of W and the exponents e_{1}, …, e_{n} of W are certain integers that can be read off from the eigenvalues of a Coxeter element. (The Coxeter number and exponents are well-defined because any two Coxeter elements are conjugate in W.) The W -Catalan number is given by

Cat(W) = ∏_{i=1}^{n} \frac{e_{i} + h + 1}{e_{i} + 1}.

The properties of Coxeter elements are closely tied to a certain (2-dimensional) plane P which we call the Coxeter plane, and which was first considered in generality by Coxeter [12]. A careful analysis of the Coxeter plane by Steinberg [21] provided the first uniform proofs of the key properties of Coxeter elements.

Our construction begins with orthogonal projections of a small W -orbit o to the Coxeter plane. Each parabolic subgroup W′ defines a partition of o into W′-orbits. The diagram for W′ is essentially this partition of o, projected to P. The planar models for almost positive roots are obtained by altering the projected orbits, which have dihedral symmetry of order 2h, to obtain a diagram with dihedral symmetry of order 2(h + 2).

Once planar diagrams are constructed, it remains to find criteria for reading off, from the diagrams, whether a parabolic subgroup is noncrossing, or whether a pair of roots is compatible. We give simple criteria for noncrossing and for compatibility for W of types H_{3} and I_{2}(m), and slightly more complicated criteria for compatibility in types E_{6}, F_{4} and H_{4}. Although a uniform criterion for compatibility in all types remains elusive, the diagrams we construct for almost positive roots seem to come very close to having a uniform criterion. Indeed, small ad hoc alterations of the diagrams in the remaining types E_{6}, E_{7}, E_{8} F_{4}, and H_{4} produce a complete model for compatibility, with the simplest possible criterion.

The approach via the Coxeter plane indicates that the classical finite Coxeter groups (and now types H_{3} and I_{2}(m)) admit simple criteria for noncrossing and for compatibility precisely because they admit small orbits. In this context, a “small” orbit is an orbit whose size is approximately the Coxeter number h. The groups of type A_{n}, B_{n}, I_{2}(m), D_{n}, and H_{3} each possess an orbit of size h or h + 2, while the remaining groups F_{4}, E_{6}, E_{7}, H_{4}, and E_{8} have orbits of sizes 2h, 2h + 3, 3h + 2, 4h, and 8h, respectively. The intrinsic complexity of the diagrams unavoidably increases when the size of the orbit is much greater than h. It is well-known that the property of having small orbits is also responsible for the combinatorial models which realize the classical groups as various groups of permutations, by letting the group act as permutations of a small orbit. However, in this latter context, a “small” orbit is one whose size is a small integer multiple of the rank of the Coxeter group.

1.3. Computer-generated diagrams. Postscript files, showing the results of the main construction for many finite Coxeter groups, are available with this paper on the website of the Séminaire Lotharingien de Combinatoire. The figures were made with the help of John Stembridge’s coxeter and weyl maple packages and PostScript drawing routines developed by the author. The files are optimized for small file size as PostScript files, by taking advantage of the fact that PostScript is a complete programming language. The author recommends viewing the files (or at least those files associated with the larger exceptional groups) with a PostScript viewer that interprets PostScript directly, rather than converting to PDF. File sizes in PDF will be up to about 350 times larger than the postscript files.

Each file for parabolic subgroup diagrams (e.g. e6nc.ps) displays one representative from each symmetry class of diagram, labels the parabolic subgroup as crossing or noncrossing, and gives a list of the reflections generating the parabolic subgroup. The blocks in the partitions represented are indicated by line segments connecting pairs of points related by a reflection in the parabolic subgroup. The blocks are also indicated by colors of vertices, with black points representing singleton blocks. Colors of multiple points at the origin can be determined from the segments, keeping in mind that there are no degenerate segments connecting different points at the origin. The reflections are numbered according to the numbering of positive roots in Stembridge’s packages. The noncrossing parabolic subgroups are identified by computer, via a bijection defined in [17, Section 6] (see also [18, Theorem 8.9]) from sortable elements to noncrossing parabolic subgroups.

Each file for diagrams of almost positive roots (e.g. e6cl.ps) pictures diagrams for pairs of almost positive roots (α, β), where α ranges over all negative simple roots and β ranges over all almost positive roots. Each diagram is a collection of line segments, labeled as necessary by which of the multiple origin points is an endpoint of the segment. The labeling of segments is given in the diagram files by coloring the segments. In Section 6, descriptions are given of ad hoc alterations to the almost positive root diagrams in some types. These altered diagrams are also available, e.g. as e6cl alt.ps.

1.4. Outline of the paper. The remainder of the paper proceeds as follows. In Section 2, we give background on crossing and noncrossing parabolic subgroups, relate these to partitions of a W -orbit, and describe the construction of Coxeter-planar diagrams for parabolic subgroups. In Section 3 we show that in the classical types, our construction of planar diagrams for partitions leads to the usual planar models for crossing/noncrossing partitions, and discuss how the construction works out in other types. In Section 4 we review the definition of compatibility and describe the usual models for compatibility in the classical types, in preparation for the development, in Section 5, of a uniform construction of diagrams for almost positive roots. Finally, in Section 6, we show that the construction recovers the classical planar diagrams, and discuss compatibility criteria in other types.

2. Parabolic subgroups and partitions of orbits

In this section we discuss crossing and noncrossing parabolic subgroups. We introduce the notion of partitions of an orbit and describe how to obtain planar diagrams for parabolic subgroups by projecting partitions of an orbit to the Coxeter plane.

2.1. Parabolic subgroups. We assume basic background on Coxeter groups and root systems, including the classification of finite Coxeter groups. This background can be found, for example, in [7, 8, 15]. Throughout the paper, (W, S) will stand for a finite Coxeter system of rank n = |S|. For s_{1}, s_{2} ∈ S, the order of s_{1}s_{2} will be denoted by m(s_{1}, s_{2}). We fix a representation of W as a real reflection group on a Euclidean space V, and make no distinction between elements of W and their action on V. We also assume that the only element fixed by W is the origin. This implies in particular that the dimension of V equals the rank of W. The set of elements of W which act as reflections is T = {wsw^{−1} : s ∈ S, w ∈ W }. For each t ∈ T, let H_{t} be the reflecting hyperplane associated to t. The collection {H_{t} : t ∈ T } is called the Coxeter arrangement associated to W.

Throughout the paper, we will assume that W is irreducible, meaning that W cannot be written as a direct product of Coxeter systems of strictly lower rank. Equivalently, we require that the diagram of W be connected as a graph. The constructions of this paper rely, in two major ways, on the assumption that W is irreducible. First, the assumption of irreducibility, together with the assumption that W fixes only the origin, implies that the linear span of any nontrivial orbit is V. Second, the assumption of irreducibility is essential to the construction of the Coxeter plane.

For any J ⊆ S, the subgroup W_{J} generated by J is called a standard parabolic subgroup. More generally, a parabolic subgroup is any subgroup which is conjugate in W to a standard parabolic subgroup. The rank of a parabolic subgroup W′ is |J|, where W_{J} is some standard parabolic subgroup conjugate to W′. The parabolic subgroups of the symmetric group S_{n+1} (the Coxeter group of type A_{n}) are exactly the subgroups W′ generated by transpositions. Such a subgroup W′ decomposes the set [n + 1] into W′- orbits. On the other hand, to each set partition Π of [n + 1], one can associate the parabolic subgroup W′ generated by transpositions (i j) such that i and j are in the same block of Π. Thus for an arbitrary finite Coxeter group W, one may think of the parabolic subgroups of W as a W -analog of partitions.

Another way to think of set partitions of [n + 1] is as subspaces in the intersection lattice of the Coxeter arrangement associated to S_{n+1}. The Coxeter arrangement for the usual reflection representation of S_{n+1} consists of all hyperplanes defined by equations x_{i} = x_{j} for 1 ≤ i < j ≤ n. Given a set partition Π of [n + 1], one constructs a subspace by imposing the equation x_{i} = x_{j} whenever i and j are in the same block of Π. This is easily seen to be a bijection between set partitions and subspaces in the intersection lattice of S_{n+1}.

For general finite W, parabolic subgroups of W are in bijection [3] with subspaces in the intersection lattice of the Coxeter arrangement for W, with a parabolic subgroup W′ mapping to the set stabilized by W′, a subspace whose codimension equals the rank of W′. The inverse map takes a subspace in the intersection lattice to the subgroup of W stabilizing that subspace.

2.2. Crossing and noncrossing. We next explain the notion of crossing or noncrossing parabolic subgroups of W, quoting results from [4, 10, 11]. Any element w ∈ W can be written as a word in the alphabet T. Since words in the alphabet S are so commonly used in the study of Coxeter groups, to avoid confusion we will refer a word in the alphabet T as a T -word. A reduced T -word for w is a T -word for w which has minimal length among all T -words for w. The absolute length of w is the length of a reduced T -word for w. (The usual length of w is the length of a reduced word for w in the alphabet S.) Define a partial order on W by setting u ≤ v if and only if u has a reduced T -word which is a prefix of some reduced T -word for v. This partial order is called the absolute order on W.

The interval [1, c] in the absolute order, where c is a Coxeter element, has come to be called the noncrossing partition lattice associated to W. For any element x of [1, c] and any reduced T -word t_{1} ⋯ t_{i} for x, the group ⟨t_{1}, …, t_{i}⟩ is a parabolic subgroup of W. Two different such words for x ∈ [1, c] give rise to the same parabolic subgroup if and only if the products of the two words are the same element of W. The parabolic subgroups arising in the manner are called noncrossing parabolic subgroups. All other parabolic subgroups are crossing. The interval [1, c] corresponds to containment order on noncrossing parabolic subgroups or, equivalently, to reverse containment order on the subspaces associated to noncrossing parabolic subgroups. If W is reducible as a direct product of nontrivial Coxeter groups, then the noncrossing parabolic subgroups of W are exactly those parabolic subgroups whose intersection with each factor is a noncrossing parabolic subgroup in the factor. Thus it is harmless (and essential, as discussed above) to restrict to the case where W is irreducible.

Remark 2.1. Although [1, c] is called the noncrossing partition lattice, it makes sense to reserve the term “noncrossing partitions” for noncrossing parabolic subgroups: The elements of [1, c] are group elements, not partitions in any natural sense, and there are no analogous group elements playing the role of “crossing partitions.”

Conjugation by an element of W permutes T and thus acts as an isomorphism of the absolute order. Since any two Coxeter elements are conjugate in W, the isomorphism type of [1, c] does not depend on the choice of c. The set of elements in [1, c] and the set of noncrossing parabolic subgroups do depend on the choice of c, but changing from c to another Coxeter element wcw^{−1} affects both of these sets by a global conjugation by w. It will be useful to fix a particularly convenient Coxeter element. The Coxeter diagram of a finite Coxeter group is a tree, and in particular is bipartite. Let S_{+} ∪ S_{−} be a bipartition of the Coxeter diagram for W. Define involutions

c_{+} := ∏_{s∈S_{+}} s and c_{−} := ∏_{s∈S_{−}} s

so that c := c_{−}c_{+} is a Coxeter element. A Coxeter element arising in this manner is called a bipartite Coxeter element. Since the elements of S_{+} commute pairwise, the product c_{+} is well-defined, and similarly c_{−} is well-defined. All further references to noncrossing partitions or crossing/noncrossing parabolic subgroups will refer to this fixed bipartite Coxeter element. The noncrossing parabolic subgroups for c and c^{−1} coincide, and thus since c^{−1} = c_{−}cc_{−} = c_{+}cc_{+}, the conjugation action of the subgroup ⟨c_{+}, c_{−}⟩ preserves the crossing/noncrossing status of parabolic subgroups.

2.3. Partitions of orbits. Besides parabolic subgroups and subspaces in the intersection lattice, another W -analog of set partitions of [n + 1] appears not to have been considered before. Given a fixed non-trivial orbit o of W, each parabolic subgroup W′ decomposes o into W′-orbits. We will call this decomposition the partition of o induced by W′. Collectively, such partitions of o will be called W -partitions of o. For general finite W, given a partition of o that is known to the be a W′-partition for some W′, one can read off W′ from the partition of o. Specifically, it is the stabilizer of its fixed subspace, and the latter is read off as in the following proposition, whose simple proof is omitted.

Proposition 2.2. Let o be a W -orbit and let Π be a partition of o induced by some parabolic subgroup W′ of W. Then the fixed subspace of W′ is the orthogonal complement of the linear span of all vectors x−y where x, y ∈ o are in the same block of the partition.

In light of Proposition 2.2, the W -partitions of o may be thought of as a W -analog of the usual partitions of [n + 1]. Note that, even fixing W = S_{n+1}, the W -partitions of orbits generalize the usual partitions of [n + 1]. The usual partitions of [n + 1] arise when o is taken to be a smallest nontrivial S_{n+1}-orbit.

2.4. Diagrams for partitions of orbits. Our approach to combinatorial models of noncrossing partitions is to fix a W -orbit o, associate a planar diagram to each W - partition of o, and then seek a combinatorial characterization of crossing and noncrossing partitions of o in terms of the planar diagrams.

The planar diagrams will arise from the orthogonal projection of o to the Coxeter plane P. Details on P can be found in [12], in [21], in Sections 3.16–3.20 of [15] or in Section V.6.2 of [8]. The important properties of P are as follows: P is fixed as a set by the action of ⟨c_{+}, c_{−}⟩, and ⟨c_{+}, c_{−}⟩ acts on P as a dihedral reflection group of order 2h. Taking ε ∈ {+, −}, the transformation c_{ε} stabilizes H_{s} for s ∈ S_{ε}. In P there are two lines L_{+} and L_{−} with the following properties: A reflecting hyperplane H for a reflection in W intersects P in L_{ε} if and only if H is the reflecting hyperplane for some simple reflection s ∈ S_{ε}. The other reflecting hyperplanes intersect P in lines which are the images of L_{±} under ⟨c_{+}, c_{−}⟩. In particular, every reflecting hyperplane is in the c-orbit of H_{s} for some s ∈ S. Equivalently, every reflection in W is in the orbit (under conjugation by c) of some simple reflection s and, more specifically, we have the following proposition. (Cf. [8, Proposition V.6.2] or [15, Exercise 3.19.2]).

Proposition 2.3. For any t ∈ T, the orbit of H_{t} under the action of the dihedral group ⟨c_{+}, c_{−}⟩ either:

(i) has h/2 elements and intersects {H_{s} : s ∈ S} in a single element.

(ii) has h elements and intersects {H_{s} : s ∈ S} in a two-element set. Furthermore, when (i) holds, the hyperplane in the intersection has H = w_{0}H, where w_{0} is the longest element of W. When (ii) holds, the two elements in the intersection are related by the action of w_{0}.

Fix a W -orbit o, and consider the orthogonal projection of o to P. The projected orbit is thought of as a point configuration, where some points have multiplicity greater than one because the orthogonal projection to P is not always one-to-one. Multiple points are considered to be distinguishable — each copy of a point is formally labeled by its pre-image in o. The problem of multiplicity can be minimized by taking o as small as possible, in which case the only point of the projected orbit having multiplicity is the origin, with multiplicity at most 3.

For W of type A, B or I_{2}, the smallest orbit is of size h, so the projection onto P consists of the vertices of an h-gon. The smallest orbit in type D_{n} or H_{3} is of size h + 2, and the projection onto P consists of an h-gon and two points at the origin. These assertions about projected orbits in types A, B, and D are argued in Sections 3.1, 3.2 and 3.4. For the exceptional types, the projected orbits are determined computationally. Figure 1 shows, for each exceptional Coxeter group W, the projection of a smallest orbit of W onto P. In the cases where points in the projected orbit project to the origin, the multiplicity of points at the origin is indicated in the figure. No other points in the projected orbits have multiplicity.

Figure 1 makes it clear why, as mentioned in Section 1.2, a “small” orbit is an orbit whose size is on the order of the Coxeter number h: Since the Coxeter element c is in particular an orthogonal transformation and fixes P as a set, it commutes with orthogonal projection to P, so that the projected orbit decomposes as the union of c-orbits in P. When the size of the W -orbit is on the order of h, the projected W -orbit consists of a single c-orbit (forming a regular h-gon in P) and perhaps several points at the origin.

Once the projection of o to P is calculated, the Coxeter-plane diagram for each parabolic subgroup W′ is obtained by projecting the partition of o induced by W′ orthogonally to P. The diagram can be thought of as a coloring of the projection of o to P, where the colors are the blocks of the partition of o. Repeated points at the origin may have different colors.

3. Diagrams for noncrossing partitions

In this section, we discuss, for W of various types, the construction of Coxeter-plane diagrams for parabolic subgroups. Computer data are available for many types, as described in Section 1.3.

E_{6}  E_{7}  E_{8}
(origin multiplicity 3)  (origin multiplicity 2)

F_{4}  H_{3}  H_{4}

(origin multiplicity 2)

Figure 1. The smallest orbit of W, projected orthogonally to the Coxeter plane.

3.1. Type A_{n}. We represent the Coxeter group W of type A_{n} in the usual way as the symmetric group S_{n+1} acting on ℝ^{n+1} by permuting coordinates. To obtain a representation fixing only the origin, one takes the quotient of ℝ^{n+1} modulo the line spanned by the vector (1, 1, …, 1). We will describe points in ℝ^{n+1} and tacitly assume the quotient. A smallest orbit o of W is the set of unit basis vectors {e_{1}, …, e_{n+1}}. The simple generators are {s_{i} : i ∈ [n]}, with s_{i} acting by transposing e_{i} and e_{i+1}. Choose the bipartition of the diagram with S_{+} = {s_{1}, s_{3}, …} and S_{−} = {s_{2}, s_{4}, …}, so that the bipartite Coxeter element c = c_{−}c_{+} is the (n+1)-cycle c = (1, 3, …, n+1, n, n−2, …, 2) if n is even or c = (1, 3, …, n, n + 1, n − 1, …, 2) if n is odd.

The orbit o is also a single orbit under the action of c. This implies in particular that no point in o projects orthogonally to the origin in P: If some e_{i} projects to the origin, then since c fixes P and thus fixes P^{⊥}, each element of o is contained in P^{⊥}. This is forbidden by considerations of dimension. We conclude that the projection of o to P is a regular (n + 1)-gon (i.e. an h-gon) centered at the origin. The cyclic order on the projections of the vertices corresponds to the (n + 1)-cycle c. The W -partitions of o coincide with the set partitions of o. It is well-known that the noncrossing partitions of type A are exactly the noncrossing partitions of a cycle introduced by Kreweras [16]. The proof can be found in [5] or [9]. Thus noncrossing parabolic subgroups are identified by the following criterion.

Noncrossing Criterion 1. A parabolic subgroup is noncrossing if and only if the convex hulls of the blocks of its Coxeter-plane diagram are disjoint.

To correctly compare the Coxeter-plane construction with the arguments in [5] or [9], one should construct the noncrossing partitions of the cycle c described above, rather than the usual noncrossing partitions of (1, 2, …, n + 1). The latter (n + 1)-cycle is a different Coxeter element s_{1}s_{2} ⋯ s_{n}, which is not bipartite with respect to our choice of simple system.

3.2. Type B_{n}. The Coxeter group of type B_{n} is realized as the symmetry group of the n-dimensional cube with vertices (±1, ±1, …, ±1). The set o = {±e_{1}, …, ±e_{n}} is a smallest orbit. The simple generators are {s_{i} : i ∈ [n]}, where s_{n} is the reflection orthogonal to e_{n}, and s_{i} acts by transposing e_{i} and e_{i+1}, for each i ∈ [n − 1]. Choose S_{+} = {s_{1}, s_{3}, …} and S_{−} = {s_{2}, s_{4}, …}, and define the bipartite Coxeter element c = c_{−}c_{+}. When n is even,

c = (1, 3, …, n − 1, −n, −n + 2, …, −2, −1, −3, …, −n + 1, n, n − 2, …, 2),

and when n is odd,

c = (1, 3, …, n, −n + 1, −n + 3, …, −2, −1, −3, …, −n, n − 1, n − 3, …, 2).

Similarly to the type-A case, no element of o projects to the origin of P, and since the antipodal pairs in o must project to antipodal pairs in P, we conclude that the projection of o to P is a regular (h = 2n)-gon centered at the origin. Coxeter-plane diagrams of parabolic subgroups are centrally symmetric set partitions of the vertices of the 2n-gon. Noncrossing Criterion 1 is the combinatorial crossing/noncrossing criterion of [19], which has been shown in [4, 6, 10] to correctly classify parabolic subgroups as crossing/noncrossing in the algebraic sense. Again, to correctly compare the above construction to [4, 6, 10, 19], one must take the correct 2n-cycle c described above.

3.3. Type I_{2}(m). For a dihedral Coxeter group W of type I_{2}(m), the parabolic subgroups are {1, t} for each reflection t as well as the trivial subgroup {1} and the entire group W. In this case, h = m and the plane P is the plane on which W acts (so that projection to P is the identity map). The orbit o can be taken to be the vertices of a regular m-gon. For any finite Coxeter group W, the trivial subgroup, the subgroups {1, t} for reflections T and the whole group W are noncrossing parabolic subgroups. Thus in type I_{2}(m) we must declare every parabolic subgroup to be noncrossing. This can be accomplished with Noncrossing Criterion 1. The validity of the criterion is trivial for W′ = {1} and W′ = W. In the remaining cases, the criterion is valid because any parabolic subgroup {1, t} decomposes o into a collection of non-overlapping parallel line segments.

3.4. Type D_{n}. The Coxeter group of type D_{n} can be realized in ℝ^{n} as the Coxeter group generated by simple reflections s_{i} transposing e_{i} and e_{i+1} for i ∈ [n − 1] and s_{n} transposing e_{n−1} and −e_{n}. A smallest orbit is o = {±e_{1}, …, ±e_{n}}. We bipartition the simple reflections, except for s_{n}, by S_{+} = {s_{1}, s_{3}, …} and S_{−} = {s_{2}, s_{4}, …}, and put s_{n} is the part with s_{n−1}. The resulting bipartite Coxeter element c = c_{−}c_{+} for n even is

(1, 3, …, n − 1, −n + 2, −n + 4, …, −2, −1, −3, …, −n + 1, n − 2, n − 4, …, 2) (n, −n),

and for n odd is

(1, 3, …, n − 2, −n + 1, −n + 3, …, −2, −1, −3, …, −n + 2, n − 1, n − 3, …, 2) (n, −n).

(a)  (b)  (c)

Figure 2. Simple reflections and Coxeter plane for H_{3}.

If an element x of o does not project to the origin of P, then the projection of x must have an h-fold orbit under the action of c. (Here, the Coxeter number h is 2n − 2.) However, since orthogonal projection to P commutes with the action of c, the point x also has an h-fold orbit. Since {±e_{n}} is a c-orbit, we conclude that the elements ±e_{n} both project to the origin. The other 2n − 2 elements of o project to the vertices of a regular h-gon in P.

In this example, we catch the first glimpse of the complications inherent in the construction: Since several points of the projected orbit coincide, it is unavoidable to have some intersections of blocks, even for noncrossing partitions. However, the complications are tame in this case, and the following criterion correctly classifies parabolic subgroups as crossing or noncrossing.

Noncrossing Criterion 2. Two blocks in a Coxeter-plane diagram are noncrossing if their convex hulls either are disjoint or intersect in a single point on the boundary of both. A parabolic subgroup of o is noncrossing if and only if the blocks in its Coxeterplane diagram are pairwise noncrossing.

Noncrossing Criterion 2 is a rephrasing of the criterion given by Athanasiadis and Reiner in [1, Section 3], again taking into account the labeling of the (2n − 2)-cycle given by c above. Although Noncrossing Criterion 2 has a formally weaker requirement for the noncrossing property, it is still valid in types A, B, and I, because in those types any two blocks that intersect necessarily intersect in their relative interiors.

3.5. Type H_{3}. The Coxeter group W of type H_{3} is the symmetry group of the icosahedron and of the dodecahedron. The smallest nontrivial orbit o of W consists of the 12 vertices of the icosahedron. We will relate all of the H_{3} constructions to the icosahedron depicted in Figure 2.a as a triangulation of a round sphere. The sphere is partially transparent, so that we see the vertices and edges on the “back” of the sphere in gray. Figure 2.b shows a choice of simple reflections for W, with each reflection represented by the intersection of its reflecting plane with the sphere. (The vertices and edges of the icosahedron are faded in Figure 2.b to let the reflections stand out.) The reflection whose plane is roughly horizontal in the picture will be called s_{2}, while s_{1} and s_{3} are the reflections with m(s_{1}, s_{2}) = 3 and m(s_{2}, s_{3}) = 5. Choose S_{+} = {s_{1}, s_{3}} and S_{−} = {s_{2}}, so that c = c_{−}c_{+} = s_{2}s_{1}s_{3} is a bipartite Coxeter element. The Coxeter plane P is indicated by the dotted line in Figure 2.c, and the Coxeter element c acts by reflecting through P and rotating P by 1/10 of a turn. (The rotation moves points on the “front” of the sphere downwards in the picture.)

Figure 3. Noncrossing partitions in H_{3}.

Two opposite vertices of the icosahedron project to the origin in P. The other 10 points project to the vertices of a regular decagon centered at the origin. The noncrossing property of parabolic subgroups is described by Noncrossing Criterion 2.

Figure 3 shows the Coxeter-plane diagram for one representative of each c-conjugation orbit of noncrossing parabolic subgroups, omitting {1} and W. Call the points at the origin ±0. If a diagram has a block shown in red (or the lighter of the two grays) then the red block contains −0 but not +0. The c-conjugation orbit of each noncrossing parabolic subgroup shown is of cardinality 5. To see that the cardinality is 5 and not 10 in some cases, recall that the action of c on the diagrams not only rotates by 1/10 of a turn, but also switches the two points at the origin. The bottom row of Figure 3 shows noncrossing diagrams for parabolic subgroups of the form {1, s} for a simple reflection s. Reading from left to right in this bottom row, the simple reflections are s_{1}, s_{2} and s_{3}.

Figure 4 shows one representative of each c-conjugation orbit of crossing parabolic subgroups. Instead of the convex hulls of the blocks, the figure shows line segments indicating that two points are related by a reflection in the parabolic subgroup. The partition of o induced by W′ is thus the closure of the relation shown by the line segments. The blocks are also indicated by colors of vertices. The bottom-left diagram has two singleton blocks at the origin (shown in black). The other three diagrams have both a blue and a yellow vertex at the origin.

The standard parabolic subgroup W_{s_{1},s_{2}} decomposes o into four orbits of three elements each, arranged into four equilateral triangles on four parallel planes. Two of the equilateral triangles are faces of the icosahedron. Of the ten parabolic subgroups conjugate to W_{s_{1},s_{2}}, five are noncrossing and five are crossing. One of the noncrossing parabolic subgroups is W_{s_{1},s_{2}} itself, which appears as the top-left diagram in Figure 3. A crossing parabolic subgroup conjugate to W_{s_{1},s_{2}} is shown as the top-left diagram in Figure 4.

The standard parabolic subgroup W_{s_{1},s_{3}} decomposes o into four orbits of two elements each, and one orbit containing 4 elements. The four-element orbit consists of the vertices of two antipodal edges of the icosahedron. Of the fifteen parabolic subgroups

Figure 4. Crossing parabolic subgroups of H_{3}.

conjugate to W_{s_{1},s_{3}}, five are noncrossing and ten are crossing, with W_{s_{1},s_{3}} appearing as the top-center diagram in Figure 3, and crossing parabolic subgroups conjugate to W_{s_{1},s_{3}} appearing as the two diagrams on the right in Figure 4.

The standard parabolic subgroup W_{s_{2},s_{3}} decomposes o into two orbits of five elements each, arranged into regular pentagons on two parallel planes, and two singleton orbits. Of the six parabolic subgroups conjugate to W_{s_{1},s_{2}}, five are noncrossing (the top-right diagram in Figure 3 is W_{s_{1},s_{2}}) and one is crossing (the bottom-left diagram in Figure 4).

3.6. Type F_{4}. The Coxeter group W of type F_{4} is the smallest example of an irreducible Coxeter group having no orbit of cardinality approximately h. A smallest orbit o of F_{4} has 24 elements, while h is 12. (This orbit consists of the vertices of a regular 24-cell.) The projection of o to P consists of two regular h-gons centered at the origin as shown in Figure 1. The presence of two h-gons in the Coxeter-plane diagrams for parabolic subgroups causes problems for Noncrossing Criteria 1 and 2 which appear already in the case where the parabolic subgroup is generated by a single reflection. Any parabolic subgroup generated by a single reflection is noncrossing. However, Figure 5 shows the diagram of such a parabolic subgroup which fails both Noncrossing Criterion 1 and Noncrossing Criterion 2. The decomposition into blocks is finer than the decomposition of the diagram into connected pieces. Specifically, two of the connected pieces of the diagram are further divided into blocks of two points each, as indicated by colors of points. Thus in two places in the diagram, convex hulls of blocks intersect in their relative interiors.

To further illustrate the difficulty of finding a noncrossing criterion for Coxeter plane diagrams of type F_{4}, observe for example that the criterion must declare Figure 6.a to be crossing while declaring Figure 6.b to be noncrossing. In Figure 6, as in Figure 4, line segments indicate that two points are related by a reflection in the parabolic subgroup

Figure 5. A (noncrossing) parabolic subgroup of rank 1 in F_{4}.

Figure 6. a: A crossing parabolic subgroup in F_{4}. b: A noncrossing parabolic subgroup in F_{4}.

and the blocks are also indicated by colors of vertices, with black dots indicating singleton blocks. Various unsatisfying criteria can be devised to detect crossing parabolic subgroups in F_{4}, for example in terms of centers of mass of projected blocks. However, even these contrived conditions fail dramatically for small parabolic subgroups in H_{4}.

4. Clusters

In this section, we give a brief account of compatibility and clusters of almost positive roots. These were introduced by Fomin and Zelevinsky to describe the vertices of the generalized associahedron [13] and also to describe compatibility of denominator vectors of cluster variables in a cluster algebra [14]. The results reviewed in this section are all contained in [13]. We continue under the vital assumption that W is irreducible.

Let Φ be a root system for W, chosen to be consistent with the fixed reflection representation. Write Π for the simple roots (corresponding to the simple generators S). Let Φ^{+} denote the positive roots, which are in one-to-one correspondence with the reflections T. Let Φ_{≥−1} = Φ_{+} ∪ (−Π) be the set of almost positive roots in the root system Φ associated to W. As before, let S = S_{+} ∪ S_{−} be a bipartition of the Coxeter diagram, and define involutions τ_{+} and τ_{−} on Φ_{≥−1}:

τ_{ε}(α) = \begin{cases}α & if α = −α_{s} for s ∈ S_{−ε} \\ c_{ε}(α) & otherwise. \end{cases}

The following is a direct consequence^{1} of Proposition 2.3.

Proposition 4.1. For any α ∈ Φ_{≥−1}, the orbit of α under the action of the dihedral group ⟨τ_{+}, τ_{−}⟩ either:

(i) has (h + 2)/2 elements and intersects −Π in a single element.

(ii) has h + 2 elements and intersects −Π in a two-element set. When (i) holds, the root in the intersection has β = −w_{0}β, where w_{0} is the longest element of W. When (ii) holds, the two roots in the intersection are related by the action of −w_{0}.

There is a unique binary relation (called “compatibility”) on Φ_{≥−1} which is both ⟨τ_{−}, τ_{+}⟩-invariant and has the following property for each negative simple root −α_{s}: A root β ∈ Φ_{≥−1} is compatible with −α_{s} if and only if α_{s} appears with coefficient zero in the simple root expansion of β. (More generally, the paper [13] defines the the compatibility degree (α ∥ β) of a pair α, β of almost positive roots, which we will not consider here.) The compatibility relation is symmetric.

Maximal sets of pairwise-compatible almost positive roots are called clusters. Each cluster contains n elements, where n is the rank of W. The clusters are the maximal faces of a simplicial complex called the cluster complex, with faces given by pairwise compatible sets of almost positive roots. Dual to the cluster complex is a simple polytope called the generalized associahedron for W.

In Section 5, we describe a construction of a planar diagram for each almost positive root, with the goal of describing compatibility of two roots in terms of the union of their two diagrams. For the purposes of comparison and motivation, we conclude this section by describing the usual planar diagrams for compatibility in types A_{n}, B_{n} and D_{n} as described in [13, Section 3.5].

4.1. The usual model for compatibility in type A_{n}. Let W be a Coxeter group of type A_{n} with the bipartition of S described in Section 3.1. For each i ∈ [n], let α_{i} be the simple root corresponding to s_{i}.

Compatibility of roots in Φ_{≥−1} is modeled by diagonals of a regular convex (n + 3)- gon. The negative simple roots −Π = {−α_{1}, …, −α_{n}} are identified with n diagonals forming a “snake” configuration as illustrated in Figure 7 for the case n = 7. The set of positive roots in type A_{n} consists of all vectors of the form α_{i} + α_{i+1} ⋯ + α_{j} for 1 ≤ i ≤ j ≤ n. Each positive root α_{i} + α_{i+1} + ⋯ + α_{j} is identified with the unique diagonal that crosses the diagonals labeled −α_{i}, −α_{i+1}, …, −α_{j} and crosses no other diagonals in the snake.

This correspondence between almost positive roots and diagonals has the property that two roots are compatible if and only if their diagonals do not cross. Thus a cluster of almost positive roots corresponds to a choice of n noncrossing diagonals, or in other words, a triangulation of the polygon. The map τ_{−} acting on Φ_{≥−1} corresponds to a

1Proposition 4.1 was first pointed out as [13, Theorem 2.6], where its proof relies on [13, Lemma 2.1]=[8, Exercise V.6.2], which relies on the considerations leading to Proposition 2.3.

−α_{1} −α_{2} −α_{3}−α_{4} −α_{5} −α_{6} –α_{7}

Figure 7. The “snake” in type A_{7}

−α_{1} −α_{2} −α_{3}−α_{4} −α_{3} −α_{2} –α_{1}

Figure 8. The “snake” in type B_{4}

symmetry of the polygon. Specifically, τ_{−} acts as the unique reflective symmetry of the polygon that fixes the diagonal labeled −α_{1}. Similarly, τ_{+} acts as the unique reflective symmetry fixing −α_{2}. Thus ⟨τ_{+}, τ_{−}⟩ is the full symmetry group of the polygon.

4.2. The usual model for compatibility in type B_{n} (C_{n}). Let W be a Coxeter group of type B_{n} with simple generators S and bipartition of S as described in Section 3.2. For each i ∈ [n], let α_{i} be the simple root corresponding to s_{i}.

Clusters of almost positive roots in type B_{n} are modeled by centrally symmetric triangulations of a regular convex (2n + 2)-gon. Each almost positive root is identified with either a diameter or a centrally symmetric pair of diagonals and, as in type A_{n}, “compatible” means “noncrossing.” As illustrated in Figure 8, the negative simple root −α_{n} is identified with a diameter and each other negative simple root is identified with a centrally symmetric pair of diagonals in the snake pattern. For each negative simple

−α_{1} −α_{2} −α_{3}−α_{5} −α_{4} −α_{3} −α_{2} –α_{1}

Figure 9. The “snake” in type D_{5}

root −α_{s}, fix one of the (1 or 2) diagonals \overline{QR} associated to −α_{s}. Then each positive root β is assigned to the unique diameter or symmetric pair of diagonals such that the coefficient of α_{s} in the simple root expansion of β equals the number of segments (0, 1 or 2) associated to β that cross the diagonal \overline{QR}. The almost positive roots of the dual root system of type C_{n} are associated to the diagonals such that a root (of type B_{n}) and its coroot (of type C_{n}) are associated to the same diagonal. The description of τ_{±} is just as in type A.

4.3. The usual model for compatibility in type D_{n}. Let W be a Coxeter group of type D_{n} with simple generators S and bipartition of S as described in Section 3.4. The model for compatibility inhabits a regular (2n)-gon. Each almost positive root is identified with a colored diameter (“gray” or “dashed”) or with an uncolored centrally symmetric pair of diagonals. As illustrated in Figure 9 in the case n = 5, the simple root −α_{n} is identified with a gray diameter, −α_{n−1} is identified with the dashed diameter in the same location, and each other negative simple root is identified with a pair of diagonals to form the familiar snake pattern. The remaining roots are assigned to colored diameters or pairs of uncolored diagonals as described in [13, Section 3.5]. Compatibility between two pairs of symmetric diagonals or between a diameter and a pair of symmetric diagonals is given by the usual noncrossing condition. Compatibility between two diameters is as follows: Two different diameters of the same color are always compatible, while two diameters of different colors are compatible if and only if they coincide (as for example −α_{4} and −α_{5} in Figure 9). The maps τ_{±} act not only geometrically, but also on colors. As before, the map τ_{−} acts as the reflective symmetry of the polygon fixing −α_{1} and the map τ_{+} acts as the reflective symmetry fixing −α_{2}. In addition τ_{(−1)^{n}} changes the colors of all diameters and τ_{(−1)^{n−1}} fixes the colors of all diameters.

5. Diagrams for almost positive roots

In this section we construct a planar diagram for each almost positive root. The main idea for the construction springs from the similarity, in the classical types, between

Figure 10. The Coxeter diagram of type E_{6}.

diagrams for noncrossing partitions and diagrams for clusters. For example, in the case where W is of type A_{n}, diagrams for noncrossing partitions involve an (n+1)-gon, while diagrams for clusters are triangulations of an (n + 3)-gon. The (n + 1) in this example is the Coxeter number h. Similarly, diagrams for noncrossing partitions in types B and D involve an h-gon, while diagrams for clusters inhabit an (h + 2)-gon.

Let o be a smallest W -orbit. Inspection of the classical examples described in Section 3 and of Figure 1 reveals that each ⟨c_{+}, c_{−}⟩-orbit in o either projects to a regular h-gon in P or to the origin of P.

We begin by representing each reflection t ∈ T by the diagram of the parabolic subgroup {1, t}. This is a set of parallel line segments connecting various points in the projected orbit. Some of the segments are labeled in the following sense: Each line segment with an endpoint at the origin is the projection of a specific line segment L in V, and the projected segment in P is considered to be labeled by the endpoint of L that projects to the origin. In particular, identical line segments in P arising from different line segments in the ambient space are considered to be distinguishable. Since each reflecting hyperplane intersects P in a line, in particular no reflecting hyperplane contains P. Thus no segment L whose endpoints are distinct points related by a reflection in W can project degenerately to the origin.

We explain the general construction with a running example in E_{6}. We take the bipartition S_{+} = {s_{1}, s_{4}, s_{6}}, S_{−} = {s_{2}, s_{3}, s_{5}} where the diagram of E_{6} is labeled as shown in Figure 10. Figure 1 shows the projection of a smallest E_{6}-orbit o into the Coxeter plane, including three points of which project to the origin. We refer to these these points as ⊕, ◯, and ⊖. Figure 11 shows the collections of segments, labeled as necessary to distinguish points at the origin, representing each simple reflection.

The line segments representing simple reflections −α_{i} for s_{i} ∈ S_{+} are perpendicular to the line L_{+} and the line segments representing simple reflections −α_{i} for s_{i} ∈ S_{−} are perpendicular to the line L_{−}. (These are the lines L_{±} from Section 2.4.) In Figure 11, the red (off-horizontal) line is L_{+} and the blue (horizontal) line is L_{−}. Reflecting a diagram through the line L_{ε} corresponds to conjugating a reflection (or a parabolic subgroup) by c_{ε}. Call an edge on an h-gon in the Coxeter plane distinguished if it is perpendicular to L_{+} or L_{−}. The distinguished edges are shown in red and blue in Figure 12.a.

The h-gons in the diagram are then expanded into (h + 2)-gons as follows: for each distinguished edge, a new vertex is placed in convex position with the other vertices, in such a way that the new vertex has the effect of subdividing the distinguished edge, as shown in Figure 12.b, with the new edges shown in green. Finally, each (h + 2)-gon is made regular, while preserving the distances of points to the origin. Also preserved are the relative orientations of the polygons: any two of the h-gons either interlace, like the two h-gons for E_{6}, or line up, like any pair of h-gons for E_{7}. (See Figure 1.) The corresponding (h + 2)-gons are made to line up or interlace accordingly. This construction of one regular (h + 2)-gon for each regular h-gon in the projected orbit is

\begin{matrix}s_{1} & s_{2} & s_{3} \\ s_{4} & s_{5} & s_{6} \end{matrix}

Figure 11. Collections of segments representing simple reflections in E_{6}

(a)  (b)  (c)

Figure 12. Making (h + 2)-gons from h-gons in E_{6}

unique up to a global scaling and rotation. Any multiple points at the origin in the projected orbit remain at the origin with the same multiplicity. Figure 12.c shows the regular (h + 2)-gons in the E_{6} example.

Once regular (h+2)-gons are constructed, the collections of line segments representing simple reflections in the original projection are used to represent negative simple roots. Specifically, each simple reflection s is represented by a collection of (labeled) line segments connecting pairs of vertices in the original h-gons. Our construction defines an inclusion from the (labeled) vertices of the projected orbit to the points of the new diagram. We use this inclusion to define a collection of line segments representing the negative simple root −α_{s}. Figure 13 shows the collections of labeled line segments representing the negative simple roots of E_{6}. Notice that some collinearities of points present in the diagrams for simple reflections are not present in the diagrams for negative simple roots.

In the case of planar diagrams for partitions, projection to the Coxeter plane defines a collection of line segments representing every reflection (and more generally every parabolic subgroup). The dihedral action on the diagrams given by symmetries of the

\begin{matrix}−α_{1} & −α_{2} & −α_{3} \\ −α_{4} & −α_{5} & −α_{6} \end{matrix}

Figure 13. Collections of segments representing negative simple roots in E_{6}

h-gons corresponds to the conjugation action of ⟨c_{+}, c_{−}⟩ on reflections. In contrast, in our construction of planar diagrams for almost positive roots, once the projected orbit has been altered as described above, there is no longer an identification, via projections, of positive roots with collections of segments. To map each positive root to a collection of segments, we first need an appropriate action of ⟨τ_{+}, τ_{−}⟩ on labeled line segments. The action is the dihedral action given by symmetries of the (h + 2)-gons, with alterations involving multiple points at the origin.

Let L′_{+} be the line through the origin such that reflection in L′_{+} preserves the diagrams representing negative simple roots −α_{i} for s_{i} ∈ S_{−}. Let L′_{−} be the line such that reflection in L′_{−} preserves the diagrams representing negative simple roots −α_{i} for s_{i} ∈ S_{+}. (Note the mixture of signs in the definitions of L′_{+} and L_{−}.) Figure 13 shows L′_{+} in red and L′_{−} in blue.

Suppose AB is a line segment in a diagram for an almost positive root. If neither A nor B lies at the origin then τ_{ε} acts on the segment by acting on each endpoint as a reflection through L′_{ε}. If one of the endpoints (say A) lies at the origin then, in most cases, τ_{ε} acts on B as a reflection through L′_{ε} and acts on A by the action of c_{ε}, which permutes the origin points. The exception is that, when A is at the origin and AB is perpendicular to L′_{ε}, the segment AB is fixed by τ_{ε}. This exceptional case occurs only when AB is one of the segments representing some −α_{i} for s_{i} ∈ S_{−ε}. In particular, τ_{ε} preserves the entire diagram of each −α_{i} for s_{i} ∈ S_{−ε}.

In the E_{6} example, the group ⟨c_{+}, c_{−}⟩ acts on the three points ⊕, ◯, and ⊖ at the origin according to the diagram in Figure 14, where edges marked + or − denote the action of c_{+} or c_{−} respectively. Figure 15 shows, in type E_{6}, the ⟨τ_{+}, τ_{−}⟩-orbit of the diagram of the negative simple roots −α_{1} and −α_{6}.

Having defined τ_{+} and τ_{−}, we require for any almost positive root β and ε ∈ {+.−} that the diagram for β and the diagram for τ_{ε}(β) be related by the action of τ_{ε} on

Figure 14. The action of ⟨c_{+}, c_{−}⟩ on origin points in E_{6}

Figure 15. The ⟨τ_{+}, τ_{−}⟩-orbit of −α_{1} (top left) and −α_{6} (bottom right) in type E_{6} diagrams. In light of Propositions 2.3 and 4.1, this requirement uniquely defines a collection of segments representing each almost positive root.

The assignment of diagrams to almost positive roots can also be easily explained in terms of the transformation τ_{+}τ_{−}. The action of τ_{+}τ_{−} on P is a rotation of order h + 2. To describe the action of τ_{+}τ_{−} on the labels of points at the origin, we define the gray zone to be the union of the two acute wedges defined by two lines through the origin: one perpendicular to L′_{+} and the other perpendicular to L′_{−}. The gray zone is shown in the almost positive root diagrams of Figures 13 and 15. When τ_{+}τ_{−} acts on a segment containing an origin point, the non-origin point is rotated while c_{+}c_{−} is applied to the label of the point at the origin. The exception to this rule occurs when the segment is rotated from one side of the gray zone to the other: in this case the label of the origin point is fixed. Inspection of Figure 15 reveals why the label of the origin point is fixed when the segment is rotated past the gray zone. (In the figure, this rule applies when τ_{+}τ_{−} is applied to −α_{1} or to −α_{6}.) When a segment contains an origin point and is incident to the gray zone, one of τ_{±} (in this case τ_{+}) fixes the segment, while the other (in this case τ_{−}) reflects the segment while swapping the label of the origin point with the label of the origin point of the antipodal segment. The swap of labels of the origin points must occur because the conjugation action of c_{ε} fixes a simple reflection α_{i} when s_{i} ∈ S_{ε}.

6. Criteria for compatibility

We now give a type-by-type account of the construction of Section 5. Computer data for each type is available as described in Section 1.3. In each type, we attempt to define a criterion for compatibility of almost positive roots. In types A_{n}, B_{n}, and I_{2}(m), the criterion is a simple noncrossing condition. Comparing the type-D construction with the model described in Section 4.3, we obtain a simple rule for compatibility in the presence of multiple origin points. Inspection of the group of type F_{4} reveals a criterion for compatibility in the presence of multiple (h+2)-gons, and, surprisingly, this criterion carries forward to the much more complicated diagrams of type H_{4}. By combining the multiple-origin-points rule from type D and the multiple-polygons rule from F_{4}, one hopes to obtain a criterion that works in generality. Indeed, the criterion works in type E_{6}, but breaks down when applied to type E_{7}. The criterion also fails for E_{8}, whose diagrams have no origin points.

In each of the types E_{6}, E_{7}, E_{8}, F_{4}, and H_{4}, we make ad hoc alterations of the Coxeter-plane diagrams which yield a model with a simple noncrossing condition on compatibility. In each case, alterations are made to the diagrams for negative simple roots, and then carried over to the positive roots by the action of ⟨τ_{+}, τ_{−}⟩.

6.1. Type A_{n}. We continue the notation of Section 3.1. The orbit {e_{i} : i ∈ [n + 1]} projects into P as a regular (n+1)-gon with vertices labeled according to the (n+1)-cycle c. Each reflection in W fixes all but two elements of the orbit, which are transposed. The simple reflections s_{i} = (i i + 1) act on the orbit as illustrated in Figure 16 for n = 7, and thus the “snake” configuration (see Figure 7) of Fomin and Zelevinsky’s model arises from the construction described in Section 5, rather than as an ad hoc construction. In the usual type-A model, the action of ⟨τ_{+}, τ_{−}⟩ on almost positive roots corresponds to the dihedral action on (n + 3)-gons. In the Coxeter-plane model, the

s_{1} s_{2} s_{3} s_{4} s_{5} s_{6} s_{7}

Figure 16. The action of simple reflections on the the smallest orbit of A_{7}

Figure 17. The G_{2} associahedron.

same correspondence holds by construction. Thus the criterion for compatibility of diagrams in the Coxeter plane is the usual model:

Compatibility Criterion 1. Two distinct almost positive roots, represented by collections C_{1} and C_{2} of line segments in P, are compatible if and only if no segment in C_{1} crosses any segment in C_{2}.

6.2. Type B_{n}. Arguing as in Section 6.1, the type-B case also reduces to the model from [13], described in Section 4.2, so Compatibility Criterion 1 describes compatibility.

6.3. Type I_{2}(m). In this case, h = m and W has an orbit of size m. The projected orbit is an m-gon, which is deformed to an (m+2)-gon. There are m+2 almost positive roots, and each corresponds to a maximal set of parallel diagonals of the (m + 2)-gon. One easily checks that the criterion for compatibility is again Compatibility Criterion 1. The clusters are shown in Figure 17 for the case I_{2}(6) = G_{2}. The edges shown connecting clusters are the edges of the corresponding associahedron.

6.4. Type H_{3}. As discussed in Section 3.5, a Coxeter group of type H_{3} has h = 10 and has smallest orbit of size 12. Coxeter-plane diagrams for the negative simple roots are shown in Figure 18. (Cf. the bottom row of Figure 3.) Two of the negative simple roots include segments connecting to origin points. To determine a criterion for compatibility, PSfrag replacements

−α_{1}

−α_{2}
−α_{3}

Figure 18. Negative simple roots in H_{3}.

Figure 19. Diagrams for clusters of type H_{3}.

−α_{1}  −α_{2}  −α_{3}  −α_{4}

Figure 20. Diagrams for almost positive roots of type D_{4}.

we check all 3 · 17 = 51 pairs −α_{s}, β where α_{s} is a negative simple root and β is an almost-positive root not equal to −α_{s}. The following simple criterion is correct:

Compatibility Criterion 2. Two distinct almost positive roots, represented by collections C_{1} and C_{2} of line segments in P, are compatible if and only if no segment in C_{1} crosses any segment in C_{2}, unless the two segments coincide (as unlabeled segments in P).

Compatibility Criterion 2 also defines compatibility in the cases A_{n}, B_{n}, and I_{2}(m). In these cases, there are no coinciding segments in the representations of distinct roots because there are no multiple points in the projected orbit.

A representative of each ⟨τ_{+}, τ_{−}⟩-orbit of clusters is shown in Figure 19. In this figure, the edges of the polygon are also drawn. The labeling of the origin points is irrelevant to Compatibility Criterion 2, but is indicated in Figure 19 by colors as in Figure 18. The leftmost diagram in Figure 19 includes the roots −α_{1} and −α_{3}, and thus has two red-blue pairs of coinciding segments attached to the origin. These pairs of segments are shown in black.

6.5. Type D_{n}. We continue the notation and conventions of Section 3.4. Diagrams for the negative simple roots of type D_{4}, shown in Figure 20, are representative of the diagrams for general n.

To compare the Coxeter-plane diagrams for almost positive roots to the usual model described in Section 4.3, we color the origin points red and blue so that the diagram for −α_{n−1} has a red segment lying to the left of the gray zone and a blue segment lying to the right of the gray zone. The diagram for −α_{n} will then have a blue segment lying to the left of the gray zone and a red segment lying to the right of the gray zone. The Coxeter-plane diagrams for almost positive roots correspond to the usual diagrams described in Section 4.3, equating a pair of half diameters with a (full) dashed diameter if the red half-diameter is to the left of the gray zone, and to a (full) gray diameter if the blue half-diameter is to the right of the gray zone.

The origin points were colored red and blue so as to make the correspondence hold for negative simple roots. Thus, to verify the correspondence, it remains only to show that the action of τ_{+} and τ_{−} preserves the correspondence. The case of non-diameters is trivial. The two origin points arise as the images of ±e_{n} under projection to P. If n is even, then c_{+} = s_{1}s_{3} ⋯ s_{n−1} ·s_{n}, which transposes e_{n} and −e_{n}, while c_{−} = s_{2}s_{4} ⋯ s_{n−2}, which fixes both e_{n} and −e_{n}. Since s_{n−1} and s_{n} are both in S_{+}, the exception in the definition of the action of τ_{ε} does not apply to τ_{+}. Thus τ_{+} reflects a half-diameter, keeping it on the same side of the gray zone, and changing its origin point. This corresponds to the action of τ_{+} on colored diameters, which applies the same reflection and reverses the color of the diameter. Similarly, τ_{−} reflects a half-diameter, keeping it on the same side of the gray zone, and fixes its origin point, corresponding to the action of τ_{−} on colored diameters, which applies the reflection and fixes the color of diameters. If n is odd, the correspondence works out similarly. The compatibility criterion in the usual D_{n} model translates to the following criterion for compatibility for Coxeter-plane diagrams, which is also correct in types A_{n}, B_{n}, I_{2}(m), and H_{3}.

Compatibility Criterion 3. Two distinct almost positive roots, represented by collections C_{1} and C_{2} of line segments in P, are compatible if and only if both of the following conditions holds:

(1) No segment in C_{1} crosses any segment in C_{2}, unless the two segments coincide (as unlabeled segments in P).

(2) If two segments — one from C_{1} and one from C_{2} — involve the same origin point then either both segments are contained in a common line or the union of the two segments does not cross the gray zone.

6.6. Type F_{4}. The Coxeter group of type F_{4} has Coxeter number h = 12 and smallest orbit of size 24. We label the diagram in a linear order and set S_{+} = {s_{2}, s_{4}} and S_{−} = {s_{1}, s_{3}}. The projected orbit consists of two 12-gons, which become two 14-gons in the cluster diagrams. Figure 21 shows diagrams for the negative simple roots in F_{4}. The diagram for −α_{2} has two sets of four nearly collinear points. Ordering the points from top to bottom, the diagram contains a segment connecting the first and third points and a segment connecting the second and fourth points. The diagram for −α_{3} also has two sets of four nearly collinear points, connected by segments in the same way.

It is immediately apparent that some crossing of segments must be allowed in the criterion for compatibility. For example, the negative simple roots −α_{3} and −α_{4} (pictured in Figure 21) are compatible. Figure 22 illustrates a crossing that must be allowed, and a crossing that must be ruled out. In each picture, the blue segments represent one of the roots and the green segments represent the other.

\begin{matrix}−α_{1} & −α_{2} \\ −α_{3} & −α_{4} \end{matrix}

Figure 21. Diagrams for negative simple roots in F_{4}

Compatibility appears to depend not only whether two segments cross, but where they cross, and what other segments they are incident to. Specifically, given a segment connecting points in the cluster diagram, the outer ring of the segment is the larger of the two (h + 2)-gons containing the endpoints of the segment. (If the two endpoints are on the same (h + 2)-gon then that (h + 2)-gon is the outer ring.) Given a pair of segments, the outer ring of the pair is the larger of the two outer rings. Given the diagrams for two positive roots, a segment is active with respect to the two roots if its outer ring R is the outermost (h + 2)-gon of the diagram or if it shares a point with an active segment whose outer ring is the next larger ring than R. Compatibility in F_{4} can be described by the following criterion:

Compatibility Criterion 4. Two distinct almost positive roots, represented by collections C_{1} and C_{2} of line segments in P, are compatible if and only if no two active segments cross within the annulus between the outer ring of the pair and the next smaller (h+2)- gon.

Compatibility Criterion 4 declares the two roots in Figure 22.a to be compatible because the two segments that cross are not active. The two roots in Figure 22.b are declared to be incompatible because two active segments cross.

The cluster diagrams for F_{4} can be altered so as to give a simpler criterion. The alteration has the disadvantage of being ad hoc, but has the advantage of producing simpler pictures. The altered negative simple roots are shown in Figure 23.

Compatibility of almost positive roots of type F_{4} is described by applying Compatibility Criterion 2 to the altered diagrams. To apply the criterion correctly, it is important to notice that the diagram for −α_{1} consists of six segments, arranged in two polygonal paths. Figure 24 shows the altered diagrams for the two pairs of roots whose unaltered diagrams appear in Figure 22.

(a)  (b)

Figure 22. a: Coxeter-plane diagram for two compatible roots in F_{4}. b: Coxeter-plane diagram for two incompatible roots in F_{4}.

\begin{matrix}−α_{1} & −α_{2} \\ −α_{3} & −α_{4} \end{matrix}

Figure 23. Altered negative simple roots in F_{4}

(a)  (b)

Figure 24. a: Altered diagram for two compatible roots in F_{4}. b: Altered diagram for two incompatible roots in F_{4}.

6.7. Type H_{4}. The Coxeter group of type H_{4} has Coxeter number h = 30 and smallest orbit of size 120. The projected orbit consists of four h-gons, which become four 32-gons in the cluster diagrams. Figures 25 and 26 show diagrams for the negative simple roots in H_{4}.

These diagrams appear almost hopelessly complex. But surprisingly, Compatibility Criterion 4 describes compatibility exactly in type H_{4} as well. In fact, something even nicer happens. For every pair of incompatible roots, there is a pair of segments, each with an endpoint on the outermost (h + 2)-gon, which cross outside the secondoutermost (h+2)-gon. One can alter the diagrams by erasing the parts of the segments that are inside the second-outermost (h + 2)-gon, and then moving the remaining parts slightly so that each remaining segment connects two vertices contained in the outermost two (h + 2)-gons. The altered diagrams for negative simple roots are illustrated in Figure 27. Compatibility of the resulting diagrams for almost positive roots is described by Compatibility Criterion 2.

6.8. Type E_{6}. The construction of Coxeter-plane diagrams for almost positive roots of type E_{6} was discussed in detail in Section 5. The diagrams constructed feature both multiple (h + 2)-gons and multiple origin points. The following is a natural common extension of Compatibility Criteria 3 and 4.

Compatibility Criterion 5. Let α_{1}, α_{2} be distinct almost positive roots, represented by collections C_{1} and C_{2} of line segments in P. Then α_{1} and α_{2} are compatible if and only if both of the following conditions holds:

(1) No two active segments cross within the annulus between the outer ring of the pair and the next smaller (h + 2)-gon.

(2) If two active segments — one from C_{1} and one from C_{2} — connect the same origin point to points on the innermost (h + 2)-gon, then either both segments are contained in a common line or the union of the two segments does not cross the gray zone.

Compatibility in type E_{6} is indeed described by Compatibility Criterion 5. But in fact, every Coxeter-plane diagram of a pair of incompatible roots exhibits a violation of condition (1) of Compatibility Criterion 5. In other words, compatibility in E_{6} is also described by Compatibility Criterion 4.

The E_{6} diagrams can also be altered to produce diagrams for which compatibility is described by Compatibility Criterion 2. The altered simple roots are shown in Figure 28.

6.9. Types E_{7} and E_{8}. Unfortunately, Compatibility Criterion 5 breaks down in type E_{7}. Figure 29 shows the diagrams for the almost positive roots −α_{3} and α_{3}, which are incompatible, but whose diagrams would be declared compatible by Compatibility Criterion 5. The counterexample seems to arise from the multiplicity of (h + 2)-gons, rather than from the multiplicity of origin points. Thus it is not surprising that a similar counterexample occurs in E_{8}. Ad hoc alterations of the Coxeter-plane diagrams yield diagrams for almost positive roots of types E_{7} and E_{8} for which compatibility is described by Compatibility Criterion 2.

\begin{matrix}−α_{1} \\ −α_{2} \end{matrix}

Figure 25. Diagrams for negative simple roots in H_{4}

\begin{matrix}−α_{3} \\ −α_{4} \end{matrix}

Figure 26. More diagrams for negative simple roots in H_{4}

\begin{matrix}−α_{1} & −α_{2} \\ −α_{3} & −α_{4} \end{matrix}

Figure 27. Altered diagrams for negative simple roots in H_{4}

\begin{matrix}−α_{1} & −α_{2} & −α_{3} \\ −α_{4} & −α_{5} & −α_{6} \end{matrix}

Figure 28. Altered diagrams for negative simple roots in E_{6} Figure 29. A counterexample to Compatibility Criterion 5 in E_{7}

7. Acknowledgments

The author wishes to thank Sergey Fomin, Jon McCammond, Frank Sottile and John Stembridge for helpful conversations.

References

[1] C. A. Athanasiadis and V. Reiner, Noncrossing partitions for the group D_{n}. SIAM J. Discrete Math 18 (2004), no. 2, 397–417.

[2] D. Armstrong, Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups. Mem. Amer. Math. Soc. 202 (2009), no. 949.

[3] H. Barcelo and E. Ihrig, Lattices of parabolic subgroups in connection with hyperplane arrangements. J. Algebraic Combin. 9 (1999), no. 1, 5–24.

[4] D. Bessis, The dual braid monoid. Ann. Sci. École Norm. Sup. (4) 36 (2003), no. 5, 647–683.

[5] P. Biane, Some properties of crossings and partitions. Discrete Math. 175 (1997), no. 1–3, 41–53.

[6] P. Biane, F. Goodman and A. Nica, Non-crossing cumulants of type B. Trans. Amer. Math. Soc. 355 (2003), no. 6, 2263–2303.

[7] A. Björner and F. Brenti, Combinatorics of Coxeter groups. Graduate Texts in Mathematics, 231, Springer, New York, 2005.

[8] N. Bourbaki, Lie groups and Lie algebras. Chapters 4–6. Springer-Verlag, Berlin, 2002.

[9] T. Brady, A partial order on the symmetric group and new K(π, 1)’s for the braid groups. Adv. Math. 161 (2001), no. 1, 20–40.

[10] T. Brady and C. Watt, K(π, 1)’s for Artin groups of finite type. Geom. Dedicata 94 (2002), 225–250.

[11] T. Brady and C. Watt, Non-crossing partition lattices in finite real reflection groups. Trans. Amer. Math. Soc. 360 (2008), no. 4, 1983–2005.

[12] H. Coxeter, Regular Polytopes, Methuen & Co., Ltd., London, 1948.

[13] S. Fomin and A. Zelevinsky, Y-systems and generalized associahedra. Ann. of Math. 158 (2003), 977–1018.

[14] S. Fomin and A. Zelevinsky, Cluster Algebras II: Finite Type Classification. Inventiones Mathematicae 154 (2003), 63–121.

[15] J. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, 29, Cambridge Univ. Press, 1990.

[16] G. Kreweras, Sur les partitions non croisées d’un cycle. Discrete Math. 1 (1972), no. 4, 333–350.

[17] N. Reading, Clusters, Coxeter-sortable elements and noncrossing partitions. Trans. Amer. Math. Soc. 359 (2007), no. 12, 5931–5958.

[18] N. Reading and D. Speyer, Sortable elements in infinite Coxeter groups. Trans. Amer. Math. Soc.,

to appear; arχiv:0803.2722.

[19] V. Reiner, Non-crossing partitions for classical reflection groups. Discrete Math. 177 (1997), no. 1–3, 195–222.

[20] R. Simion, Noncrossing partitions. Discrete Math. 217 (2000), no. 1–3, 367–409.

[21] R. Steinberg, Finite reflection groups. Trans. Amer. Math. Soc. 91 (1959) 493–504.

Department of Mathematics, North Carolina State University, Raleigh, North Carolina 27695-8205, USA

  E-mail address: nathan reading@ncsu.edu
  URL: http://www4.ncsu.edu/∼nreadin