Printer Friendly

Poset topology and homological invariants of algebras arising in algebraic combinatorics.

1 Introduction

In a highly influential paper [3], Bidigare, Hanlon and Rockmore showed that a number of popular Markov chains are random walks on the faces of a hyperplane arrangement. Their analysis of these Markov chains took advantage of the monoid structure on the set of faces. This theory was later extended by Brown [11, 12] to a larger class of monoids called left regular bands. In both cases, the representation theory of these monoids play a prominent role. It is used to compute the spectrum of the transition operators of the Markov chains and to prove diagonalizability of the transition operators.

It develops that there is a close connection between algebraic and combinatorial invariants of these monoids: certain homological invariants of the monoid algebra coincide with the cohomology of order complexes of posets naturally associated with a monoid. We present here a synopsis of the results together with applications of this beautiful interplay between combinatorial topology and homological algebra.

The full details will appear in two longer papers [23, 25], which include lengthy discussions of the history, examples and applications of these monoids as well as thorough references to the literature.

2 Left Regular Bands

A particularly important class of monoids arising in probability theory and in algebraic combinatorics is the class of left regular bands [11, 12, 13, 27, 28, 7, 16].

Definition 2.1 A left regular band is a semigroup B satisfying the identities

[chi square] = x for all x [member of] B, (1)

xyx = xy for all x, y [member of] B. (2)

In general we will assume in this paper that B is finite and has an identity (is a monoid).

An example arises from the set {0, +, -}, where the monoid operation o satisfies x x y = x if x [not equal to] 0 and x x y = y otherwise. Several important examples of left regular bands arising in combinatorics are submonoids of [{0, +, -}.sup.n]. These include the monoid structure on both real hyperplane arrangements, matroids, oriented matriods and interval greedoids (see Section 3).

It is known that left regular bands are precisely the homomorphic images of submonoids of [{0, +, -}.sup.n], for some n. The paper [24] classifies those that are submonoids of some [{0, +, -}.sup.n]. Almost all the left regular bands appearing so far in the algebraic combinatorics literature embed in [{0, +, -}.sup.n]; the main exception are the complex hyperplane monoids discussed in [section] 5.4 below.

The following two posets associated with a left regular band play a central role in what follows.

R-poset. For a monoid M and m [member of] M, we let mM = {mm': m' [member of] M} denote the principal right ideal generated by m. Green's R-preorder is defined on M by m [[less than or equal to].sub.R] n if mM [subset or equal to] nM. The associated equivalence relation is denoted R; it is one of Green's relations on a monoid [19].

In a left regular band B, Green's R-preorder admits the following description:

a [[less than or equal to].sub.R] b iff ba = a.

Indeed, if aM [subset or equal to] bM, then a = bm and so ba = [b.sup.2]m = bm = a. Thus, if a [[less than or equal to].sub.R] b and b [[less than or equal to].sub.R] a, then a = aba = ab = b. It follows that B is a poset with respect to [[less than or equal to].sub.R]. We call this partial order the R-order on B and denote it simply by [less than or equal to]. Figures 1 and 2 illustrate the R-order on specific examples.

Support Lattice. For a left regular band B, let [LAMBDA](B) denote the set of principal left ideals of B:

[LAMBDA](B) = {Ba: a [member of] B}

where Ba = {ba : b[member of]G B}. Then [LAMBDA](B) is a poset under inclusion. Furthermore, it is a lattice with intersection as the meet operation (denoted [conjunction]). The map [sigma]: B [right arrow] [LAMBDA](B) given by [sigma](a) = Ba satisfies the following properties for all a, b [member of] B:

[sigma](ab) = [sigma](a) [conjunction] [sigma](b) and ab = a iff [sigma](b) [greater than or equal to] [sigma](a) (3)

The first property says that a is a monoid morphism. Note that [sigma] is an order preserving poset morphism: that is, if a [[less than or equal to].sub.R] b, then [sigma](a) [less than or equal to] [sigma](b). Proofs of these statements can be found in [17, 11].

Following the standard conventions of lattice theory, we denote by 1 the top of [LAMBDA](B) (which is B, itself) and by [??] the bottom (called the minimal ideal of B). In [11, 12], Brown calls [LAMBDA](B) the support lattice of B (although he uses the reverse ordering) and a is called the support map.

3 Examples of Left Regular Bands

