Séminaire Lotharingien de Combinatoire 54A (2006), Article B54Aj

BERGMAN COMPLEXES, COXETER ARRANGEMENTS, AND GRAPH ASSOCIAHEDRA

FEDERICO ARDILA, VICTOR REINER, AND LAUREN WILLIAMS*

Abstract. Tropical varieties play an important role in algebraic geometry. The Bergman complex B(M) and the positive Bergman complex B^{+}(M) of an oriented matroid M generalize to matroids the notions of the tropical variety and positive tropical variety associated to a linear ideal. Our main result is that if A is a Coxeter arrangement of type Φ with corresponding oriented matroid M_{Φ}, then B^{+}(M_{Φ}) is dual to the graph associahedron of type Φ, and B(M_{Φ}) equals the nested set complex of A. In addition, we prove that for any orientable matroid M, one can find |μ(M)| different reorientations of M such that the corresponding positive Bergman complexes cover B(M), where μ(M) denotes the Möbius function of the lattice of flats of M.

1. Introduction

In this paper we study the Bergman complex and the positive Bergman complex of a Coxeter arrangement. We relate them to the nested set complexes that arise in De Concini and Procesi’s wonderful arrangement models [11, 12], and to the graph associahedra introduced by Carr and Devadoss [8], by Davis, Januszkiewicz, and Scott [10], and by Postnikov [19].

The Bergman complex of a matroid is a pure polyhedral complex which can be associated to any matroid. It was first defined by Sturmfels [23] in order to generalize to matroids the notion of a tropical variety associated to a linear ideal. The Bergman complex can be described in terms of the lattice of flats of the matroid, and is homotopy equivalent to a wedge of spheres, as shown by Ardila and Klivans [1].

The positive Bergman complex B^{+}(M) of an oriented matroid M is a subcomplex of the Bergman complex of the underlying unoriented matroid \underline{M}. It generalizes to oriented matroids the notion of the positive tropical variety associated to a linear ideal. B^{+}(M) depends on a choice of acyclic orientation of M, and as one varies this acyclic orientation, one gets a covering of the Bergman complex of \underline{M}; we will prove this in Section 3. The positive Bergman complex can be described in terms of the Las Vergnas face lattice of M and it is homeomorphic to a sphere, as shown by Ardila, Klivans, and Williams [2].

Graph associahedra are polytopes which generalize the associahedron, which were discovered independently by Carr and Devadoss [8], by Davis, Januszkiewicz, and Scott [10], and by Postnikov [19]. There is an intrinsic tiling by associahedra of the Deligne–Knudsen–Mumford compactification of the real moduli space of curves \overline{M_{0}^{n}(ℝ)}, a space which is related to the Coxeter complex of type A. The motivation for Carr and Devadoss’ work was the desire to generalize this phenomenon to all simplicial Coxeter systems.

* Supported in part by the by the National Science Foundation under Grant No. DMS-0502858.

Let A_{Φ} be the Coxeter arrangement corresponding to the (possibly infinite, possibly non-crystallographic) root system Φ associated to a Coxeter system (W, S) with diagram Γ; see Section 6 below. Choose a region R of the arrangement, and let M_{Φ} be the oriented matroid associated to A_{Φ} and R. In this paper we prove:

Theorem 1.1. The positive Bergman complex B^{+}(M_{Φ}) of the arrangement A_{Φ} is dual to the graph associahedron P (Γ).

In particular, the cellular sphere B^{+}(M_{Φ}) is actually a simplicial sphere, and a flag (or clique) complex.

This result is also related to the wonderful model of a hyperplane arrangement and to nested set complexes. The wonderful model of a hyperplane arrangement is obtained by blowing up the non-normal crossings of the arrangement, leaving its complement unchanged. De Concini and Procesi [11] introduced this model in order to study the topology of this complement. They showed that the nested sets of the arrangement encode the underlying combinatorics. Feichtner and Kozlov [12] gave an abstract notion of the nested set complex for any meet-semilattice, and Feichtner and Müller [13] studied its topology. Recently, Feichtner and Sturmfels [14] studied the relation between the Bergman complex and the nested set complexes (see Section 7 below).

In this paper we also prove for finite root systems Φ:

Theorem 1.2. The Bergman complex B(M_{Φ}) of A_{Φ} equals its nested set complex.

In particular, the cell complex B(M_{Φ}) is actually a simplicial complex.

2. The Bergman complex and the positive Bergman complex

Our goal in this section is to explain the notions of the Bergman complex of a matroid and the positive Bergman complex of an oriented matroid which were studied in [1] and [2]. In order to do so we must review a certain operation on matroids and oriented matroids.

Definition 2.1. Let M be a matroid or oriented matroid of rank r on the ground set [n], and let ω ∈ ℝ^{n}. Regard ω as a weight function on M, so that the weight of a basis B = {b_{1}, …, b_{r}} of M is given by ω_{B} = ω_{b_{1}} + ω_{b_{2}} + ⋯ + ω_{b_{r}}. Let B_{ω} be the collection of bases of M having minimum ω-weight. (If M is oriented, then bases in B_{ω} inherit orientations from bases of M.) This collection is itself the set of bases of a matroid (or oriented matroid) which we call M_{ω}.

It is not obvious that M_{ω} is well-defined. However, when M is an unoriented matroid, we can see this by considering the matroid polytope of M: the face that minimizes the linear functional ω is precisely the matroid polytope of M_{ω}. For a proof that M_{ω} is well-defined when M is oriented, see [2].

BERGMAN COMPLEXES, COXETER ARRANGEMENTS, AND GRAPH ASSOCIAHEDRA 3

Notice that M_{ω} will not change if we translate ω or scale it by a positive constant. We can therefore restrict our attention to the sphere

S^{n−2} := { ω ∈ ℝ^{n} : ω_{1} + ⋯ + ω_{n} = 0 , ω_{1}^{2} + ⋯ + ω_{n}^{2} = 1}.

The Bergman complex of M will be a certain subset of this sphere.

The matroid M_{ω} depends only on a certain flag associated to ω.

Definition 2.2. Given ω ∈ ℝ^{n}, let F(ω) denote the unique flag of subsets

(1)  ∅ = F_{0} ⊂ F_{1} ⊂ ⋯ ⊂ F_{k} ⊂ F_{k+1} = [n]

such that ω is constant on each set F_{i} \ F_{i−1} and satisfies ω|_{F_{i}\F_{i−1}} < ω|_{F_{i+1}\F_{i}}. We call F(ω) the flag of ω, and we say that the weight class of ω or of the flag F is the set of vectors ν such that F(ν) = F.

It is shown in [1] that M_{ω} depends only on the flag F := F(ω); specifically

(2)  M_{ω} = ⨁_{i=1}^{k+1} F_{i}/F_{i−1},

where F_{i}/F_{i−1} is obtained from the matroid restriction of M to F_{i} by quotienting out the flat F_{i−1}. Hence we also refer to this oriented matroid M_{ω} as M_{F}.

Definition/Theorem 2.3. [1] The Bergman complex of a matroid M on the ground set [n] is the set

B(M) = {ω ∈ S^{n−2} : M_{F(ω)} has no loops}
= {ω ∈ S^{n−2} : F(ω) is a flag of flats of M}.

Since the matroid M_{ω} depends only on the weight class that ω is in, the Bergman complex of M is the disjoint union of the weight classes of flags F such that M_{F} has no loops. We say that the weight class of a flag F is valid for M if M_{F} has no loops.

There are two polyhedral subdivisions of B(M), one of which is clearly finer than the other.

Definition 2.4. The fine subdivision of B(M) is the subdivision of B(M) into valid weight classes: two vectors ω and ν of B(M) are in the same class if and only if F(ω) = F(ν). The coarse subdivision of B(M) is the subdivision of B(M) into M_{ω}- equivalence classes: two vectors ω and ν of B(M) are in the same class if and only if M_{ω} = M_{ν}. We call these equivalence classes fine cells and coarse cells; however, by default, any reference to a cell of B(M) will refer to a coarse cell.

The fine subdivision gives the following corollary of Theorem 2.3.

Corollary 2.5. [1] Let M be a matroid of rank r. The fine subdivision of the Bergman complex B(M) is a geometric realization of Δ(L_{M} −{ ˆ0 , ˆ1 }), the order complex of the proper part of the lattice of flats of M. It follows that B(M) is homotopy equivalent to a wedge of |μ(M)| spheres of dimension r − 2, where μ(M) denotes the Möbius function from the bottom to the top element in L_{M}.

There are positive analogues of all of the above definitions and theorems. First we must give the definition of positive covectors and positive flats.

