Gallery posets of supersolvable arrangements.

1 Introduction

This article is about the topology of some posets associated to real hyperplane arrangements. Throughout, the topology attached to a poset P is that of its order complex [DELTA](P), the simplicial complex of chains [x.sub.1] < [x.sub.2] < ... < [x.sub.k] of P. If P is a bounded poset, its proper part [bar.P] is the same poset with those bounds removed.

A reduced gallery of a real central arrangement A is a sequence of chambers [c.sub.0], [c.sub.1], ..., [c.sub.m] such that adjacent chambers are separated by exactly one hyperplane, and [c.sub.0] and [c.sub.m] are separated by m hyperplanes. For any codimension 2 subspace X [member of] L(A), a gallery between opposite chambers [c.sub.0], -[c.sub.0] can cross the hyperplanes containing X in two ways. We introduce a poset R(A, [r.sub.0]) of reduced galleries r ordered by single-step inclusion of sets of codimension 2 subspaces separating r from [r.sub.0]. The Hasse diagram of this poset is the usual graph of reduced galleries. An example is shown in Figure 1

When A is supersolvable and [r.sub.0] is incident to a modular flag, the poset was essentially shown to be bounded by Reiner and Roichman ; see Section 4 for details. In this situation, we prove [bar.R](A, [r.sub.0]) is homotopy equivalent to a (rk A - 3)-sphere.

For a face F and a chamber c of A, there is a unique chamber F x c incident to F that is closest to c. A cellular string is a sequence of faces ([X.sub.1], [X.sub.2], ..., [X.sub.m]) in L(A) such that [X.sub.1] x [c.sub.0] = [c.sub.0], [X.sub.m] x (-[c.sub.0]) = -[c.sub.0] and

[X.sub.i] x (-[c.sub.0]) = [X.sub.i+1] x [c.sub.0] ([for all]i).

The poset [omega](A, [c.sub.0]) of cellular strings is ordered by refinement. Our main result is the following.

Theorem 1.1 Let A be a real supersolvable hyperplane arrangement with chamber [c.sub.0] and gallery [r.sub.0] both incident to a modular flag. Let x = ([X.sub.1], [X.sub.2], ..., [X.sub.m]) [member of] [omega](A, [c.sub.0]) be a cellular string of A. The set of galleries incident to x forms a closed interval of R(A, [r.sub.0]) whose proper part is homotopy equivalent to [sub.S][[summation].sup.m.sub.i=1]codim([X.sub.i])-m-2.

We conjecture that all other intervals are contractible.

The motivation for this work primarily comes from two sources: the parameterization of noncontractible intervals in the chamber poset of an arrangement A proved by Edelman and Walker , and a conjecture by Reiner on the noncontractible intervals of the Higher Bruhat orders . We hope to derive new instances of the generalized Baues problem posed by Billera, Kapranov, and Sturmfels via these posets . We summarize the relevant results below.

Two posets naturally arise from a rank d real central hyperplane arrangement A: the poset of faces [Laplace](A) ordered by reverse inclusion and the poset of chambers P(A, [c.sub.0]) ordered by separation from some base chamber [c.sub.0]. These posets are reviewed in Section 3. Restricting A to the unit sphere gives a cellular decomposition of [S.sup.d-1]. This implies [bar.[Laplace]](A) is homeomorphic to a (d - 1)-sphere. In , Edelman and Walker use a recursive coatom ordering on an auxiliary poset to prove [bar.P](A, [c.sub.0]) is homotopy equivalent to [S.sup.d-2]. Moreover, they show the noncontractible open intervals of P are parameterized by the elements of L.

Theorem 1.2 (Edelman, Walker ) Let A be a real hyperplane arrangement with base chamber [c.sub.0]. The set of chambers incident to a face F [member of] [Laplace](A) forms a closed interval [c, d] in P(A, [c.sub.0]) such that (c, d) is homotopy equivalent to [S.sup.codimF-2]. Every other open interval of P(A, [c.sub.0]) is contractible