This section quickly surveys some examples of left regular bands found in the combinatorics literature. Often, these are special cases of certain semigroup-theoretic constructions. Further examples and detailed expositions can be found in [23]. We also describe a new class of left regular bands introduced in [23].

Free left regular bands. The free left regular band on a set A will be denoted F (A) and the free left regular band on n-generators will be written [F.sub.n]. One can view F (A) as the set of words over A with no repeated letters (cf. (2)); multiplication is concatenation followed by removal of repetitions (reading from left to right). For example, in [F.sub.5] we have 523 * 13245 = 52314. The support lattice of F(A) can be identified with the power set P (A) with the operation of union; the support map [sigma] takes a word to the set of letters appearing in the word; Figure 1 illustrates the R-order and the support lattice of F({a, b, c}).

Hyperplane face monoids and oriented matroids Hyperplane arrangements, and more generally oriented matroids, provide an important source of examples of left regular bands, which turn out to be submonoids of the left regular band [{0, +, -}.sup.n] introduced in Section 2. We recall the construction and properties of these left regular bands referring the reader to [11, Appendix A] for details.

A central hyperplane arrangement in V = [R.sup.n] is a finite collection A of hyperplanes of V passing through the origin. For each hyperplane H [member of] A, fix a labelling [H.sup.+] and [H.sup.-] of the two open half spaces of V determined by H; the choice of labels [H.sup.+] and [H.sup.-] is arbitrary, but fixed throughout. Let [H.sup.0] = H.

The elements of the monoid are the faces of A: the non-empty intersections of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [[epsilon].sub.H] [member of] {0, +, -}. Thus, a face x is completely determined by the sequence [epsilon](x) = [([[epsilon].sub.H]).sub.H[member of]A]. See Figure 2. The image of e identifies the set of faces of A with a submonoid of [{0, +, -}.sup.A] and so we obtain a monoid structure by defining the product of x and y to be the face with sign sequence [epsilon](x) x [epsilon](y).

The monoid of faces of A is called the face monoid and is denoted F. The lattice A(F) is isomorphic to the intersection lattice [Laplace] of A; it consists of the subspaces of V that can be expressed as an intersection of hyperplanes from A. Under this isomorphism, the support map a corresponds to the map that sends a face x to the smallest subspace that contains x.

Free partially commutative left regular bands. If [GAMMA] = (V, E) is a simple graph, then the free partially commutative left regular band associated with [GAMMA] is the left regular band B([GAMMA]) with presentation

B([GAMMA]) = (V | xy = yx for all edges {x, y} [member of] E).

This is the left regular band analogue of free partially commutative monoids (also called trace monoids or graph monoids [18, 14]) and of free partially commutative groups (also called right-angled Artin groups or graph groups [31]). For example, if [GAMMA] has no edges, then B([GAMMA]) is the free left regular band on the vertex set, whereas if r is a complete graph, then B([GAMMA]) is the free semilattice on the vertex set of [GAMMA].

The elements of B([GAMMA]) correspond to acyclic orientations of induced subgraphs of the complementary graph [bar.[GAMMA]] of [GAMMA]. Indeed, any element w of the free left regular band F(V), which is a repetition-free sequence of vertices, gives rise to an acyclic orientation O(w) as follows: the vertices of the subgraph are the letters appearing in w; there is an edge x [right arrow] y if x comes before y in w and if {x, y} is not an edge of [GAMMA].

Theorem 3.1 Elements [upsilon], w [member of] F (V) are equal in B([GAMMA]) if and only if a([upsilon]) = [sigma](w) and O([upsilon]) = O(w).

The Tsetlin library Markov chain can be modelled as a hyperplane random walk, but is most naturally a random walk on the free left regular band, see [11, 12] for details. Similarly, the random walk on acyclic orientations of a graph considered by Athanasiadis and Diaconis as a function of a hyperplane walk [2] is most naturally a random walk on a free partially commutative left regular band.

Other examples. There are numerous other examples of left regular bands appearing in disguise in the algebraic combinatorics literature and elsewhere, as well as numerous examples of left regular band semigroups. These include the face semigroup of an affine hyperplane arrangement, the set of covectors associated with an affine oriented matroid or a T-convex set of topes and the face semigroup of a finite CAT(0) cube complex. These are presented in detail in [23, 25].

4 Statement of the Main Result