Definition 2.6. Let M be an acyclic oriented matroid on the ground set [n]. We say that a covector v ∈ {+, −, 0}^{n} of M is positive if each of its entries is + or 0. We say that a flat of M is positive if it is the 0-set of a positive covector.

Observation 2.7. If M is the acyclic oriented matroid corresponding to a hyperplane arrangement A whose orientation is determined by a choice of region R, then the positive flats are in correspondence with the faces of R. In this case we will also say that the flats which are positive are “positive with respect to R.”

For example, consider the braid arrangement A_{3}, consisting of the six hyperplanes x_{i} = x_{j}, 1 ≤ i < j ≤ 4 in ℝ^{4}. Figure 1 illustrates this arrangement, when intersected with the hyperplane x_{4} = 0 and the sphere x_{1}^{2} + x_{2}^{2} + x_{3}^{2} = 1. Let R be the region specified by the inequalities x_{1} ≥ x_{2} ≥ x_{3} ≥ x_{4}, and let M_{A_{3}} be the oriented matroid corresponding to the arrangement A_{3} and the region R. Then the positive flats are ∅, 1, 4, 6, 124, 16, 456 and 123456.

Figure 1. The braid arrangement A_{3}.

The positive Bergman complex counterpart to Definition/Theorem 2.3 is the following.

Definition/Theorem 2.8. [2] The positive Bergman complex of M is

B^{+}(M) = {ω ∈ S^{n−2} : M_{F(ω)} is acyclic}
= {ω ∈ S^{n−2} : F(ω) is a flag of positive flats of M}.

Within each equivalence class of the coarse subdivision of B(M), the vectors ω give rise to the same unoriented M_{ω}. Since the orientation of M_{ω} is inherited from that of M, they also give rise to the same oriented matroid M_{ω}. Therefore each coarse cell of B(M) is either completely contained in or disjoint from B^{+}(M). Thus B^{+}(M) inherits the coarse and the fine subdivisions from B(M), and each subdivision of B^{+}(M) is a subcomplex of the corresponding subdivision of B(M).

Recall that the Las Vergnas face lattice F_{ℓv}(M) is the lattice of positive flats of M, ordered by containment. Note that the lattice of positive flats of the oriented matroid M sits inside L_{M}, the lattice of flats of M. By Observation 2.7, if M is the oriented matroid of the arrangement A and the region R, then F_{ℓv}(M) is the face poset of R.

Corollary 2.9. [2] Let M be an oriented matroid of rank r. Then the fine subdivision of B^{+}(M) is a geometric realization of Δ(F_{ℓv}(M)−{ ˆ0 , ˆ1 }), the order complex of the proper part of the Las Vergnas face lattice of M. It follows that the positive Bergman complex of an oriented matroid is homeomorphic to an (r − 2)-sphere.

Example 2.10. Let M be the oriented matroid from Figure 1. The positive flats of M are {∅, 1, 4, 6, 16, 124, 456, 123456}. The lattice of positive flats of M is shown in bold in Figure 2, within the lattice of flats of M.

Figure 2. The lattice of positive flats within the lattice of flats.

3. Further theory of Bergman and positive Bergman complexes

This section develops some further theory of Bergman complexes in the setting of both unoriented and oriented matroids. These results will be used later, in the proofs of Theorems 1.1 and 1.2, but are also of independent interest.

3.1. Covering the Bergman complex with positive Bergman complexes. We know that, for any acyclic orientation of a matroid M of rank r, the corresponding positive Bergman complex is homeomorphic to an (r − 2)-sphere, while the Bergman complex B(M) of the (unoriented) matroid M is homotopy equivalent to |μ(M)| such (r − 2)-spheres. In fact, as we vary the acyclic reorientations (that is, the topes or maximal covectors) of M, the corresponding positive Bergman complexes cover B(M). The first goal of this section is to give a polyhedral realization of this statement: for any orientable matroid M, we exhibit |μ(M)| reorientations of M whose positive Bergman complexes cover B(M).

The motivating example is the matroid M of a real central hyperplane arrangement A. Let H be an affine hyperplane which is generic with respect to A. Consider the regions of A which have a non-empty and bounded intersection with H; we will see that there are |μ(M)| of them. We claim that the positive Bergman complexes corresponding to these regions cover the Bergman complex of M.

For general oriented matroids, one can mimic the previous construction. Let M = (E, L) be an oriented matroid of rank r with ground set E and collection of covectors L ⊆ {+, −, 0}^{E}. Let L_{g} ⊆ {+, −, 0}^{E∪{g}} be an extension of L by a generic element g ∉ E; this means that g is not in the closure of any set A ⊂ E with r(A) < r. Let N be the affine oriented matroid N = (E ∪ {g}, L_{g}, g) with distinguished element g (which is not a loop).

Let L_{g}^{+} = {X ∈ L_{g} | X_{g} = +} and let L̂_{g}^{+} = L_{g}^{+} ∪ {ˆ0, ˆ1} be the affine face lattice of N. Let L_{g}^{++} = {X ∈ L_{g}^{+} | (L_{g})_{≤X} ⊆ L̂_{g}^{+}} be the bounded complex of N. The maximal elements of L_{g}^{+} are the topes, and the maximal elements of L_{g}^{++} are the bounded topes with respect to g. Each bounded tope of L_{g} with respect to g determines a tope of L by deletion of g; we call these the bounded topes of L with respect to g, and write B^{++} for the set of such topes.

In the realizable case, M is the oriented matroid of A with respect to a chosen region. Instead of the generic affine hyperplane H, we consider the translate g of H through the origin, declaring H to be on the positive side of g. The arrangement A ∪ {g} determines the generic extension N of M. The faces in L_{g}^{+} correspond to the faces of A that intersect H, and the faces in L_{g}^{++} correspond to the faces of A that have a non-empty and bounded intersection with H. The topes in B^{++} are in one-to-one correspondence with the bounded regions of the arrangement A ∪ H.

The beta invariant β(N) of a matroid N is given by

β(N) = (−1)^{r(N)} ∑ μ_{N}(X)r(X),

summing over all flats X of N. Here μ_{N} denotes the Möbius function of the lattice L_{N}.

Proposition 3.1. [15, 18] An affine oriented matroid N with distinguished element g has exactly β(N) topes that are bounded with respect to g.

Lemma 3.2. (cf. [15, Theorem 3.2]) If N is a generic extension of M by g, then

β(N) = (−1)^{r(N)}μ(M).

Proof. For any nonloop, noncoloop element g in a matroid N, one has [26, Theorem 7.3.2(c)]

(3)  β(N) = β(N − g) + β(N/g).

Since g is generic, the lattice L_{N/g} is simply the truncation of L_{N−g} in which one removes the entire rank r − 1 (but keeps the element ˆ1), where r = r(N). Hence starting with equation (3), one has on the right-hand side two sums of the quantities μ(X)r(X) with X ranging over the two lattices L_{N−g} and L_{N/g}, with opposite signs in front of the two sums because the ranks of N − g and N/g differ by one. Thus the terms with X of rank at most r − 2 all cancel, and one is left with the terms of rank at least r − 1 in the two sums:

(−1)^{r}β(N) = r · μ(N − g) + (r − 1) (  ∑_{X of rank r−1 in L_{N−g}} μ(X)) − (r − 1)μ(N/g)
= r · μ(N − g) + (r − 1) (μ(N/g) − μ(N − g)) − (r − 1)μ(N/g)
= μ(N − g),

as we wished to show. □

Theorem 3.3. Let M be an oriented matroid, and N an extension by a generic element g. Let T_{1}, …, T_{|μ(M)|} be the bounded topes in M with respect to g. Then the |μ(M)| positive Bergman complexes corresponding to the T_{i}s cover the Bergman complex of the unoriented matroid \underline{M}.

Proof. There is no harm in assuming that M is simple and loop and coloop-free. In view of Definition/Theorem 2.8, it suffices to show that, for any flag of flats F = {∅ ⊂ F_{1} ⊂ ⋯ ⊂ F_{r−1} ⊂ E}, we can find a tope T_{i} with 1 ≤ i ≤ |μ(M)| such that all the F_{j}s are positive with respect to T_{i}. This means that T_{i} has a flag of subfaces (covectors with some entries of T_{i} replaced by zeroes) X_{1} > … > X_{r−1} such that X_{i} spans F_{i}.

We proceed by induction, where the base case is trivial. Now consider the rank r−1 oriented matroid M/F_{1} (which, in the realizable case, corresponds to the arrangement that A determines on the hyperplane F_{1}). The set F_{1} is also a flat in N, and N/F_{1} is also a generic extension of M/F_{1} by g. Consider the flag of flats

F′ = {∅ ⊂ F_{2} − F_{1} ⊂ ⋯ ⊂ F_{r−1} − F_{1} ⊂ E − F_{1}}