This theorem establishes an isomorphism between [Laplace] and the poset [Int.sub.nonc](P) of noncontractible intervals of P, ordered by inclusion. For an arbitrary bounded poset P, the full interval poset [bar.Int](P) has a deformation retract to its subposet of proper noncontractible intervals. Furthermore, [bar.Int](P) is homeomorphic to the suspension of P. Thus, EW's theorem may be viewed as an explanation of the homotopy equivalence

[bar.L](A) [equivalent] susp([bar.P](A, [c.sub.0])).

In , Bjorner applied Theorem 1.2 to compute the homotopy type of a poset [omega](A, [c.sub.0]) of cellular strings of A.

Theorem 1.3 (Bjorner ) The poset of cellular strings [omega](A, [c.sub.0]) of a rank d arrangement A with base chamber c0 is homotopy equivalent to [S.sup.d-2].

Bjorner's proof uses the identification of [omega](A, [c.sub.0]) with the poset [DELTA]H(P(A, [c.sub.0])) of chains [??] = [x.sub.0] < [x.sub.1] < ... < [x.sub.m] = [??] of P for which each interval ([x.sub.i], [x.sub.i+i]) is noncontractible. Once again a general argument shows that [[DELTA].sup.H](P) is homotopy equivalent to [DELTA](P).

Theorem 1.3 as stated above is a special case of the theorem of Billera, Kapranov, and Sturmfels on the homotopy type of a poset of cellular strings in a polytope . However, Bjorner's argument has a wide-reaching generalization to the cellular string posets of duals of shellable CW-spheres .

The paper is structured as follows. The above theorems are interpreted for Coxeter groups in Section 2. Some notation for hyperplane arrangements is given in Section 3. In Section 4 we define the poset of galleries for supersolvable arrangements. In Section 5, we recall the Suspension Lemma and use it to compute the homotopy type of the proper part of R. Theorem 1.1 is proved in Section 6. In Section 7, we draw a parallel between the poset of galleries for supersolvable arrangements and the Higher Bruhat orders. This connection will be developed further in future work.

2 Coxeter Groups

A finite Coxeter system (W, S) is a finite group W with a presentation of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [m.sub.st] = 1 if s = t and [m.sub.st] = [m.sub.ts] [member of] [Z.sub.[greater than or equal to]2] otherwise. For example, if S = {[s.sub.1], ..., [s.sub.n-1]} with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when [absolute value of i - j] = 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when [absolute value of i - j] > 1, then W is isomorphic to the symmetric group [G.sub.n].

A parabolic subsystem ([W.sub.J], J) is a subgroup [W.sub.J] generated by a subset J [subset or equal to] S. The collection of left cosets of parabolic subgroups

[Laplace](W) = {[wW.sub.J] | [member of] e W, J [subset or equal to] S}

may be viewed as a poset ordered by inclusion.

Let T = {[wsw.sup.-1] | s [member of] S, w [member of] W} denote the set of reflections of W. Define the length l(w) of w [member of] W to be the smallest value for which w equals [s.sub.1] ... [s.sub.l](-w) for some [s.sub.i] [member of] S. The (right) inversion set Inv(w) of w [member of] W is {t [member of] T | l(wt) < l(w)}. The weak Bruhat order P(W) is the set W ordered by inclusion of inversion sets; see Figure 2.

An interesting relationship between the posets P and [Laplace] was discovered by Bjorner.

Theorem 2.1 (Bjorner ) Let (W, S) be a finite Coxeter system. The coset [wW.sub.J] [member of] [Laplace](W) forms a closed interval [x, y] of P(W) such that (x, y) is homotopy equivalent to [S.sup.[absolute value of J]-2]. Every other open interval of P(W) is contractible.

Any finite Coxeter group has an associated reflection arrangement A and canonical isomorphisms [Laplace](A) [congruent] [Laplace](W) and P(A, [c.sub.0]) = P(W) for any choice of base chamber [c.sub.0]. Thus, Theorem 2.1 is a direct consequence of Theorem 1.2.

In this article, we describe a lifting of Theorem 2.1 to the intervals of a poset of galleries in a supersolvable hyperplane arrangement. We begin by describing the Coxeter case.