Our main result expresses certain algebraic invariants of B in terms of the cohomology of simplicial complexes associated with its R-poset. This allows us to compute these algebraic invariants using the combinatorics of the poset, which we do for certain classes of left regular bands in the next section.

We begin by describing the algebraic invariants. Fix a commutative ring with unit k. For every element X of the support lattice A(B), the ring k becomes a kB-module via the action

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

for all b [member of] B and [alpha] [member of] k. These modules, denoted by [k.sub.X], are precisely the simple kB- modules when k is a field [11, 27]. We are interested in computing the algebraic invariants [Ext.sup.n.sub.B]([k.sub.X], [k.sub.Y]) for two such modules [1]. It turns out that these invariants coincide precisely with the cohomology of certain simplicial complexes associated with B, so a detailed description of [Ext.sup.n] is not necessary for what follows. Indeed, the power of the main result resides in the fact that we can compute these algebraic invariants by making use of combinatorial properties of B.

For elements X and Y of the support lattice [LAMBDA](B), pick an element y [member of] B with [sigma](y) = Y and define

B[X, Y] = {z [member of] B: X [less than or equal to] [sigma](z) and z [[less than or equal to].sub.R] y}.

Passing from B to the monoid B[X, Y] corresponds to the restriction-contraction operation for oriented matroids. This is a subposet of B with respect to Green's R-order. Let [DELTA](B[X, Y)) be the order complex of the poset B[X, Y]\{y}: it is the simplicial complex whose vertex set is B[X, Y]\{y} and whose simplices are the finite chains in the poset. (Up to isomorphism, this poset does not depend on the choice of y [member of] Y.)

Theorem 4.1 Let B be a finite left regular band, k a commutative ring with unit, and X,Y G A (B). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5 Applications of the Main Result

5.1 Quiver with relations of a left regular band algebra

We begin by investigating applications of the degree 0 and degree 1 cohomology. They encode information about the structure of the monoid algebra kB and allows us to describe a quiver presentation of kB.

Quiver. Assume for the moment that k is a field. Then the dimension of the degree 0 cohomology of [DELTA](B[X, Y)) counts its number of connected components [29]. Combined with Theorem 4.1, we obtain a combinatorial interpretation of the dimension of [Ext.sup.1.sub.kB]([k.sub.X], [k.sub.Y]). The dimensions of these spaces carry all the information needed to construct the quiver of an algebra [1], which yields the following new description for the quiver of kB. This is more conceptual and sometimes easier to apply than [27].

Theorem 5.1 Let B be a finite left regular band and k afield. Then the quiver of kB has vertex set [LAMBDA](B). The number of arrows from X to Y is zero unless X < Y, in which case it is one less than the number of connected components of [DELTA](B[X, Y)).

The quiver of [kF.sub.3] is depicted in Figure 3; for instance, there are two arrows from the bottom to the top since there are three connected components in the Hasse diagram of the R-order on [F.sub.3]\{1}. Corollary 5.3 provides a description of the quiver of [F.sub.n] for all n [greater than or equal to] 0.

Quiver relations. One can think of a quiver as a combinatorial encoding of a special presentation of the algebra by generators and relations: the quiver is a directed graph whose vertices correspond to primitive orthogonal idempotents and whose arrows correspond to a minimal generating set of the radical. Relations take the form of linear combinations of paths of the quiver [1]. A result of Bongartz [1, 10] implies that the number of relations involving paths between two vertices in a minimal quiver presentation for a left regular band algebra is determined by the dimension of [Ext.sup.2]. Theorem 4.1 admits the following corollary.

Corollary 5.2 If X < Y in [LAMBDA](B), then the number of relations involving paths from X to Y in a minimal quiver presentation of a left regular band algebra kB is given by dimk [[??].sup.1]([DELTA](B[X, Y)), k).

5.2 Algebras of free left regular bands are hereditary

A finite dimensional algebra whose left ideals are projective modules is called hereditary. This is equivalent to the property that [Ext.sup.2] vanishes; to the property that each submodule of a projective module is projective; and to the property that the global dimension of the algebra is at most 1. A result of Gabriel says that a split basic algebra is hereditary precisely when it has a quiver presentation with an acyclic quiver and no relations [1]. In section 5.6 we will see a characterization of those left regular band algebras kB that are hereditary in terms of the order complex of B, but we foreshadow it by showing that the algebra of the free left regular band is hereditary.