of M/F_{1}. By the induction hypothesis, we can find a tope T′, bounded in M/F_{1} with respect to g, which has a flag of faces T′ = Y_{1} > Y_{2} > … > Y_{r−1} such that Y_{i} spans F_{i} − F_{1} in M/F_{1}.

Since M is simple, the flat F_{1} consists of a single element; call it e. Then the covector Y_{i} of M/F_{1} comes from the covector X_{i} of M which is identical to Y_{i}, except for the extra entry (X_{i})_{e} = 0. Clearly X_{1} > ⋯ > X_{r−1} and X_{i} spans F_{i}.

Since e is not a loop of M, some covectors Z^{+} and Z^{−} of M have Z_{e}^{+} = + and Z_{e}^{−} = −. The topes T^{+} = X_{1} ∘ Z^{+} and T^{−} = X_{1} ∘ Z^{−} are identical to Y_{1} = T′, except for the extra entries (T^{+})_{e} = + and (T^{−})_{e} = −. The X_{i}s are faces of both T^{+} and T^{−}, so it remains to show that at least one of T^{+} and T^{−} is bounded with respect to g in M.

Suppose this is not the case. Then we can find non-zero covectors A ≤ T^{+} ∪ {g} and B ≤ T^{−} ∪ {g} of N such that A_{g} = B_{g} = 0. If A_{e} = 0, then A − e would be a non-zero covector in N/F_{1}, smaller than T′ ∪ {g} and satisfying (A − e)_{g} = 0; this would contradict the boundedness of T′ in M/F_{1} with respect to g. Therefore we have A_{e} = + and, similarly, B_{e} = −.

Consider now the covectors A and B of N and their separator e. In fact, e is the only separator of A and B, because

\begin{aligned}A ≤ T^{+} ∪ \{g\} & = T′ ∪ \{e\} ∪ \{g\} \\ B ≤ T^{−} ∪ \{g\} & = T′ ∪ \{\overline{e}\} ∪ \{g\}. \end{aligned}

Using the covector axiom (L3) [4, Theorem 4.1.1], we will find a covector C of N such that C_{e} = 0 and C_{f} = (A ∘ B)_{f} = (B ∘ A)_{f} for all f ≠ e. Thus C − e is a covector of N/F_{1} which is smaller than T′ ∪ {g} and satisfies (C − e)_{g} = 0. This contradicts the boundedness of T′ in M/F_{1} with respect to g, unless C − e = 0. But if this were the case, then e would be a coloop of N. In the presence of the generic element g, this is impossible: E − e has corank at most 1 in M, so (E − e) ∪ {g} is spanning in N, without containing e. This completes the proof. □

Theorem 3.3 is closely related to recent work of Björner and Wachs. In [5], they construct a basis for the homology of the geometric lattice of an orientable matroid M, which is indexed by the bounded topes of M with respect to an extension by a generic element g.

3.2. The forest of a flag, and coarse cells in the Bergman complex. Recall from Definition 2.4 that the Bergman complex B(M) has two subdivisions into cells. Its fine subdivision has cells indexed by all flags F of flats of M. These fine cells then group themselves into the cells of the coarse subdivision, according to their associated matroids M_{F}. It turns out that one can always determine M_{F}, and hence the coarse cell to which a flag F corresponds, based on a certain labelled forest T_{F} associated to F. These forests also turn out (see Section 7) to be closely related to the complex of nested sets^{1}.

Recall that the connected components of a matroid M are the equivalence classes for the following equivalence relation on the ground set E of M: say e ∼ e′ for two elements e, e′ in E whenever they lie in a common circuit of M, and then take the transitive closure of ∼. Recall also that every connected component is a flat of M, and M decomposes (uniquely) as the direct sum of its connected components.

Definition 3.4. To each flag F of flats of a matroid M indexed as in (1), associate a forest T_{F} of rooted trees, in which each vertex v is labelled by a flat F (v), as follows:

• For each connected component F of the matroid M, create a rooted tree (as specified below) and label its root vertex with F.

• For each vertex v already created, and already labelled by some flat F (v) which is a connected component of some flat F_{j} in the flag F, create children of v labelled by each of the connected components of F_{j−1} which are contained properly in F (v).

1The material in this subsection is closely related to results of Feichtner and Sturmfels [14, Section 4 and end of Section 3]; in particular, see our Remark 3.10. However, the crucial notion of a circuitous base (Definition 3.6, Proposition 3.9) does not appear in their work, and we have chosen to explain this subsection in our language so as to keep the paper more self-contained.

Alternatively, one can construct the forest T_{F} by listing all the connected components of all the flats in F, and partially ordering them by inclusion.

Proposition 3.5. For any flag F of flats in a matroid M, the labelled forest T_{F} determines the matroid M_{F}.

Proof. Recall the expression (2) for M_{F}. By construction of T_{F}, every component of F_{i} is F (v) for some unique vertex v, and every component of F_{i−1} lying in F (v) is F (v′) for some child v′ of v. Since quotients commute with direct sums, this gives

(4)  M_{F} = ⨁_{vertices v of T_{F}} (F (v)/ ⨁_{children v′ of v} F (v′)) .

□

In general, the converse of this proposition does not hold; one can have M_{F} = M_{F′} without T_{F} = T_{F′}. For example (cf. [14, Example 1.2]), in the matroid M on ground set E = {1, 2, 3, 4, 5} having rank 3 and circuits {123, 145, 2345}, the two flags

\begin{aligned}F & := (∅ ⊂ 1 ⊂ 123 ⊂ 12345) \\ F′ & := (∅ ⊂ 1 ⊂ 145 ⊂ 12345) \end{aligned}

exhibit this possibility.

However, there is at least one nice hypothesis that allows one to reconstruct T_{F} from M_{F}. Given a base B of a matroid M on ground set E, and any element e ∈ E\B, there is a unique circuit of M contained in B ∪ {e}, called the basic circuit circ(B, e). Note that the flat spanned by circ(B, e) will always be a connected flat.

Definition 3.6. Say that a base B of a matroid M is circuitous if every connected flat spanned by a subset of B is spanned by the basic circuit circ(B, e) for some e ∈ E\B.

Note that the basic circuit circ(B, e) spanning the connected flat F must be (F ∩ B) ∪ {e}. Before we state our proposition, we prove two useful lemmas.

Lemma 3.7. Let F be a flat in a matroid M, spanned by some independent set I. Then every connected component of F is spanned by some subset of I, namely, by the intersection of that component with I.

Proof. Let r denote the rank function for M, and let F have components F_{1}, …, F_{t}. Then

∑_{i} r(F_{i}) = r(F) = |I| = ∑_{i} |F_{i} ∩ I| = ∑_{i} r(F_{i} ∩ I) ≤ ∑_{i} r(F_{i}),

which means we must have an equality for each i: r(F_{i} ∩ I) = r(F_{i}). In other words, F_{i} ∩ I spans F_{i}. □

Given a subset A ⊂ E of the ground set of a matroid, let cl(A) denote its closure, that is, the flat spanned by A.

Lemma 3.8. Let F ⊂ G be flats of a matroid that are spanned by subsets of a circuitous base B. If G is connected, then G/F is also connected.

Proof. Let I_{F} = F ∩ B and I_{G} = G ∩ B; these are bases for F and G, respectively. Also, I_{F} ⊂ I_{G}, and I_{G} − I_{F} is a base for the quotient G/F. Since G is a connected flat spanned by a subset of the circuitous base B, there exists e in G − B such that cl(circ(B, e)) = G, and circ(B, e) = I_{G} ∪ {e}.

We now claim that

circ_{G/F} (I_{G} − I_{F} , e) = I_{G} − I_{F} ∪ {e}.

We need to check that I_{G} − I_{F} ∪ {e} − {g} is independent in G/F for any g ∈ I_{G} − I_{F} ∪ {e}. Since I_{F} is a basis of F, this follows from the fact that I_{G} ∪ {e} − {g} is independent in G. We conclude by observing that G/F is the flat spanned by circ(I_{G} − I_{F} , e), so it is connected. □

Proposition 3.9. Let B be a circuitous base of a matroid M. Then for any two flags F, F′ of flats spanned by subsets of B, one has M_{F} = M_{F′} if and only if T_{F} = T_{F′}.

Proof. We start by making two observations about the matroid M_{F} and the tree T_{F}.

First we observe that, under these hypotheses, the expression (4) is actually the decomposition of M_{F} into its irreducible components. By Lemma 3.7, the F (v)s are connected flats spanned by subsets of B. The direct sums ⊕_{v′}F (v′) are also spanned by subsets of B. Lemma 3.8 then guarantees that F (v)/ ⊕_{v′} F (v′) is connected for each vertex v of the tree.