For a finite Coxeter system (W, S) there is a unique element [w.sub.0] [member of] W with Inv([w.sub.0]) = T. Let R(W) denote the set of reduced words [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for [w.sub.0]. The set R(W) forms a graph where two reduced words are adjacent if they differ in a single braid move:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The connectivity of R( W) for arbitrary finite Coxeter groups was originally shown by Tits. Athanasiadis, Edelman, and Reiner showed this graph is ([absolute value of S] - 1)-connected in .

In , Reiner and Roichman give a lower bound for the diameter of R(W) by defining a set-valued metric on the graph of reduced words. When W is a Coxeter group of type A or B they show this lower bound is achieved by constructing a bounded graded poset whose Hasse diagram is an orientation of R(W). This construction is recalled in Section 4; see Example 4.1. For the remainder of this article R(W) will denote this poset.

For J [subset or equal to] S, let [w.sub.0](J) denote the longest element of the subsystem ([W.sub.J], J). The poset of cellular strings [omega](W) is the set of words ([J.sub.1], [J.sub.2], ..., [J.sub.m]) where 0 [not equal to] [J.sub.i] [subset or equal to] S for all i and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The cellular strings are ordered by refinement, i.e. ([I.sub.1], ..., [I.sub.l]) [less than or equal to] ([J.sub.1], ..., [J.sub.m]) if there is are indices 0 = [[alpha].sub.1] < ... < [[alpha].sub.t] < l such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 2.2 Let (W, S) be a Coxeter system of type A or B. The set of reduced words for [w.sub.0] refining a cellular string ([J.sub.1], ..., [J.sub.m]) forms an interval [x, y] in R(W) such that (x, y) is homotopy equivalent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We conjecture that these are the only noncontractible intervals of R(W).

The weak order on W may be defined by setting u [less than or equal to] [upsilon] if there exists a geodesic from e to [upsilon] passing through u in the Cayley graph of W with respect to the generating set S. If the base point in the geodesic order is changed from e to some other element of W, an isomorphic poset is obtained since W acts simply transitively on its Cayley graph.

Similarly, R(W) may be defined by fixing a reduced expression [r.sub.0] and ordering by geodesics in the graph of reduced words for [w.sub.0]. However, different choices of [r.sub.0] yield nonisomorphic posets, many of which fail to be bounded or fail to satisfy Theorem 2.2, even in types A and B; see Figure 3. For type A, the base word is

[r.sub.0] = [s.sub.1]([s.sub.2][s.sub.1])([s.sub.3][s.sub.2][s.sub.1]),

while in type B, the base is

[r.sub.0] = [s.sub.0]([s.sub.1][s.sub.0][s.sub.1])([s.sub.2][s.sub.1][s.sub.0][s.sub.1][s.sub.2]) ...

At this time it is unclear whether a good choice of r0 exists for every finite Coxeter group.

3 Hyperplane Arrangements

Let A be an oriented real central hyperplane arrangement in [R.sup.d]. Its lattice of flats L(A) consists of the subspaces [H.sub.1] [intersection] ... [intersection] [H.sub.k] for [{[H.sub.j]}.sup.j.sub.k=1] [subset or equal to] A ordered by reverse inclusion. The rank i elements [L.sub.i](A) are the subspaces of codimension i.

Each hyperplane H in A divides [R.sup.d] into three connected sets [H.sup.+], [H.sup.-], [H.sup.0], where [H.sup.+] is the positive halfspace defined by H, [H.sup.-] = -[H.sup.+], and [H.sup.0] = H. The face poset [Laplace](A) is the set of nonempty cells of the form [[intersection].sub.H[member of]A][H.sup.[epsilon](H)] where [epsilon] is a sign vector in [{0, +, - }.sup.A], ordered by reverse inclusion of their closures. If F is a face defined by [[epsilon].sub.F] [member of] [{0, +, -}.sup.A], set [F.sup.0] = {H [member of] A | [[epsilon].sub.F](H) = 0}. The map F [??] [F.sup.0] is an order-preserving map [Laplace](A) [right arrow] [Laplace](A). The set [Laplace](A) is closed under o where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The chambers of A are the d-dimensional faces in [Laplace](A). The Li-separation set [L.sub.1](c, d) of two chambers c, d is the set of hyperplanes separating c and d. If c is fixed then d is determined by [L.sub.1](c, d) by reversing the halfspaces of [L.sub.1](c, d) in the sign vector for c.

Fixing a base chamber [c.sub.0], the poset of chambers P (A, [c.sub.0]) is the set of chambers of A ordered by c [less than or equal to] d if [L.sub.1]([c.sub.0], c) [subset or equal to] [L.sub.1]([c.sub.0], d).

4 Gallery poset

A gallery is a sequence of chambers [c.sub.0], [c.sub.1], ..., [c.sub.m] such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Unless otherwise specified, we will assume the gallery connects an antipodal pair of chambers [c.sub.0], -[c.sub.0]. For a fixed base chamber [c.sub.0], a gallery is determined by the order in which the hyperplanes are crossed. The set of galleries admits a free involution r [??] -r when [absolute value of A] > 1, where -r is the gallery from [c.sub.0] to -[c.sub.0] which crosses the hyperplanes of A in the reverse order of r.

For a subspace X [member of] L(A), the localization [A.sub.X] of A at X is {H [member of] A | H [subset or equal to] X}. If c is a chamber of A, set cX to be the chamber of [A.sub.X] containing c. If r = [c.sub.0], [c.sub.1], ..., -[c.sub.0] is a gallery, then [r.sub.X] is the sequence ([c.sub.0])X, ([c.sub.1])X, ..., [(-[c.sub.0]).sub.X] with repetitions removed, which is a gallery of [A.sub.X].

The [L.sub.2]-separation set [L.sub.2](r, r') is {X [member of] [L.sub.2](A) | [r.sub.X] [not equal to] [r'.sub.X]}. Given a base gallery [r.sub.0], R(A, [r.sub.0]) is the poset of galleries between [c.sub.0] and -[c.sub.0] ordered by single-step inclusion of the sets [L.sub.2]([r.sub.0], *). That is, r [less than or equal to] r' if there exists a sequence r = [r.sub.1], [r.sub.2], ..., [r.sub.m] = r' such that