The Hasse diagram of the R-order of the free left regular band [F.sub.n] is a tree, as are the diagrams of the subposets [F.sub.n][X, Y]. Consequently, the cohomology of the complexes [DELTA](B[X, Y)) vanishes in positive degrees. Theorem 5.1 and Corollary 5.2 combine to show that [kF.sub.n] is hereditary and to describe its quiver.

Corollary 5.3 The algebra [kF.sub.n] is hereditary over any field k. Its quiver has vertex set the subsets of {1, ..., n}. If X [??] Y, then there are [absolute value of X\Y] - 1 arrows from X to Y. There are no other arrows.

This result was first proved by K. Brown using quivers and a counting argument [27, Theorem 13.1]. Our argument for heredity generalizes to any left regular band whose R-order is a tree; we call such left regular bands right hereditary. These include the matroid left regular bands of Brown [11], the interval greedoid left regular bands of Bjorner [7], and the Rhodes and Karnofsky-Rhodes expansions of a lattice [23]. We will see in Theorem 5.9 another, more transparent, proof of Corollary 5.3, which also makes it simple to compute the quiver of a right hereditary left regular band.

5.3 Hyperplane face monoids

Recall that A denotes a central hyperplane arrangement in a d-dimensional real vector space V, [Laplace] its intersection lattice, and F its left regular band of faces. Without loss of generality, we suppose that the intersection of all the hyperplanes in A is the origin: otherwise quotient V by this intersection.

We argue that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a (d - 1)-sphere. The R-order on F can be described geometrically as y [less than or equal to] x if and only if x [subset or equal to] [bar.y], where [bar.y] denotes the set-theoretic closure of y. This establishes an order-reversing bijection between F\{1} and the cells of the regular cell decomposition [summation] obtained by intersecting the arrangement with a sphere centered at the origin. The dual of E is the boundary of a polytope whose poset of faces is isomorphic to F [13]. Since the order complex of the poset of faces of a polytope is the barycentric subdivision of the polytope, it follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a (d - 1)-sphere.

This argument also applies to [DELTA](B[X, Y)) with X [less than or equal to] Y since it corresponds to the hyperplane arrangement in X obtained by intersecting X with the hyperplanes in A containing Y and not X. It follows that [DELTA](B[X, Y)) is a sphere of dimension dim(X) - dim(Y) - 1. Thus, we recover Lemma 8.3 of [28].