Secondly we show that, among the sets cl(circ(B, e)) with e in F (v)\ ∪ F (v′) and not in B, there is a maximum one under containment, which is precisely F (v).

Take any e in F (v)\ ∪ F (v′) and not in B. The flat F (v) is spanned by a subset I of B, and I ∪ {e} is dependent. Therefore circ(B, e) ⊆ I ∪ {e} ⊆ F (v), which implies cl(circ(B, e)) ⊆ F (v).

Now, since F (v) is a connected flat spanned by a subset of B, F (v) = cl(circ(B, e)) for some e ∈ E\B. Clearly e ∈ F (v). If e was in F (v′) for some child v′ of v, the argument of the previous paragraph would imply that cl(circ(B, e)) ⊆ F (v′). Therefore e ∈ F (v)\ ∪ F (v′).

The two previous observations give us a procedure to recover the tree T_{F} from the matroid M_{F}. The first step is to decompose M_{F} into its connected components M_{1}, …, M_{t}, having accompanying ground set decomposition E = E_{1} ⊔ ⋯ ⊔ E_{t}. The second step is to recover the flat corresponding to each M_{i}, as the maximum cl(circ(B, e)) with e ∈ E_{i}\B. The labelled forest T_{F} is simply the poset of inclusions among these flats. □

It will turn out that the simple roots Δ of a root system Φ always form a circuitous base for the associated matroid M_{Φ}; see Proposition 6.1(iii) below.

Remark 3.10. When the matroid M is connected, the forest T_{F} constructed above is a rooted tree. It coincides with the tree constructed by Feichtner and Sturmfels in [14, Proposition 3.1] when they choose the minimal building set for their lattice. In this way, Proposition 3.5 follows from [14, Theorem 4.4].

4. Graph associahedra

To any graph one can associate a polytope called a graph associahedron; the graph associahedron associated to a chain is the usual associahedron. These polytopes were discovered independently by Carr and Devadoss [8], Davis, Januszkiewicz, and Scott [10], and Postnikov [19]. There is an intrinsic tiling by associahedra of the Deligne– Knudsen–Mumford compactification of the real moduli space of curves \overline{M_{0}^{n}(ℝ)}, a space which is related to the Coxeter complex of type A. The motivation for the work of Carr and Devadoss was the desire to generalize this phenomenon to other Coxeter systems.

In order to define graph associahedra, we must introduce the notions of tubes and tubings. We follow the presentation of [8].

Definition 4.1. Let Γ be a graph. A tube is a nonempty set of nodes of Γ whose induced graph is a proper, connected subgraph of Γ. There are three ways that two tubes can interact on the graph:

• Tubes are nested if t_{1} ⊂ t_{2}.

• Tubes intersect if t_{1} ∩ t_{2} ≠ ∅ and t_{1} ⊄ t_{2} and t_{2} ⊄ t_{1}.

• Tubes are adjacent if t_{1} ∩ t_{2} = ∅ and t_{1} ∪ t_{2} is a tube in Γ. Tubes are compatible if they do not intersect and they are not adjacent. A tubing T

of Γ is a set of tubes of Γ such that every pair of tubes in T is compatible. A k-tubing is a tubing with k tubes.

Graph-associahedra are defined via a construction which we will now describe.

Definition 4.2. Let Γ be a graph on n nodes. Let Δ_{Γ} be the n − 1 simplex in which each facet corresponds to a particular node. Note that each proper subset of nodes of Γ corresponds to a unique face of Δ_{Γ}, defined by the intersection of the faces associated to those nodes. The empty set corresponds to the face which is the entire polytope Δ_{Γ}. For a given graph Γ, truncate faces of Δ_{Γ} which correspond to 1-tubings in increasing order of dimension (i.e. first truncate vertices, then edges, then 2-faces, …). The resulting polytope P (Γ) is the graph associahedron of Carr and Devadoss.

Figure 3 illustrates the construction of the graph associahedron of a Coxeter diagram of type D_{4}. We start with a simplex, whose four facets correspond to the nodes of the diagram. In the first step, we truncate three of the vertices, to obtain the second polytope shown. We then truncate three of the edges, to obtain the third polytope shown. In the final step, we truncate the four facets which all correspond to tubes. This step is not shown in Figure 3, since it does not affect the combinatorial type of the polytope.

When the graph Γ is the n-element chain, the polytope P (Γ) is the associahedron A_{n−1}. One can see this by considering an easy bijection between valid tubings and parenthesizations of a word of length n − 1, as illustrated in Figure 4.

Carr and Devadoss proved that the face poset of P (Γ) can be described in terms of valid tubings.

Figure 3. P (D4) \begin{matrix}c \\ ◯ \end{matrix}Satyan Devadoss

Figure 4. The associahedron A_{2} is the graph associahedron of a 3-

element chain. \begin{matrix}c \\ ◯ \end{matrix}Satyan Devadoss

Theorem 4.3. [8] The face poset of P (Γ) is isomorphic to the set of valid tubings of Γ, ordered by reverse containment: T < T′ if T is obtained from T′ by adding tubes.

Corollary 4.4. [8] When Γ is a path with n − 1 nodes, P (Γ) is the associahedron A_{n} of dimension n. When Γ is a cycle with n − 1 nodes, P (Γ) is the cyclohedron W_{n}.

5. Coxeter systems, the Tits cone, and parabolic flats

In this section we review the notion of a Coxeter system (W, S), and explain two ways of thinking about the associated matroid. The first way is to consider the vector configuration of positive roots Φ^{+} of the corresponding root system Φ in V := ℝ^{|S|}. The second way is to consider a certain arrangement A_{Φ} of hyperplanes in V^{∗} intersecting a W -invariant convex cone known as the Tits cone. We attempt to give a careful discussion of the issues that arise when W is infinite, for example, how to define the Bergman complex, and what kinds of flats of the associated matroid are relevant for Bergman complexes and wonderful compactifications.

A Coxeter system is a pair (W, S) consisting of a group W and a set of generators S ⊂ W, subject only to relations of the form

(ss′)^{m(s,s′)} = 1,

where m(s, s) = 1, m(s, s′) = m(s′, s) ≥ 2 for s ≠ s′ in S. In case no relation occurs for a pair (s, s′), we make the convention that m(s, s′) = ∞. We will always assume that S is finite.

Note that to specify a Coxeter system (W, S), it is enough to draw the corresponding Coxeter diagram Γ: this is a graph on vertices indexed by elements of S, with vertices s and s′ joined by an edge labelled m(s, s′) whenever this number (∞ allowed) is at least 3.

Remark 5.1. In what follows, the reader should note that the positive Bergman complex and the graph associahedron associated with Γ will turn out not to depend on the edge labels m(s, s′) of Γ, and only depend upon the undirected graph underlying Γ. However, the Bergman complex will turn out to depend upon the edge labels m(s, s′).

Although an arbitrary Coxeter system (W, S) need not have a faithful representation of W as a group generated by orthogonal reflections (for a positive definite inner product), there exists a reasonable substitute, called its geometric representation [6, Sec. V.4], [16, Sec. 5.3, 5.13], which we recall here. Let V := ℝ^{|S|} with a basis of simple roots Δ := {α_{s} : s ∈ S}. Define an ℝ-valued bilinear form (·, ·) on V by

(α_{s}, α_{s′}) := − cos (\frac{π}{m(s, s′)}) ,

and let s act on V by the “reflection” that fixes α_{s}^{⊥} and negates α_{s}:

s(v) := v − 2(v, α_{s})α_{s}.

This turns out to extend to a faithful representation of W on V, and one defines the root system Φ and positive roots Φ^{+} by

\begin{aligned}Φ & := \{w(α_{s}) : w ∈ W, s ∈ S\}, \\ Φ^{+} & := \{α ∈ Φ : α = ∑_{s∈S} c_{s}α_{s} with c_{s} ≥ 0\}. \end{aligned}

It turns out that Φ = Φ^{+} ⊔ Φ^{−} where Φ^{−} := −Φ^{+}, and that W will be infinite if and only if Φ is infinite.

Definition 5.2. Given a root β ∈ Φ, expressed uniquely in terms of the simple roots Δ as β = ∑_{s∈S} c_{s}α_{s}, define the support of β (written supp β) to be the vertex-induced subgraph of the Coxeter diagram Γ on the set of vertices s ∈ S for which c_{s} ≠ 0.

We will need the following lemma about supports of roots. It is well-known when W is finite and crystallographic [6, No. VI.1.6, Cor. 3], and a proof of its first assertion for the Coxeter systems associated to Kac–Moody Lie algebras can be found in [17, Lemma 1.6]; we will need the assertion in general.