[L.sub.2]([r.sub.0], [r.sub.1]) [subset] [L.sub.2]([r.sub.0], [r.sub.2]) [subset] ... [subset] [L.sub.2]([r.sub.0],[ .sub.r]m) [absolute value of [L.sub.2]([r.sub.0], [r.sub.i])\[L.sub.2]([r.sub.0], [r.sub.i-1])] = 1.

Any gallery r is determined by its [L.sub.2]-separation set [L.sub.2]([r.sub.0], r) from some fixed gallery [r.sub.0]. This follows since the relative order of any two hyperplanes H, H' in the total order on A induced by r is the same as their relative order in [r.sub.H[intersection]H'].

The Hasse diagram of R(A, [r.sub.0]) is an orientation of the graph of reduced galleries from [c.sub.0] to -[c.sub.0] in A. One of the reasons for studying the poset R is to deduce properties of this graph from those of R.

A flat X [member of] L(A) of a hyperplane arrangement A is modular if X + Y [member of] L(A) for all Y [member of] L(A). A hyperplane arrangement A is supersolvable if its lattice of flats L(A) contains a maximal chain of modular elements [R.sup.d] = [X.sub.0] < [X.sub.1] < .... < [X.sub.d] = 0, [X.sub.i] [member of] [L.sub.i](A). For our purposes, it will be useful to define a maximal chain of faces [F.sub.0] < [F.sub.1] < ... < [F.sub.d] = 0, [F.sub.i] [member of] [[Laplace].sub.i](A) to be a modular chain if the flats [F.sup.0.sub.i] are all modular.

A gallery r from c to d is incident to a face F [member of] [Laplace](A) if r contains the chambers F x c and F x d. A gallery is incident to a subspace X [member of] L(A) if it is incident to some face spanning X. We say a gallery r is incident to a modular flag [c.sub.0] = [F.sub.0] < [F.sub.1] < ... < [F.sub.d] = 0 if it contains [F.sub.i] x [c.sub.0] and [F.sub.i] x (-[c.sub.0]) for all i. Intuitively this means r first crosses [F.sub.1], then wraps around [F.sub.2], then around [F.sub.3], and so on.