Proposition 5.4 For X, Y [member of] [Laplace] and n [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We apply Theorem 4.1. Since [DELTA](B[X, Y)) is a sphere of dimension dim(X) - dim(Y) - 1, it follows that [[??].sup.n-1]([DELTA](B[X, Y)), k) is 0 unless dim(X) - dim(Y) = n, in which case it is k.

It follows that the quiver of kF coincides with the Hasse diagram of [Laplace] ordered by reverse inclusion.

Corollary 5.5 (Saliola [28, Corollary 8.4]) The quiver of kF has vertex set [Laplace]. The number of arrows from X to Y is zero unless Y X and dim(X) - dim(Y) = 1, in which case there is exactly one arrow.

In [28] a set of quiver relations for kF was described: for each interval of length two in L take the sum of all paths of length two in the interval. It was also shown that kF is a Koszul algebra and that its Koszul dual algebra is isomorphic to the incidence algebra of the intersection lattice [Laplace].

5.4 Complex hyperplane face monoids

There is a left regular band of faces that one can associate with a complex arrangement [9] and it turns out that the situation for complex hyperplane arrangements is similar to that of real hyperplane arrangements. Things are slightly more complicated in this setting because the complexes A(B[X, Y)) do not arise from complex hyperplane face monoids. However, a careful analysis of the PL structure of the cell complex associated with the arrangement reveals that [DELTA](B [X, Y)) is a sphere of dimension dimR X - [dim.sub.R] Y - 1, from which we obtain the following analogues of the results from the real case, cf. [section] 5.3.

Proposition 5.6 For X, Y [member of] [Laplace] and n [greater than or equal to] 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

An immediate consequence is that the quiver of kF coincides with the Hasse diagram of the augmented intersection lattice L ordered by reverse inclusion, as was the case for real hyperplane arrangements.

5.5 Geometric left regular bands and commutation graphs

We say that a left regular band B is geometric if, for each a [member of] B, the left stabilizer {b [member of] B | b [[less than or equal to].sub.R] a} of a is commutative (and hence a lattice under the order [[less than or equal to].sub.R] with the meet given by the product). The left regular bands associated to hyperplane arrangements, oriented matroids and CAT(0) cube complexes are geometric, whence the name. Almost all the left regular bands appearing so far in the algebraic combinatorics literature embed in [{0, +, -}.sup.n] and hence are geometric (see the discussion in [section] 2).

For a finite geometric left regular band B, we will use the following special case of Rota's cross-cut theorem [26, 6] to provide a simplicial complex homotopy equivalent to the order complex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of B\{1}. This second complex simplifies the computation of the quiver of kB.

Theorem 5.7 (Rota) Let P be a finite poset such that any subset of P with a common lower bound has a meet. Define a simplicial complex K with vertices the maximal elements of P and with simplices those subsets with a common lower bound. Then K is homotopy equivalent to the order complex [DELTA](P).

We also need the well-known notion of the clique complex or flag complex Cliq(G) of a simple graph G: it is the simplicial complex whose vertices are the vertices of G and whose simplices are the subsets of vertices that induce a complete subgraph. Notice that G is the 1-skeleton of Cliq(G) and that Cliq(G) is obtained by 'filling in' the 1-skeleton of every q-simplex found in G.

Let M(B) be the set of maximal elements of B\{1} and let [GAMMA](M(B)) be the commutation graph of M(B): that is, the graph whose vertex set is M(B) and whose edges are pairs (a, b) such that ab = ba. For oriented matroids, the commutation graph is known as the cocircuit graph in the literature [8].

Theorem 5.8 If B is a finite geometric left regular band, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to the clique complex Cliq([GAMMA](M(B))) of the commutation graph [GAMMA](M(B)) of the maximal elements of B\{1}.

Theorem 5.8 can be used to give another proof that if a left regular band B is right hereditary, then kB is hereditary (cf. Section 5.2). It also leads to an easy computation of the quiver.

Theorem 5.9 Let B be a finite, right hereditary, left regular band and k afield. Then kB is hereditary. Its quiver has vertex set [LAMBDA](B). The number of arrows from X to Y is zero if X [??] Y; otherwise, it is one less than the number of children of y with support greater than or equal to X (for any y [member of] B with [sigma](y) = Y).

Theorem 5.9 covers the algebras of nearly all the left regular bands considered by K. Brown in [11] (except the hyperplane monoids) and the interval greedoid left regular bands of Bjorner [7].

5.6 Global dimension of a left regular band algebra

We now turn to applications of the higher degree cohomology spaces, especially the first degree for which the higher degree cohomology vanishes. This "vanishing degree" relates the Leray number of the simplicial complex with the global dimension of the monoid algebra.

The global dimension gl. dim A of a finite dimensional algebra A over a field k is the smallest integer n such that [Ext.sup.m.sub.A]([S.sub.1], [S.sub.2]) = 0 for all m> n and all simple A-modules [S.sub.1] and [S.sub.2] (see [1]). An algebra A has global dimension zero if and only if it is semisimple; it has gl. dim A [less than or equal to] 1 if and only if it is hereditary.

Theorem 5.10 Let B be a finite left regular band and k afield. Then

gl.dim kB = min{n: [[??].sup.n]([DELTA](B[X, Y)), k) = 0 for all X, Y [member of] [LAMBDA](B) with X < Y}.

In particular, one has gl. dim kB [less than or equal to] m where m is the length of the longest chain in [LAMBDA](B).

As an immediate corollary, we obtain a characterization of those algebras kB that are hereditary in terms of the order complex of B.

Corollary 5.11 The monoid algebra kB of a left regular band is hereditary if and only if each connected component of each simplicial complex [DELTA](B[X, Y )),for X < Y [member of] A(B), is acyclic.

5.7 Leray numbers and an improved upper bound on global dimension

We can improve on the upper bound from Theorem 5.10 using the Leray number of a simplicial complex. The k-Leray number of a simplicial complex K with vertex set V is

[L.sub.k](K) = min {d: [[??].sup.i](K[W], k) = 0 for all i [less than or equal to] d and all W [subset or equal to] V},

where K[W] denotes the subcomplex of K consisting of all simplices whose vertices belong to W.

Theorem 5.12 Let B be a finite left regular band and k afield. Then gl. dim k B is bounded above by the Leray number [L.sub.k]([DELTA](B)) of the order complex of B.

Originally, interest in Leray numbers came about because of connections with Helly-type theorems [30, 22,21]: the Leray number of a simplicial complex provides an obstruction for realizing the complex as the nerve of a collection of compact convex subsets of [R.sup.d]. Leray numbers also play a role in combinatorial commutative algebra: [L.sub.k](K) turns out to be the Castelnuovo-Mumford regularity of the Stanley-Reisner ring of K over k [21]; or equivalently, [L.sub.k](K) + 1 is the regularity of the face ideal of K [20].

In section 5.8, we give a new interpretation to the Leray number of the clique complex of a graph in terms of non-commutative algebra.

5.8 Leray numbers and free partially commutative left regular bands

In this section, we prove that the global dimension of a free partially commutative left regular band B (r) is equal to the Leray number of the clique complex of the graph [GAMMA].

Theorem 5.13 Let [GAMMA] = (V, E) be a finite graph and k a commutative ring with unit. Then, for W [??] U [??] V and n [greater than or equal to] 1, we have

[Ext.sup.n.sub.kB([GAMMA])]([k.sub.U], [k.sub.W]) = [[??].sup.-1](Cliq([GAMMA][U\W]), k).

Proof: We present here the proof of the special case W = 0 and U = V (it turns out that the general case reduces to this case). The maximal elements of B([GAMMA])\{1} are the elements of V. The commutation graph for this set is exactly [GAMMA]. Since B([GAMMA]) is a geometric left regular band, we conclude [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is homotopy equivalent to Cliq([GAMMA]) by Theorem 5.8. The theorem now follows from Theorem 4.1.

Our first corollary characterizes the free partially commutative left regular bands with a hereditary k-algebra. A graph is said to be chordal if it contains no induced cycle of length greater than 3. It is known that [L.sub.k](K) [less than or equal to] 1 if and only if K is the clique complex of a chordal graph, cf. [23, 30, 22].

Corollary 5.14 If k is afield and [GAMMA] a finite graph, then the global dimension of kB([GAMMA]) is the k-Leray number [L.sub.k](Cliq([GAMMA])). In particular, kB([GAMMA]) is hereditary if and only if [GAMMA] is a chordal graph.

Our next corollary computes the quiver of the algebra of a free partially commutative left regular band.

Corollary 5.15 Let [GAMMA] = (V, E) be a finite graph. The quiver of kB([GAMMA]) has vertex set the power set of V. If U [??] W, then the number of arrows from U to W is one less than the number of connected components of [GAMMA][U\W]. There are no other arrows.

It is easy to see that if r is triangle-free, that is, has no 3-element cliques, then Cliq([GAMMA]) = [GAMMA] and so [L.sub.k](Cliq([GAMMA])) = 2 unless r is a forest (in which case [GAMMA] is chordal). This provides a natural infinite family of finite dimensional algebras of global dimension 2.

5.9 CW left regular bands and minimal projective resolutions

In this last section, we indicate how one can use topological properties of the R-poset of a left regular band B to construct minimal projective resolutions of the modules [k.sub.X] (recall that these are all the simple kB-modules when k is a field, cf. [section] 4).

For this section, we assume that B is a finite left regular band, but allow it to be a semigroup. To simplify notation below, we write [B.sub.[greater than or equal to]X] for B[X, [??]], which we call the contraction of B to X (it corresponds to the usual notion of contraction in hyperplane and oriented matroid theory). We say that B is connected if each [DELTA]([B.sub.[greater than or equal to]X]) is connected; this is automatic if B is a monoid since 1 is a greatest element and hence [DELTA]([B.sub.[greater than or equal to]X]) is in fact contractible. In [25] it is proved using Theorem 4.1 that kB is unital if and only if B is connected and, moreover, the [DELTA]([B.sub.[greater than or equal to]X]) are all acyclic in this case.

Theorem 5.16 Let B be a connected left regular band and k a commutative ring with unit. Then the augmented simplicial chain complex [C.sub.*](A([B.sub.[greater than or equal to]X]); k) [??] [k.sub.X] is a kB- projective resolution.

Notice that [C.sub.0]([DELTA]([B.sub.[greater than or equal to]X]); k) = [kB.sub.[greater than or equal to]X] and hence this resolution is almost never minimal. We can improve upon this to get a minimal resolution by taking advantage of the fact that the R-posets of many of the examples we have been discussing have very nice topology. For instance, for real and complex hyperplane face monoids, the subposets B[X, Y) are the face posets of spheres (see [section][section] 5.3-5.4).

Following [5], we say that a poset P is a CWposet if it is the face poset of a finite regular CW complex; we denote the associated CW complex by [summation](P).

Motivated by the many examples, we formulate the following definition. We say that a left regular band B is a CW left regular band if [B.sub.[greater than or equal to]X] is a connected CW poset for all X [member of] [LAMBDA](B). For example, the set of faces of a central or affine hyperplane arrangement or the set of covectors of an oriented matroid (possibly affine) is a CW left regular band. The face poset of a CAT(0) cube complex [31, 15] also admits a CW left regular band structure. Tree space [4], sometimes called the tropical Grassmannian, is an example of a CAT(0) cube complex of combinatorial interest.

The enumerative combinatorics of a CW left regular band is like that of a hyperplane arrangement or an oriented matroid. The support semilattice is Cohen-Macaulay and the f-vector is determined by the support semilattice via an analogue of Zaslavsky's theorem. See [25] for details.

Theorem 5.17 Let B be a finite CW left regular band, X [member of] [LAMBDA](B) and let k be afield. Then the augmented cellular chain complex [C.sub.*](E([B.sub.[greater than or equal to]X]); k) [right arrow] [k.sub.X] is the minimal projective resolution of [k.sub.[greater than or equal to]X].

In particular, this applies to the case where B is the face monoid of a (central or affine) real or complex hyperplane arrangement, the set of covectors of an oriented matroid or oriented interval greedoid, or the face monoid of a CAT(0) cube complex.

The key ingredient in the proof of Theorem 5.17 is that if B is a CW left regular band, then B acts on the CW complex [summation](B). Since [summation](B) is acyclic, its augmented chain complex becomes an acyclic chain complex of kB-modules, which turn out to be projective.

For CW left regular bands, we can also prove that kB is a Koszul algebra, identify its Koszul dual algebra and its Ext-algebra and describe a presentation by quiver with relations. Below, [Inc.sub.k](P) denotes the incidence algebra of a poset P over the ring k. The full details are presented in [25].

Theorem 5.18 Let B be a finite CW left regular band and let k be afield. Then kB is a Koszul algebra, its Koszul dual algebra is [kB.sup.!] [congruent to] [Inc.sub.k]([LAMBDA][(L).sup.op]) and its Ext-algebra is Ext(kB) [congruent to] [Inc.sub.k]([LAMBDA](L)).

Acknowledgements

The first author wishes to warmly thank the Center for Algorithmic and Interactive Scientific Software, CCNY, CUNY for inviting him to be a Visiting Professor during part of the research of this paper. The second author was supported in part by NSERC and FRQNT. The third author was supported in part by NSERC. The first and third authors' research was supported by Grant No. 2012080 from the United States-Israel Binational Science Foundation (BSF). Some of the research of this paper was done while the third author was at the School of Mathematics and Statistics of Carleton University. Finally, the authors really appreciate the thoroughness, care, and thoughtful comments from the referees.

References

[1] I. Assem, D. Simson, and A. Skowronski. Elements of the representation theory of associative algebras. Vol. 1, volume 65 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 2006.

[2] C. A. Athanasiadis and P. Diaconis. Functions of random walks on hyperplane arrangements. Adv. inAppl. Math., 45(3):410-437, 2010.

[3] P. Bidigare, P. Hanlon, and D. Rockmore. A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J., 99(1):135-174, 1999.

[4] L. J. Billera, S. P. Holmes, and K. Vogtmann. Geometry of the space of phylogenetic trees. Adv. in Appl. Math., 27(4):733-767, 2001.

[5] A. Bjorner. Posets, regular CW complexes and Bruhat order. European J. Combin., 5(1):7-16, 1984.

[6] A. Bjorner. Topological methods. In Handbook of combinatorics, Vol. 1, 2, pages 1819-1872. Elsevier, Amsterdam, 1995.

[7] A. Bjorner. Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries. In Building bridges, volume 19 of Bolyai Soc. Math. Stud., pages 165-203. Springer, Berlin, 2008.

[8] A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, second edition, 1999.

[9] A. Bjorner and G. M. Ziegler. Combinatorial stratification of complex arrangements. J. Amer. Math. Soc., 5(1):105-149, 1992.

[10] K. Bongartz. Algebras and quadratic forms. J. London Math. Soc. (2), 28(3):461-469, 1983.

[11] K. S. Brown. Semigroups, rings, and Markov chains. J. Theoret. Probab., 13(3):871-938, 2000.

[12] K. S. Brown. Semigroup and ring theoretical methods in probability. In Representations of finite dimensional algebras and related topics in Lie theory and geometry, volume 40 of Fields Inst. Commun., pages 3-26. Amer. Math. Soc., Providence, RI, 2004.

[13] K. S. Brown and P. Diaconis. Random walks and hyperplane arrangements. Ann. Probab., 26(4):1813-1854, 1998.

[14] P. Cartier and D. Foata. Problemes combinatoires de commutation et rearrangements. Lecture Notes in Mathematics, No. 85. Springer-Verlag, Berlin, 1969.

[15] V. Chepoi. Graphs of some CAT(0) complexes. Adv. in Appl. Math., 24(2):125-179, 2000.

[16] F. Chung and R. Graham. Edge flipping in graphs. Adv. in Appl. Math., 48(1):37-63, 2012.

[17] A. H. Clifford. Semigroups admitting relative inverses. Ann. of Math. (2), 42:1037-1049, 1941.

[18] V. Diekert and G. Rozenberg, editors. The book of traces. World Scientific Publishing Co. Inc., River Edge, NJ, 1995.

[19] J. A. Green. On the structure of semigroups. Ann. of Math. (2), 54:163-172, 1951.

[20] G. Kalai and R. Meshulam. Intersections of Leray complexes and regularity of monomial ideals. J. Combin. Theory Ser A, 113(7):1586-1592, 2006.

[21] G. Kalai and R. Meshulam. Leray numbers of projections and a topological Helly-type theorem. J. Topol., 1(3):551-556, 2008.

[22] C. G. Lekkerkerker and J. C. Boland. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45-64, 1962/1963.

[23] S. Margolis, F. Saliola, and B. Steinberg. Combinatorial topology and the global dimension of algebras arising in combinatorics. To appear in J. Eur. Math. Soc. (JEMS). arXiv:12 05.1159.

[24] S. Margolis, F. Saliola, and B. Steinberg. Semigroups embeddable in hyperplane face monoids. Semigroup Forum, 2013. arXiv:1212.6683.

[25] S. Margolis, F. Saliola, and B. Steinberg. Cell complexes and projective resolutions for left regular bands, 2014. In preparation.

[26] G.-C. Rota. On the foundations of combinatorial theory. I. Theory of Mobius functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2:340-368 (1964), 1964.

[27] F. V. Saliola. The quiver of the semigroup algebra of a left regular band. Internat. J. Algebra Comput., 17(8):1593-1610, 2007.

[28] F. V. Saliola. The face semigroup algebra of a hyperplane arrangement. Canad. J. Math., 61(4):904929, 2009.

[29] M. L. Wachs. Poset topology: tools and applications. In Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pages 497-615. Amer. Math. Soc., Providence, RI, 2007.

[30] G. Wegner. d-collapsing and nerves of families of convex sets. Arch. Math. (Basel), 26:317-321, 1975.

[31] D. T. Wise. From riches to raags: 3-manifolds, right-angled Artin groups, and cubical geometry, volume 117 of CBMS Regional Conference Series in Mathematics. Published by the AMS, 2012.

Stuart Margolis (1) * Franco Saliola (2) ([dagger]) Benjamin Steinberg (3) ([double dagger])

(1) Department of Mathematics, Bar Han University, Israel

(2) Laboratoire de Combinatoire et d'informatique Mathematique (LaCIM), UQAM, Canada

(3) City College of New York, USA

* Email: margolis@math.biu.ac.il.

([dagger]) Email: saliola.franco@uqam.ca.

([double dagger]) Email: bsteinberg@ccny.cuny.edu.
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Margolis, Stuart; Saliola, Franco; Steinberg, Benjamin
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2014
Words:6514
Previous Article:A generalization of the carries process.
Next Article:On the H-triangle of generalised nonnesting partitions.
Topics:

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