Lemma 5.3. Let (W, S) be an arbitrary Coxeter system with Coxeter graph Γ. Then for any root β ∈ Φ the graph supp β is connected, and conversely, every connected subgraph Γ′ of Γ occurs as supp β for some positive root β.

Proof. For the first assertion, let β be a root, which we may assume is positive without loss of generality. It is known [3, Sec. 4.6] that there exists a chain of (distinct) positive roots

α = β_{1} ⋖ β_{2} ⋖ ⋯ ⋖ β_{k} = β

in which α is a simple root, and where each relation ⋖ is a covering relation in what Björner and Brenti call the root poset. This is the poset on positive roots defined as follows: β ≤ γ if there exists s_{1}, s_{2}, …, s_{k} ∈ S such that

(1) γ = s_{k}s_{k−1} … s_{1}β, and

(2) dp(s_{i}s_{i−1} … s_{1}β) = dp(β) + i, for all 1 ≤ i ≤ k. Here, the depth dp of a positive root is defined to be

dp(β) = min{k : w(β) ∈ Φ^{−} for some w ∈ W with ℓ(w) = k}.

In particular, when two positive roots

\begin{aligned}γ & = ∑_{t∈S} c_{t}α_{t} \\ γ′ & = ∑_{t∈S} c′_{t}α_{t} \end{aligned}

satisfy γ ⋖ γ′, then

(5)  γ′ = s(γ) = γ − 2(γ, α_{s})α_{s}

for some s ∈ S, and the nonnegative coefficients c_{t}, c′_{t} satisfy c_{t} ≤ c′_{t} for all t ∈ S, so that supp γ ⊆ supp γ′; see [3, Corollary 4.6.5]. By induction on k, it suffices to show that if supp(γ) is connected and γ ⋖ γ′, then supp(γ′) is connected. From expression (5) we conclude that supp γ ⊆ supp γ′ ⊆ supp γ ∪ {s}. Hence either

• supp γ′ = supp γ, which is connected, so we are done, or

• s ∉ supp γ and supp γ′ = supp γ ⊔ {s}. If supp γ ⊔ {s} is connected, we are done. If not, then (γ, α_{s}) = 0, so the expression (5) forces the contradiction γ′ = γ.

For the second assertion, let Γ′ be a connected subgraph of Γ, and we will exhibit a positive root γ′ with supp γ′ = Γ′ using induction on the number of vertices of Γ′. Let s ∈ S be a vertex lying in Γ′ whose removal leaves a connected subgraph Γ′′ = Γ − {s}. By induction there exists a positive root γ having supp γ = Γ′′, and we claim that γ′ := s(γ) has supp(γ′) = Γ′. To see this, note that γ = ∑_{t∈Γ′′} c_{t}α_{t} with each c_{t} > 0. Hence

(α_{s}, γ) = ∑_{t∈Γ′′} c_{t}(α_{s}, α_{t}) < 0,

since each (α_{s}, α_{t}) is nonpositive, and at least one is negative due to Γ′′ ∪ {s} = Γ′ being connected. Therefore the expression (5) for γ′ shows that supp(γ′) = Γ′. □

We use M_{Φ} to denote the matroid represented by the vector configuration of positive roots Φ^{+} in V. Thus M_{Φ} is a matroid of finite rank r = |S|, but has ground set E = Φ^{+} of possibly (countably) infinite cardinality.

Remark 5.4. When the ground set E is infinite, we need to be careful about how we define the objects that we are studying: it is no longer clear what is meant by a weight vector ω or the bases of minimum ω-weight. Therefore we will not refer to M_{ω} in this case; only to the matroid M_{F} associated to a flag of flats F. We will not think of the positive Bergman complex as a subset of weight vectors (as in Definition/Theorem 2.8), but as a coarsening of the order complex of the lattice of positive flats (which we can do by Corollary 2.9). Although we can similarly consider the Bergman complex as a coarsening of the order complex of the lattice of flats, for technical reasons we will not deal with the Bergman complex of a matroid with an infinite ground set in this paper.

For an arbitrary Coxeter system (W, S), when one wants to think of the oriented matroid M_{Φ} as the oriented matroid of a hyperplane arrangement A_{Φ} (as opposed to the oriented matroid of the configuration of vectors Φ^{+}), one must work with the contragredient representation V^{∗}. Then M_{Φ} is simply the matroid of the reflecting hyperplanes in V^{∗} for the positive roots Φ^{+}.

We now review the Tits cone. See [6, Sec. V.4], [16, Sections 1.15, 5.13], [7, Chapter I], and particularly [25] for a very detailed discussion. Let {δ_{s} : s ∈ S} denote the basis for V^{∗} dual to the basis of simple roots Δ for V. Then the (closed) fundamental chamber R is the nonnegative cone spanned by {δ_{s} : s ∈ S} inside V^{∗}. The Tits cone is the union T := ⋃_{w∈W} w(R), a (possibly proper, not necessarily closed nor polyhedral) convex cone inside V^{∗}. Every positive root α ∈ Φ^{+} has associated a hyperplane and two half-spaces, H_{α}, H_{α}^{+}, H_{α}^{−} in V^{∗}, consisting of those functionals f ∈ V^{∗} for which f(α) is zero, positive, or negative, respectively. These hyperplanes and half-spaces decompose the Tits cone^{2} into cells σ that turn out to be simplicial cones σ, each of them relatively open within the linear subspace that they span. The top-dimensional (open) cones are exactly the images w(int(R)) as w runs through W, where int(R) denotes the interior of the fundamental chamber R. The tope (maximal covector) in the oriented matroid M_{Φ} associated to w(int(R)) will have the sign + on the roots Φ^{+} ∩ w^{−1}(Φ^{+}) and the sign − on the roots Φ^{+} ∩ w^{−1}(Φ^{−}). More generally one has the following proposition (see [25, Section 3.2]) relating an arbitrary cone σ to a coset wW_{J} of a standard parabolic subgroup W_{J} (= the subgroup of W generated by J) for some subset J ⊆ S

Proposition 5.5. The cones σ in the decomposition of T are naturally in bijection with the cosets wW_{J} of standard parabolic subgroups, with wW_{J} determined by the following equality:

wW_{J} = {u ∈ W : u^{−1}(σ) ⊆ R}.

The cone σ will then have the following description as an intersection: for any u in the coset wW_{J}, one has

σ = ⋂_{s∈J} u(H_{α_{s}}) ∩ ⋂_{s∈S\J} u(H_{α_{s}}^{+}).

As a consequence of this proposition (see [25, Prop. 3.4]), the linear span of the cone σ in V^{∗} is the hyperplane intersection ⋂_{s∈J} H_{w(α_{s})}, which is the subspace (V^{∗})^{wW_{J} w^{−1}} fixed by the parabolic subgroup wW_{J}w^{−1}.

2When W is infinite, note that only part of the hyperplane or its half-spaces lies inside the Tits cone T.

As pointed out in Remark 5.4, when W (equivalently Φ, or E = Φ^{+}) is infinite, we want to consider the positive Bergman complex to be a coarsening of the order complex of the lattice of positive flats. However, in this situation we have a choice to make, because there are three different kinds of flats F of the (oriented) matroid M_{Φ}, not all of which are relevant to the De Concini–Procesi wonderful compactifications. These three kinds of flats are distinguished by how the associated intersection subspace

X_{F} := ⋂_{α∈F} H_{α}

intersects the Tits cone T:

(1) An arbitrary flat F will have at least the zero subspace {0} in the intersection X_{F} ∩ T.

(2) A parabolic flat F is one for which X_{F} ∩ T is of maximum possible dimension, that is, dim(X_{F}). In this case, it must contain a cone σ of this same dimension, say indexed by the coset wW_{J}, whose linear span has pointwise stabilizer wW_{J}w^{−1}. Hence F = wΦ_{J}^{+} is a W -conjugate^{3} of a standard parabolic flat Φ_{J}^{+}, where Φ_{J}^{+} is the subset of positive roots lying in the span of the simple roots {α_{s}}_{s∈J}.

(3) A finite parabolic flat F is one for which X_{F} ∩ int(T) has maximum possible dimension dim(X_{F}). This turns out [25, Cor. 3.8] to be equivalent to F being the parabolic flat wΦ_{J}^{+} where the parabolic subgroup W_{J} is finite. In other words, int(T) is the union of the cones σ in T whose associated parabolic subgroup is finite.