Example 4.1 The type [A.sub.n-1] reflection arrangement A is the set

{[H.sub.ij] = ker[([x.sub.i] - [x.sub.j]) [subset] [R.sup.n]).sub.1[less than or equal to]i<j[less than or equal to]n].

Its intersection lattice [Laplace](A) is in natural correspondence with set partitions of [n]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, the face poset [Laplace](A) is in correspondence with set compositions of [n]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The face poset [Laplace](A) contains a modular chain

(1, 2, 3, 4, ..., n) > (12, 3, 4, ..., n) > (123, 4, ..., n) > ... > (1234 ... n)

Any gallery incident to this flag must contain the chambers

(1, 2, 3 4, ..., (2, 1 3, 4, ..., (3, 2, 1 4, ..., ..., (n, ..., 4, 3 2, 1).

It is clear that there is a unique gallery [r.sub.0] containing these chambers: starting from the base chamber (1, 2, ..., n), the 2 is pushed to the front, then the 3, then the 4, etc. In Coxeter notation, [r.sub.0] corresponds to the reduced word [s.sub.1]([s.sub.2][s.sub.1])([s.sub.3][s.sub.2][s.sub.1]) ... ([s.sub.n-1][s.sub.n-2] .... [s.sub.1]).

A simple way to show R(A, [r.sub.0]) is bounded and graded by r [??] [absolute value of [L.sub.2]([r.sub.0], r)] is via wiring diagrams; see Figure 4. Given the wiring diagram corresponding to some gallery r, one can remove elements in the [L.sub.2]-separation set by slowly "pulling " the n-th wire so it crosses all of the other wires at the end. Each triple {ijn} or 2-pair {ij, kn} involving wire n on which [r.sub.0] and r disagree is resolved by this procedure without affecting other elements of [L.sub.2](A). Inducting on n, we conclude that [r.sub.0] [less than or equal to] r as desired.

In , Reiner and Roichman generalized the idea of "pulling out the n-th wire" for arbitrary supersolvable arrangements to prove that R(A, [r.sub.0]) is a bounded, graded poset. The key property of supersolvable arrangements is the linearity of the fibers of the localization map at a modular line, as described in the following Proposition.

Proposition 4.2 (RR ) Assume that l is a modular ray in [Laplace](A). Let [c.sub.l] [member of] P([A.sub.l], ([c.sub.0]);) be a chamber of the localized arrangement A;. Let [pi]: P(A, [c.sub.0]) [right arrow] P([A.sub.l], ([c.sub.0]);) be the localization map.

1. There exists a linear order on the fiber [[pi].sup.-1]([c.sub.l]) = {[c.sub.1], [c.sub.2], ..., [c.sub.t]} such that [c.sub.1] is incident to l and the separation sets [L.sub.1]([c.sub.1], [c.sub.i]) are nested:

0 = [L.sub.1]([c.sub.1], [c.sub.1]) [subset] [L.sub.1]([c.sub.1], [c.sub.2]) [subset] ... [subset] [L.sub.1]([c.sub.1], [c.sub.t]) = A\[A.sub.l]

This induces a linear order [H.sub.1], [H.sub.2], ... on A\[A.sub.l] such that [H.sub.i] is the unique hyperplane separating [c.sub.i] and [c.sub.i+1].

2. Using the linear order on A\[A.sub.l] from part (1), if i < j < k and if the chamber c incident to I is also incident to I + [H.sub.i] [intersection] [H.sub.k] then [H.sub.j] [contains or equal to] [H.sub.i] [intersection] [H.sub.k].

The next proposition says that the fibers of the localization map are bounded.

Proposition 4.3 (RR ) Assume that I is a modular ray and let [c.sub.0] be a chamber incident to l. Let [pi] denote the function r [??] [r.sub.l] sending galleries of A from [c.sub.0] to -[c.sub.0] to galleries of [A.sub.l]. Given a reduced gallery [r.sub.l] [member of] [A.sub.l], let [r.sub.1] be the unique gallery incident to l in the fiber [[pi].sup.- 1]([r.sub.l]) defined by Proposition 4.2(1). If [r.sub.1] [not equal to] [r.sub.2] [member of] [[pi].sup.-1]([r.sub.l]) there exists X [member of] [L.sub.2]([r.sub.1], [r.sub.2]) incident to [r.sub.2].

Inducting on the rank of A, Reiner and Roichman conclude that if [r.sub.0] is incident to a modular flag of A, then R(A, [r.sub.0]) is a bounded graded poset.

Bjorner, Edelman, and Ziegler proved that the chamber poset P(A, [c.sub.0]) of a supersolvable arrangement is a lattice if [c.sub.0] is incident to a modular flag . In contrast, the gallery poset R(A, [r.sub.0]) is not a lattice in general; see Example 4.1.

The gallery poset R(A, [r.sub.0]) is defined by measuring the "difference" between two galleries with a set [L.sub.2](r, r') and ordering the galleries by single-step inclusion of the sets [L.sub.2]([r.sub.0], r). Ordering instead by ordinary inclusion defines a poset [R.sub.[subset or equal to]](A, [r.sub.0]). We do not know whether these posets are ever distinct when r0 is incident to a modular flag of A. When A is the type A braid arrangement, this question resembles a question about two versions of the second Higher Bruhat orders, B(n, 2) and [B.sub.[subset or equal to]](n, 2). These two posets were shown to be the same by Felsner and Weil .

5 Homotopy type of the gallery poset

Theorem 5.1 Let [r.sub.0] be a gallery incident to a modular flag of a rank d supersolvable arrangement A. The proper part of the poset of reduced galleries R(A, [r.sub.0]) is homotopy equivalent to a (d - 3)-sphere.

The main topological result we use to prove the theorem is Rambau's Suspension Lemma .

Lemma 5.2 (Rambau) Let P, Q be bounded posets with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and distinguished order ideal J [subset or equal to] P. Let f: P [right arrow] Q be a surjective order-preserving map with order-preserving sections i, j: Q [right arrow] P. Assume that

1. i(Q) [subset or equal to] J and j (Q) [subset or equal to] P\J

2. ([for all]p [member of] P) (i x f)(p) [less than or equal to] p [less than or equal to] (j x f )(p)

3. [f.sup.-1]([[??].sub.q]) [intersection] J = {[[??].sub.p]} and [f.sup.-1]([[??].sub.Q]) [intersection] (P\J) = {[[??].sub.P]}

Then [bar.P] is homotopy equivalent to the suspension of [bar.Q].

Figure 5 shows an application of the Suspension Lemma to the gallery poset of the four coordinate hyperplanes in [R.sup.4].

Proof: (of theorem) We begin by defining the maps and objects in the Suspension Lemma 5.2.

Let F be a modular flag of faces

F: [c.sub.0] = [F.sub.0] < [F.sub.1] < ... < [F.sub.d] = 0, [F.sub.i] [member of] [Laplace](A),

and set l = [F.sub.d-1]. Let [r.sub.0] be the unique gallery incident to F.

Define gallery posets P = R(A, [r.sub.0]), Q = R([A.sub.l], [([r.sub.0]).sub.l]), and let f: P [right arrow] Q be usual localization map removing hyperplanes not containing l.

Define a section i: Q [right arrow] P by lifting a gallery [r.sub.l] in Q along l to a gallery from l x [c.sub.0] to l x (-[c.sub.0]) and completing it in the unique way described in Proposition 4.2. We similarly define a section j: Q [right arrow] P by lifting along -l.

Let (H,H') be the unique pair of adjacent hyperplanes in [r.sub.0] such that H [contains or equal to] l and H' [contains or not equal to] l. We claim that [X.sub.0] = H [intersection] H' is the unique codimension 2 subspace incident to [r.sub.0] not containing l. Uniqueness holds since any Y [member of] [L.sub.2](A)\[L.sub.2]([A.sub.l]) contains some hyperplane of [A.sub.l] by the modularity of l, but the hyperplanes in [A.sub.l] appear in [r.sub.0] before those of A\[A.sub.l]. Incidence at [X.sub.0] follows from Proposition 4.2(2). Let J denote the order ideal {r [member of] P | [X.sub.0] [member of] [L.sub.2]([r.sub.0], r)}.

With this setup, we verify the three properties in Lemma 5.2. (1) is clear since [L.sub.2]([r.sub.0], i(r)) is a subset of [L.sub.2]([A.sub.l]) and [L.sub.2]([r.sub.0], j(r)) is a superset of [L.sub.2](A)\[L.sub.2]([A.sub.l]). Proposition 4.3 implies i(r) is the minimum element of the fiber [f.sup.-1](r). Dually, j(r) is the maximum element of [f.sup.-1](r). This verifies (2). Finally, (3) follows from the uniqueness of [X.sub.0].

The proof of Theorem 5.1 applies to [R.sub.[subset or equal to]] with little variation, so we do not repeat it here. An alternate proof using the Crosscut Lemma also computes the homotopy type of [R.sub.[subset or equal to]], but that argument does not suffice for R.

6 Main Theorem

Theorem 6.1 Let A be a supersolvable arrangement with chamber [c.sub.0] and gallery [r.sub.0] incident to a modular flag. Let x = ([X.sub.1], [X.sub.2], ..., [X.sub.m]) [member of] [omega](A, [c.sub.0]) be a cellular string of A The set of galleries incident to x forms a closed interval of R(A, [r.sub.0]) whose proper part is homotopy equivalent to a sphere of dimension [[summation].sup.m.sub.i=1] codim([X.sub.i]) - m - 2.

To decompose the set of galleries incident to a cellular string into a product of bounded posets, we make use of the following simple lemma.

Lemma 6.2 Assume A is supersolvable with modular flag of faces F: [F.sub.0] < [F.sub.1] < ... < [F.sub.d] = 0 .If X [member of] L(A) then the localized arrangement [A.sub.X] is supersolvable with modular flag

[F.sub.X]: [([F.sub.0]).sub.X] [less than or equal to] [([F.sub.1]).sub.X] [less than or equal to] ... [less than or equal to] [([F.sub.d]).sub.X] = 0.

If [r.sub.0] is the unique gallery incident to F, then [([r.sub.0]).sub.X] is the unique gallery incident to [F.sub.X].

Proof: (of theorem) For each [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a poset of galleries of a supersolvable arrangement with base gallery incident to a modular flag. By Theorem 5.1, the proper part of R is homotopy equivalent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A gallery [r.sub.i] in [R.sub.i] can be viewed as a gallery between [X.sub.i] x [c.sub.0] and [X.sub.i] x (-[c.sub.0]) in the arrangement A. Since x is a cellular string, any sequence [([r.sub.i] [member of] [R.sub.i]).sup.*] can be patched together to a gallery between [c.sub.0] and -[c.sub.0] in A. Consequently, the galleries incident to x may be indentified with the product poset

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In general, if bounded posets P, Q are homotopy equivalent to spheres [S.sup.p], [S.sup.q], respectively, then [bar.PxQ] is homotopy equivalent to [S.sup.p+q+2]. Applying this fact to the above product completes the proof.

Example 6.3 Continuing Example 4.1, the cellular strings [omega](A, [c.sub.0]) may be identified with wiring diagrams where multiple wires may cross at a vertical section. The set of galleries incident to a given cellular string x are the simple wiring diagrams obtained by resolving multiple crossings in the diagram associated to x. The incident galleries form an interval in R(A, [r.sub.0]) whose minimum element resolves multiple crossings in colexicographic order and whose maximum element resolves in reverse colexicographic order. Figure 6 shows an example.

7 Generic lifting spaces

The chamber and gallery posets have a common generalization to a poset G(M, N) of generic singleelement liftings of an oriented matroid. The precise definition is rather technical and will be described in a separate paper. Roughly speaking, G(M, N) consists of generic affine slices of M with some prescribed boundary. When M is realizable as a hyperplane arrangement, the rank 2 slices can be identified with galleries.

Special cases of these posets were called uniform extension posets by Ziegler . Ziegler observed that these posets tend to be poorly behaved. However, when the base extension is an alternating matroid, one obtains a bounded graded poset known as a Higher Bruhat order. We are interested in finding other cases where G(M, N) is a bounded graded poset with nice topology. We summarize the main results about the Higher Bruhat orders here.

A set family [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is consistent if for any (k + 2)-subset P = {[i.sub.0] < [i.sub.1] < ... < [i.sub.k+1]} of [n], the intersection [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is either {P\[i.sub.k+1], P\[i.sub.k], ..., P\[i.sub.t]} or {P\[i.sub.0], P\[i.sub.1], ..., P\[i.sub.t]} for some t. The Higher Bruhat order B(n, k) is the collection of consistent set families [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ordered by single-step inclusion.

In , Ziegler proved that B(n, k) is isomorphic a poset of generic single-element liftings of the rank k alternating matroid M (n, k) on [n]. In a way similar to the gallery posets, the single-element liftings are ordered by single-step inclusion of a difference set from the affine alternating matroid M(n + 1, k + 1). Ziegler proved that B (n, k) is a bounded, graded poset. He also observed that choosing a different base lifting can determine an unbounded poset. In future work, we explain the relevance of the alternating matroid by showing it is "incident" to a modular flag of M(n, n).

Rambau showed that [bar.B](n, k) is homotopy equivalent to [S.sup.n-k-2]. Analogous to our conjecture on the intervals of the gallery posets, Reiner conjectured that the set of noncontracible intervals of B(n, k) is naturally parameterized by the full lifting space [omega](n, k) of M (n, k) (Conjecture 6.9(a) ). Just as in the discussion following Theorem 1.2, this connection would imply the previous result of Sturmfels and Ziegler that [bar.[omega]](n, k) is homotopy equivalent to [S.sup.n-k-1] .

Acknowledgements

The author thanks his advisor Pavlo Pylyavskyy and Vic Reiner for helpful discussions and suggestions.

References

 Christos A Athanasiadis, Paul H Edelman, and Victor Reiner. Monotone paths on polytopes. Mathematische Zeitschrift, 235(2):315-334, 2000.

 Louis J Billera, Mikhail M Kapranov, and Bernd Sturmfels. Cellular strings on polytopes. Proceedings of the American Mathematical Society, 122(2):549-555, 1994.

 A. Bjorner, P.H. Edelman, and G.M. Ziegler. Hyperplane arrangements with a lattice of regions. Discrete & computational geometry, 5(3):263-288, 1990.

 Anders Bjorner. Orderings of coxeter groups. Combinatorics and algebra, 34:175-195, 1984.

 Anders Bjorner. Essential chains and homotopy type of posets. Proceedings of the American Mathematical Society, 116(4):1179-1181, 1992.

 Anders Bjorner. Topological methods. handbook of combinatorics, vol. 1, 2, 1819-1872, 1995.

 Paul H Edelman and James W Walker. The homotopy type of hyperplane posets. Proceedings of the American Mathematical Society, 94(2):221-225, 1985.

 Stefan Felsner and Helmut Weil. A theorem on higher bruhat orders. Discrete & Computational Geometry, 23(1):121-127, 2000.

 Jorg Rambau. A suspension lemma for bounded posets. Journal of Combinatorial Theory, Series A, 80(2):374-379, 1997.

 Vic Reiner and Yuval Roichman. Diameter of graphs of reduced words and galleries. Trans. Amer. Math. Soc., 365:2779-2802, 2013.

 Victor Reiner. The generalized baues problem. New perspectives in algebraic combinatorics, 38:293-336, 1999.

 Bernd Sturmfels and Gunter M. Ziegler. Extension spaces of oriented matroids. Discrete & Computational Geometry, 10:23-45, 1993.

 Gunter M. Ziegler. Higher bruhat orders and cyclic hyperplane arrangements. Topology, 32:259-279, 1993.

Thomas McConville *

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

* Email: mcco0 4 8 9@umn.edu. Supported by RTG grant NSF/DMS-1148634
Author: Printer friendly Cite/link Email Feedback McConville, Thomas DMTCS Proceedings Report Jan 1, 2014 5877 Stabilized-interval-free permutations and chord-connected permutations. Weakly prudent self-avoiding bridges. Fuzzy sets Homotopy theory Mathematical research Set theory