It turns out that W (or equivalently, Φ) is finite if and only if the Tits cone T coincides with the whole space V^{∗} (and hence also coincides with the interior int(T)). In this case, there is no distinction between the three kinds of flats: all flats are finite parabolic. The reader interested solely in the case of finite Coxeter groups W can therefore safely ignore the remainder of this section. Example 5.6. The distinctions between the three kinds of flats are well-illustrated by the case where (W, S) is an irreducible affine Coxeter system, that is, when the bilinear form (·, ·) is positive semidefinite, but degenerate. In this case, the kernel of the bilinear form is a 1-dimensional subspace ℓ, and one can faithfully realize the group W as one generated by Euclidean affine reflections in an affine hyperplane of V^{∗}: simply intersect the Tits cone with a (strictly) affine hyperplane normal to ℓ. See [6, Ch. V, Sec. 4.9].

As an example of a non-parabolic flat in this situation, pick any two roots α, β in Φ^{+} whose corresponding affine reflections s_{α}, s_{β} have parallel reflecting hyperplanes. Then s_{α}, s_{β} generate an infinite subgroup W′ ⊊ W, whose fixed subspace in V^{∗} corresponds to a flat F = cl({α, β}) that is not parabolic. To see this, note that in the affine case, all proper parabolic subgroups W_{J} with J ⊊ S are finite, and hence all proper parabolic subgroups wW_{J}w^{−1} are also finite. But W′ is infinite.

3Strictly speaking, in order to insure that wΦ_{J}^{+} ⊆ Φ^{+}, we should insist here that the coset representative w for wW_{J} is chosen to be of minimum length.

There is also a unique parabolic flat which is not finite parabolic in this situation, namely the improper flat F = Φ^{+}. Its corresponding intersection subspace X_{F} = {0} lies in the Tits cone T, but not in its interior int(T).

Remark 5.7. The geometry of the Tits cone when W is infinite, and in particular, its interior int(T), turn out to be important in the geometric group theory surrounding the generalized (Artin) braid group B(W, S) associated to (W, S). Inside the complex vector space V^{∗}⊗ℂ, one has the open subset V^{∗}+i·int(T), from which one can remove the intersection with the complexified hyperplanes ⋃_{α∈Φ^{+}} H_{α}. This hyperplane complement carries a free action of W with interesting topology: it is conjectured (and proven in many cases) that it is an Eilenberg–MacLane K(P B(W, S), 1)-space for the (pure) braid group P B(W, S), and hence that its quotient by W is a K(B(W, S), 1) for the braid group B(W, S); see Charney and Davis [9].

In principle one might therefore consider (at least) three different versions of the poset of flats of the oriented matroid M_{Φ}: the posets of arbitrary, parabolic, or finite parabolic flats

L^{arb}(M_{Φ}) ⊃ L^{par}(M_{Φ}) ⊃ L^{finpar}(M_{Φ}).

By the previous discussion, these posets of flats are isomorphic to the following posets of subgroups.

Proposition 5.8. The map

W′ ↦ {α ∈ Φ^{+} : s_{α} ∈ W′}

induces isomorphisms between the following posets of subgroups and posets of flats, all ordered by inclusion:

{ reflection subgroups } ≅ L^{arb}(M_{Φ})
{ parabolic subgroups } ≅ L^{par}(M_{Φ})
{ finite parabolic subgroups } ≅ L^{finpar}(M_{Φ}).

When W is finite, of course, all three notions of flats coincide and all reflection subgroups are finite parabolic. When W is infinite we must make a choice of which flats to consider.

Remark 5.9. When discussing the De Concini–Procesi wonderful compactifications of Coxeter arrangements, Carr and Devadoss [8] chose to consider only Coxeter systems (W, S) which they call simplicial, namely those in which every proper parabolic subgroup W_{J} with J ⊊ S is finite, or equivalently, the simplicial decomposition of the Tits cone T intersected with the unit sphere in V^{∗} is a locally finite simplicial complex. Such Coxeter systems include those which are finite, affine and compact hyperbolic. When doing the wonderful compactification, they made the natural choice of compactifying the complement of the arrangement within the interior int(T) of the Tits cone, after intersecting with the sphere. This means that they only blew up along the finite parabolic flats, those in L^{finpar}(M_{Φ}), and avoided the problem of how to define blow-ups along non-parabolic flats, where the normal structure is not that of a finite hyperplane arrangement.

We make a slightly different choice. If one is not so concerned with the blow-ups themselves, but rather with the truncations of the fundamental simplex R which would tile the hypothetical blow-up, then these truncated polytopes (the graph associahedra) are well-defined whether or not the arrangement is locally finite. In particular, we would like to consider graph-associahedra associated to graphs Γ for which (W, S) is not simplicial, such as the complete graphs Γ = K_{n} for n ≥ 4. For this reason we do not restrict ourselves to the finite parabolic flats; instead we consider all parabolic flats.

On the other hand, the relevant flats of the matroid which are relevant for these truncations and blow-ups in the wonderful compactification are those which intersect the Tits cone T in full dimension. For this reason, when discussing the positive Bergman complex B^{+}(M) in the next section, we will consider only the poset of parabolic flats L^{par}(M_{Φ}).

Remark 5.10. It is not clear that we should expect good behavior from the Bergman complex B(M_{Φ}) or positive Bergman complex B^{+}(M_{Φ}) defined with respect to the lattice L^{arb}(M_{Φ}) of arbitrary flats, when M_{Φ} is infinite.

6. The positive Bergman complex of a Coxeter arrangement

In this section we prove that the positive Bergman complex of a Coxeter arrangement of type Φ is dual to the graph associahedron of type Φ. More precisely, both of these objects are homeomorphic to spheres of the same dimension, and their face posets are dual.

Caution. Throughout this section, whenever the Coxeter system (W, S) with root system Φ has W (or equivalently, Φ) infinite, the word flat used in the connection with the oriented matroid M_{Φ} will mean a parabolic flat, as discussed in the end of Section 5.

Proposition 6.1. Let (W, S) be an arbitrary Coxeter system, with root system Φ and Coxeter diagram Γ.

(i) Positive flats in the oriented matroid M_{Φ} correspond to subsets J ⊂ S, that is, they are the standard parabolic flats Φ_{J}^{+}.

(ii) Connected positive flats in the oriented matroid M_{Φ} correspond to subsets J ⊂ S such that the vertex-induced subgraph Γ_{J} is connected, that is, to tubes in Γ.

(iii) The simple roots Δ form a circuitous base for the matroid M_{Φ}.

(iv) If F ⊂ G are flats in M_{Φ} with G connected, then the matroid quotient G/F is connected.

Proof. (i): The hyperplanes bounding the base region/tope R are {H_{α_{s}} : s ∈ S}, so positive flats are those spanned by sets of the form {α_{s} : s ∈ J} for subsets J ⊂ S. As in the previous section, we denote such a positive flat by Φ_{J}^{+}. (ii): Let J ⊂ S with subgraph Γ_{J}, and consider its associated positive flat Φ_{J}^{+}. The first assertion of Lemma 5.3 shows that Φ_{J}^{+} will not be connected if Γ_{J} is disconnected.

To see this, represent the flat Φ_{J}^{+} by a matrix in which the rows correspond to simple roots of Φ_{J}^{+}, i.e. vertices of Γ_{J}, and the columns express each positive root in Φ_{J}^{+} as a combination of simple roots. By permuting columns, one can obtain a matrix which is a block-direct sum of two smaller matrices, and hence Φ_{J}^{+} will not be connected.

On the other hand, if Γ_{J} is connected, then the second assertion of Lemma 5.3 shows that there is a positive root α with supp α = Γ_{J}, and consequently {α_{s} : s ∈ J} ∪ {α} gives a circuit in M_{Φ} spanning this flat, so it is connected. (iii): This follows from the argument in (ii); given J ⊂ S with Γ_{J} connected, the basic circuit circ(Δ, α) where supp α = Γ_{J} spans the connected flat corresponding to J. (iv): Let the flats F, G correspond (since they are assumed to be parabolic flats) to the parabolic subgroups uW_{J}u^{−1}, vW_{K}v^{−1}. Equivalently, assume they are equal to uΦ_{J}^{+}, vΦ_{K}^{+}. One can make the following reductions:

• Translating by v^{−1}, one can assume that v is the identity.

• Since (W_{K}, K) itself forms a Coxeter system with root system Φ_{K}, one can assume M_{Φ} = G and K = S. In particular, M_{Φ} is connected.

• Replacing the Coxeter system (W, S) by the system (W, uSu^{−1}), one can as-

sume that u is the identity. In other words, F is the positive flat corresponding to some subgraph Γ_{J} of Γ, and we must show M_{Φ}/F is a connected matroid. This is a consequence of (iii) and Lemma 3.8. □

We now give our main result.

Theorem 1.1. Let (W, S) be an arbitrary Coxeter system, with root system Φ, Coxeter diagram Γ, and associated oriented matroid M_{Φ}. Then the face poset of the coarse subdivision of B^{+}(M_{Φ}) is dual to the face poset of the graph associahedron P (Γ).

Proof. By Theorem 4.3, we need to show that the face poset of (the coarse subdivision of) B^{+}(M_{Φ}) is equal to the poset of tubings of Γ, ordered by containment. We begin by describing a map Ψ from flags of positive flats to tubings of Γ.

By Proposition 6.1, positive flats of M_{Φ} correspond to subsets J ⊂ S or subgraphs Γ_{J} of the Coxeter graph Γ. Furthermore, a positive flat is connected if and only if Γ_{J} is a tube, and hence an arbitrary positive flat corresponds to a disjoint union of compatible tubes, no two of which are nested. Since an inclusion of flats corresponds to an inclusion of the subsets J, a flag F of positive flats corresponds to a nested chain of such unions of non-nested compatible tubes, that is, to a tubing Ψ(F). Furthermore, in this correspondence, inclusion of flags corresponds to containment of tubings.

We claim that the map from flags to tubings is surjective. Given some tubing of Γ, linearly order its tubes J_{1}, …, J_{k} by any linear extension of the inclusion partial ordering, and then the flag F of positive flats having F_{i} spanned by {α_{s} : s ∈ J_{1} ∪ J_{2} ∪ ⋯ ∪ J_{i}} will map to this tubing.

Lastly, we show that Ψ is actually a well-defined injective map when regarded as a map on cells of the coarse subdivision of B^{+}(M_{Φ}). To do so, it is enough to show that two flags F, F′ of positive flats give the same tubing if and only if M_{F} and M_{F′} coincide. By Lemma 6.1(iv) and Proposition 3.9, we need to show that Ψ(F) and Ψ(F′) coincide if and only if T_{F} and T_{F′} coincide. But this is clear, because by construction, the rooted forest T_{F} ignores the ordering within the flag, and only records the data of the tubes which appear, that is, the tubing. □

Corollary 6.2. The positive Bergman complex of a Coxeter arrangement is simplicial, and is in fact, a flag simplicial sphere.

Another corollary of our proof is a new realization for the positive Bergman complex of a Coxeter arrangement: we can obtain it from a simplex by a sequence of stellar subdivisions (since stellar subdivisions are dual to the truncations defining the graphassociahedra; see [27, Exercise 3.0]).

7. The Bergman complex of a Coxeter arrangement

In this section we will give a concrete description of the Bergman complex of a Coxeter arrangement, in terms of the nested set complex. We will also address a question of Eugene Tevelev [24] concerning the relationship of the positive Bergman complex to the Bergman complex in this setup.

Nested set complexes are simplicial complexes at the combinatorial heart of De Concini and Procesi’s subspace arrangement models [11], and of the resolution of singularities in toric varieties [12]. We now recall the definition of the minimal nested set complex of a meet-semilattice L, which we will simply refer to as the nested set complex of L, and denote N (L). For the sake of avoiding the technicalities of infinite semilattices, matroids, and Coxeter groups, we will assume that everything is finite in this section.

Say an element y of L is irreducible if the lower interval [ˆ0, y] cannot be decomposed as the product of smaller intervals of the form [ˆ0, x]. The nested set complex N (L) of L is a simplicial complex whose vertices are the irreducible elements of L. A set X of irreducibles is nested if for any nonempty antichain {x_{1}, …, x_{k}} in X, x_{1} ∨ ⋯ ∨ x_{k} is not irreducible. These nested sets are the simplices of N (L).

If M is a matroid and L_{M} is its lattice of flats, we will also call N (L_{M}) the nested set complex of M, and denote it N (M). It is easy to see that the irreducible elements of L_{M} are the connected flats of M.

Theorem 1.2. For any finite Coxeter system (W, S) and associated finite root system Φ, the coarse subdivision of the Bergman complex B(M_{Φ}) of the Coxeter arrangement of type Φ is equal to the nested set complex N (M_{Φ}). In particular, the Bergman complex B(M_{Φ}) is a simplicial complex.

We offer two proofs of this result. The first is short, but not very self-contained in that it invokes a result of Feichtner and Sturmfels. They showed that, for any matroid M, the simplicial complex N (M) has a geometric realization which is intermediate in coarseness between the fine and coarse subdivisions of the Bergman complex B(M). Furthermore, they gave the following criterion for when N (M) and the coarse subdivision of B(M) coincide.

Theorem 7.1. [14, Theorem 5.3] The nested set complex N (M) and the Bergman complex B(M) together with its coarse subdivision coincide if and only if the matroid G/F is connected for every pair of flats F ⊂ G in which G is connected.

Theorem 1.2 then follows immediately from this result together with our Proposition 6.1(iv).

On the other hand, one might suspect that in the case of a Coxeter arrangement, Theorem 1.1 describing the positive Bergman complex B^{+}(M), and Theorem 1.2 about the entire Bergman complex B(M), should be related by Theorem 3.3 showing that B(M) is covered by several copies of B^{+}(M). The goal of the remainder of this section is to develop this connection, in the context of arbitrary oriented matroids, partly in order to answer the question of Tevelev mentioned earlier, and partly for its own interest.

We begin in the setting of an (unoriented) matroid M, giving the relationship between nested sets and the labelled forest T_{F} associated to a flag of flats of M in Proposition 3.5. This next proposition can be gleaned implicitly from the material in [14, Sections 3 and 4], but we state it explicitly here, and include our own proof, for the sake of self-containment.

Proposition 7.2. Let M be an (unoriented) matroid. Given a flag F of flats in M, consider the set of connected flats {G_{i}} which label the vertices of the forest T_{F}. Then the collection of all such sets {G_{i}} of flats, as F ranges over all flags of flats in M, are precisely the nested sets of M.

Proof. For any F, the labels of T_{F} are connected flats of M by definition. Now let us show that they form a nested set. We need to show that for any antichain {G_{1}, …, G_{k}} of flats among the vertex labels T_{F}, their L_{M}-join is not connected, so assume that it is. Let F_{i} be the smallest flat of F containing H = G_{1} ∨⋯∨G_{k}. Since H is connected, it is a subset of a connected component G of F_{i}. But G lies above G_{1}, …, G_{k} in the tree; this means that the G_{i}s are connected components of flats F_{j} with j < i, and are therefore contained in F_{i−1}. But then H, being their L_{M}-join, must also be contained in F_{i−1}, contradicting the minimality of i.

Now we show that every nested set N of M, when its elements are ordered by inclusion, can be obtained as the vertex labels of the forest T_{F} for some flag F of flats of M. The connected flats in N can be labelled G_{1}, G_{2}, …, G_{k} in such a way that i < j implies G_{i} ⊉ G_{j}. Let the flag F consist of the flats F_{i} = G_{1} ∨ ⋯ ∨ G_{i} for 1 ≤ i ≤ k.

First we show that F_{i} is just the union of the maximal G_{j}s with j ≤ i. Suppose there was an element e in F_{i} which is not in one of these G_{j}s. Then there must be a circuit containing e and elements of, say, G_{a}, …, G_{z}. Then e, G_{a}, …, G_{z} are contained in the same connected component of M. Any other f in G_{a} ∨ ⋯ ∨ G_{z} is in this same component, so G_{a} ∨ ⋯ ∨ G_{z} is connected. This contradicts the assumption that N is nested.

By the same reasoning, we cannot have a circuit in F_{i} consisting of elements of more than one of the G_{j}s. Therefore the maximal G_{j}s with j ≤ i are actually the connected components of F_{i}. In particular, G_{i} is one of them. This shows that the flag F gives rise to the nested set N, as we wished to prove. □

We next wish to understand, in the setting of an (acyclically) oriented matroid M, how nested sets interact with the notion of positive flats. First, we need a small technical lemma.

Lemma 7.3. If a flat of an oriented matroid M is positive, so are its connected components.

Proof. Let G be a connected component of a positive flat F and assume for the sake of contradiction that G is not positive. By [4, Proposition 9.1.2], we can find a signed circuit X of M such that X^{+} ⊆ G and X^{−} ⊈ G. We then have that X^{+} ⊆ F, which implies that X^{−} ⊆ F since F is positive. Therefore X is a circuit in F, containing elements of more than one of its connected components. This is a contradiction. □

Proposition 7.4. Let M be an acyclically oriented matroid whose positive tope is simplicial. As F ranges over all flags of positive flats in M, the sets of flats labelling vertices of the forests T_{F} are precisely those nested sets of M which consist of positive (connected) flats.

Proof. By Proposition 7.2, if F is a flag of positive flats, then T_{F} is a nested set of M. The labels of T_{F} are positive by Lemma 7.3.

Now start with a nested set N of M consisting of positive connected flats, labelled G_{1}, G_{2}, …, G_{k} in such a way that i < j implies G_{i} ⊉ G_{j}. As in the proof of Proposition 7.2, the flag F consisting of the flats F_{i} = G_{1} ∨ ⋯ ∨ G_{i} for 1 ≤ i ≤ k satisfies T_{F} = N. Finally, each F_{i} is a disjoint union of G_{j}s, which are positive. Since the positive tope is simplicial, the F_{i}s are also positive. □

Remark 7.5. Proposition 7.4 is closely related to Feichtner and Sturmfels’ notion [14, Section 4] of the localization of the nested set complex N (M) to a basis B of the matroid M, if one chooses B to be the elements of the ground set which bound the simplicial positive tope of M.

Observation 7.6. Proposition 7.4 can fail if the positive tope is not simplicial. For example, consider the oriented matroid M of affine dependencies of the vertices of a square which are cyclically labelled {1, 2, 3, 4}. Now, {1, 3} is a nested set of L_{M} consisting of positive flats. However, it does not arise as the forest of a flag of positive flats.

Observation 7.7. The nested sets of M which consist of positive (connected) flats are not the same as the nested sets of the lattice of positive flats F_{lv}(M). In the previous example, {1, 3} is nested in L_{M} but not in F_{lv}(M). Even in Example 2.10, the (simplicial) oriented matroid of the braid arrangement A_{3}, {1, 4} is not nested in L_{M} but it is nested in F_{lv}(M).

We now give the second proof of Theorem 1.2. In view of Proposition 7.2, Proposition 3.5 tells us that, for any matroid M, the nested set complex N (M) is a refinement of the coarse subdivision of the Bergman complex B(M) and a coarsening of the order complex Δ(\overline{L}_{M}) (i.e. the fine subdivision of B(M)). Therefore, it suffices to show that, in the case of a (finite) Coxeter arrangement, every cell in the nested set complex is equal to the cell of the Bergman complex which contains it.

So consider an arbitrary cell C_{N} corresponding to a nested set N in the nested set complex N (M_{Φ}), and the cell D of the Bergman complex B(M_{Φ}) containing it. By Theorem 2.8, we can find a tope T of M such that the positive Bergman complex B^{+}(M_{Φ}) corresponding to T contains the cell D, and therefore the cell C_{N}. Since M_{Φ} is simplicial, Proposition 7.4 implies that the flats in N are positive with respect to T.

Proposition 6.1 tells us that connected positive flats correspond to tubes in Γ. It is easy to see that a set of connected positive flats is nested if and only if the corresponding set of tubes is a tubing of Γ. Therefore C_{N} is precisely the cell of B^{+}(M_{Φ}) labelled by the tubing corresponding to N, by (the proof of) Theorem 1.1. It follows that C_{N} = D, as we wished to show. □

Recently Tevelev [24] asked whether every (coarse) cell in the Bergman complex B(M_{Φ}) of a Coxeter arrangement of type Φ is Coxeter-group equivalent to a cell in B^{+}(M_{Φ}), i.e. a cell obtained from a tubing of the corresponding Dynkin diagram. Using Theorem 3.3, we can give an affirmative answer to this question. We begin with the following observation about the group Aut(M) of all automorphisms ϕ : E → E for a finite matroid M on ground set E = [n].

Proposition 7.8. The group Aut(M), acting on ℝ^{n} by permuting coordinates, preserves the Bergman fan B(M), and acts by cellular automorphisms on its coarse subdivision.

Proof. Recall that a weight vector ω in ℝ^{n} has a uniquely associated flag F(ω) of subsets as in (1), and any permutation ϕ : E → E respects this association: F(ϕ(ω)) = ϕ(F(ω)). Since ω lies in B(M) if and only if this flag of subsets is a flag of flats, a matroid automorphism ϕ will preserve this property, and hence preserves B(M).

Recall also from (2) that the matroid M_{ω} induced by ω is exactly ⨁_{i=1}^{k+1} F_{i}/F_{i−1}. Since two weight vectors ω, ν lie in the same coarse cell if and only if M_{ω} = M_{ν}, the second assertion of the proposition follows. □

Proposition 7.9. Let M_{Φ} be the oriented matroid of a (finite) Coxeter arrangement of type Φ with Coxeter group W. Then any coarse cell in B(M_{Φ}) is W -equivalent to a coarse cell in B^{+}(M_{Φ}).

Proof. Since W acts by matroid automorphisms on the ground set E of M_{Φ}, Proposition 7.8 implies that W permutes the coarse cells of B(M).

Now let C be any coarse cell of B(M), and choose a fine cell c ⊂ C defined by a flag of flats F. By Theorem 3.3 and the fact that W acts transitively on the regions of the arrangement, there exists some w ∈ W such that w(c) is a fine cell defined by a flag of positive flats, i.e. w(c) lies inside a coarse cell D of B^{+}(M). But now it follows that w(C) = D: w(C) must be a cell of B(M), and it contains w(c), which lies in D. □

Acknowledgments We are very grateful to Satyan Devadoss for allowing us to reproduce two of his figures from [8]. These are our Figures 3 and 4. Additionally, we thank Bernd Sturmfels, Eva Feichtner, and Eugene Tevelev for useful discussions.

References

[1] F. Ardila and C. Klivans, The Bergman complex of a matroid and phylogenetic trees, to appear in the J. Combin. Theory, Ser. B; arXiv:math.CO/0311370.

[2] F. Ardila, C. Klivans, and L. Williams, The positive Bergman complex of an oriented matroid, to appear in the Europ. J. Combin.

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

[4] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993.

[5] A. Björner and M. Wachs, Geometrically constructed bases for homology of partition lattices of types A, B and D, Electronic J. Combin. 11(2) (2004).

[6] N. Bourbaki, Lie groups and Lie algebras Chapters 4–6, Elements of Mathematics (Berlin), Springer–Verlag, Berlin, 2002.

[7] K.S. Brown, Buildings, Springer Monographs in Mathematics, Springer–Verlag, New York, 1998.

[8] M. Carr, S. Devadoss, Coxeter complexes and graph associahedra, to appear in Topology and its Applications.

[9] R. Charney and M.W. Davis, Finite K(π, 1)s for Artin groups, Prospects in topology (Princeton, NJ, 1994), 110–124, Ann. of Math. Stud. 138, Princeton Univ. Press, Princeton, NJ, 1995.

[10] M. Davis, T. Januszkiewicz, and R. Scott, Fundamental groups of minimal blow-ups, AdvṀath. 177 (2003), 115–179.

[11] C. De Concini, C. Procesi, Wonderful models of subspace arrangements, Selecta Math. (N.S.) 1 (1995), 459–494.

[12] E. Feichtner, D. Kozlov, Incidence combinatorics of resolutions, Selecta Math. (N.S.) 10 (2004), 37–60.

[13] E. Feichtner, I. Müller, On the topology of nested set complexes, Proc. Amer. Math. Soc. 133 (2005), 999–1006.

[14] E. Feichtner, B. Sturmfels, Matroid polytopes, nested sets and Bergman fans, to appear in Port. Math..

[15] C. Greene, T. Zaslavsky, On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc. 280 (1983), 97–126.

[16] J. Humphreys, Reflection groups and Coxeter groups. Cambridge University Press, 1990.

[17] V. Kac, Infinite dimensional Lie algebras, Cambridge University Press, 1990.

[18] M. Las Vergnas, Acyclic and totally cyclic orientations of combinatorial geometries, Discrete Math. 20 (1977), 51–61.

[19] A. Postnikov, Permutahedra, associahedra, and beyond, preprint, 2005; arXiv:math.CO/0507163.

[20] D. Speyer and B. Sturmfels, The tropical Grassmannian, Adv. Geom. 4 (2004), 389–411.

[21] D. Speyer and L. Williams, The tropical totally positive Grassmannian, J. Algebraic Combin. 22 (2005), 189–210.

[22] R. P. Stanley, Enumerative combinatorics, vol. 1, Cambridge University Press, New York, 1986.

[23] B. Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, American Mathematical Society, Providence, RI, 2002.

[24] E. Tevelev, personal communication.

[25] J.H. Walter, Bases of chambers of linear Coxeter groups, Groups and combinatorics — in memory of Michio Suzuki, 423–436, Adv. Stud. Pure Math. 32, Math. Soc. Japan, Tokyo, 2001.

[26] T. Zaslavsky, The Möbius function and the characteristic polynomial, Chapter 7 in Theory of matroids (edited by N. White) Encyclopedia of Mathematics and its Applications, 26. Cambridge University Press, Cambridge, 1986.

[27] G. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer–Verlag, New York, 1995.

Department of Mathematics, San Francisco State University, San Francisco, CA 94132, USA

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

Department of Mathematics, Harvard University, 1 Oxford Street, Cambridge, MA 02138, USA