The theory developed here provides tools for the study of the structure of partially commutative groups, their universal theory and automorphism groups

S e MR

СИБИРСКИЕ ЭЛЕКТРОННЫЕ МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ

Siberian Electronic Mathematical Reports

http://semr.math.nsc.ru

Том 5, стр. 151–176 (2008) УДК 512.54, 519.17

MSC 05C25, 20E15

ORTHOGONAL SYSTEMS IN FINITE GRAPHS

A. J. DUNCAN, I. V. KAZACHKOV, V. N. REMESLENNIKOV

Abstract. To a finite graph there corresponds a free partially commu- tative group: with the given graph as commutation graph. In this paper we construct an orthogonality theory for graphs and their corresponding free partially commutative groups. The theory developed here provides tools for the study of the structure of partially commutative groups, their universal theory and automorphism groups. In particular the theory is applied in this paper to the centraliser lattice of such groups.

Glossary of Notation.

Γ — a finite undirected graph with vertex setX Γ1⊕Γ2 — the join of graphsΓ1 andΓ2

CG(S) — the centraliser of a a subsetS ofG C(G) — the set of centralisers of a groupG

GorG(Γ) — the (free) partially commutative group with underlying graph Γ

lg(w) — the length of a geodesic wordw^′ such thatw=Gw^′ d(x, y) — the distance fromxtoy,x, y∈Γ

O^Z(Y) — the orthogonal complement ofY inZ, i.e.{u∈Z|d(u, y)≤

≤1, for ally ∈Y}

Y^⊥ — the orthogonal complement ofY inX,O^X(Y)

cl^Z(Y) — the closure ofY inZ with respect to O^Z(Y), i.e. cl^Z(Y) =

=O^Z(O^Z(Y))

cl(Y) — the closure ofY inX, i.e.cl(Y) =Y^⊥⊥

Duncan, A. J., Kazachkov, I. V., Remeslennikov, V. N., Centraliser Dimension and Universal Classes of Groups.

c

2008 Duncan A.J., Kazachkov I.V., Remeslennikov V.N.

Research was carried out with the support of EPSRC grant GR/S71200, “Algebraic geometry over groups and algorithms for Artin groups”.

Received March, 1, 2008, published March, 31, 2008.

151

L(Γ)orL — the lattice of closed sets ofΓ

X — the setX∪ {t}

Γ — the graph(X, E(Γ)∪Et),Et={(t, x)|x∈Jt},Jt⊆X L — the lattice of closed sets,L(Γ), ofΓ

Lt — {Y ⊆X |Y =C∩Jt, whereC∈L}

L˜ — the setL∪Lt

h(L) — the height of a latticeL

Y ∼⊥Z — Y, Z ⊆X are⊥-equivalent in X, that isY^⊥=Z^⊥

acl(S) — the Abelian closure of a simplexS, that is the union ofT ⊆X such thatS∼⊥T

Y ∼oZ — subsetsY, Z⊆X areo-equivalent, i.e.Y^⊥rY =Z^⊥rZ fcl(A) — the free-closure of a free co-simplexA, that is the union of all

free co-simplexesB such thatA∼oB

[x]⊥ — the⊥-equivalence class ofx, that is{y∈X | x∼⊥y}

[x]o — theo-equivalence class ofx, that is{y∈X | x∼oy}

x∼y — x, y∈X are equivalent, i.e. eitherx∼⊥y orx∼oy [x] — the equivalence class ofxwith respect to ∼

Γ^c — the compression of the graphΓ Introduction

This paper is a continuation of a series of papers [4, 5] where the authors develop the theory of free partially commutative groups.

Free partially commutative groups arise in many branches of mathematics and computer science and consequently are known by a variety of names: semifree groups, graph groups, right-angled Artin groups, trace groups, locally free groups.

We refer the reader to [2], [9] and references there for a survey of these groups, which we shall refer to here as partially commutative groups.

The analysis of proofs of results on partially commutative groups shows that these rely heavily upon two main ideas: divisibility and orthogonality. The divis- ibility theory of partially commutative groups has been formalised in [9] and is a convenient tool for solving major algorithmic problems. The idea of considering or- thogonal complements of subsets of vertices of the underlying graph of a partially commutative implicitly occurs in many papers, see for instance, [14, 12] and also [11] pp. 650-651. In this paper we formalise this idea and establish the main results of orthogonality theory for graphs.

Definition. Let G(Γ) be the partially commutative group with underlying graph Γ = (X, E). For a vertex x ∈ X we define x^⊥ to be the set of all vertices of Γ connected withx. For a subsetY ⊆X we define

Y^⊥= \

y∈Y

y^⊥.

Let L(Γ)be the set of all subsetsZ of X of the formY^⊥ for some Y ⊆X. We call L(Γ)the lattice of closed sets of Γ.

The importance of the lattice of closed setsL(Γ)for the theory of partially com- mutative groups is a consequence of the the fact that the latticeL(Γ)is isomorphic

to the lattice of parabolic centralisers (see Section 1) of G(Γ) which, in turn, is crucial for study of the groupG(Γ)itself and its automorphism groupAut(G(Γ)).

The main problem that we consider in this paper is how the lattice of closed set behaves when one joins a vertexv to the graphΓto form a new graphΓ. Naturally¯ this depends on which vertices of Γ are joined to v. In particular, we prove that the latticesL=L(Γ)andL=L(Γ)are isomorphic if and only ifv is joined to the orthogonal complement of a simplexS⊂X; see Theorem 2.38.

Moreover, we prove that the height h(L) of the extended lattice L is h(L) = h(L) +m, wherem= 0,1 or2, see Theorem 2.28.

In Sections 2.7 and 2.10 we introduce operations of free and Abelian inflation and deflation on graphs and prove that the lattice of closed setsLbehaves nicely under these operations. We then introduce the notion of compression of a graphΓwhich plays an important role in the study of partially commutative groups and prove that the lattices of closed sets for the graph Γ and its compression are closely related.

The compression of a graph allows us to give a decomposition of the automorphism group of the graph as a semi-direct product of the automorphism group of the compression with a direct sum of symmetric groups.

The results of the current paper play a key role in two papers of authors which are currently under preparation: one on the structure of lattices of centralisers of a given partially commutative group G, the other on the structure of the automorphism groupAut(G), [7, 8].

A major part of our research on partially commutative groups, [4, 5, 6, 7, 8] was carried out while the second and the third authors were visiting the University of Newcastle Upon Tyne, thanks to the support of the EPSRC grants EP/D065275/1 and GR/S61900/01.

1. Preliminaries

1.1. Graphs. Graph will mean undirected, finite graph throughout this paper. If xand y are vertices of a graph then we define thedistance d(x, y)from xtoy to be the minimum of the lengths of all paths from x to y in Γ. A subgraph S of a graphΓis called afullsubgraph if verticesaandbofSare joined by an edge ofS whenever they are joined by an edge ofΓ.

Let Γ be a graph with V(Γ) =X. A subset Y of X is called a simplex if the full subgraph of Γwith vertices Y is isomorphic to a complete graph. A maximal simplex is called a clique. A subset Y of X is called a free co-simplex if the full subgraph ofΓwith verticesY is isomorphic to the null graph. The reason why the word “free” is necessary here will become apparent later (see Section 2.10).

LetΓi be a graph with vertex set Xi, fori = 1,2. The join Γ1⊕Γ2 ofΓ1 and Γ2 is the graph with vertex set the disjoint union X1⊔X2and edge set consisting of all the edges ofΓi, fori= 1and2 and an edge joiningx1 to x2 for allx1 ∈X1

andx2∈X2.

1.2. Lattices. Let P be a partially ordered set with order relation ≤. Then P is said to be a lattice if every pair of elements of P has a unique infimum and a unique supremum. We usually writes∧tands∨tfor the infimum and supremum, respectively, ofsandt.

A lattice is said to beboundedif it has both a minimum and a maximum element.

Anascending chainin a lattice is a sequence of elements a0, a1, . . . such thatai<

ai+1. Thelengthof a finite chaina0 <· · ·< ak is said to bek.Descending chains

are defined analogously. A lattice may be bounded and have infinite ascending or descending chains (or both). Theheightof a latticeLis defined to be the maximum of the lengths of all chains inL, if it exists, and∞otherwise.

A homomorphism of partially ordered sets is a map from one partially ordered set to another which preserves the order relation. If P and Q are lattices then a homomorphism of partially ordered sets f :P → Qis called a homomorphism of latticesiff(s∨t) =f(s)∨f(t)ands∧t=f(s)∧f(t), for alls, t∈P. For further details on lattices we refer the reader to [1].

1.3. Centraliser Lattices. IfS is a subset of a groupGthen the centraliser ofS inGisCG(S) ={g∈G:gs=sg, for alls∈S}. We writeC(S)instead of CG(S) when the meaning is clear. Let C(G)denote the set of centralisers of a group G.

The relation of inclusion then defines a partial order ‘≤’ on C(G). We define the infimum of a pair of elements ofC(G)in the obvious way as:

C(M1)∧C(M2) =C(M1)∩C(M2) =C(M1∪M2).

Moreover the supremumC(M1)∨C(M2)of elementsC(M1)andC(M2)ofC(G)may be defined to be the intersection of all centralisers containing C(M1) andC(M2).

ThenC(M1)∨C(M2)is minimal among centralisers containingC(M1)andC(M2).

These definitions makeC(G)into a lattice, called the centraliser latticeofG. This lattice is bounded as it has a greatest element, G = C(1), and a least element, Z(G), the centre ofG. Lattices of centralisers have been extensively studied; a brief survey of results can be found in [4].

Thecentraliser dimension of a group Gis defined to be the height of the cen- traliser lattice ofGand is denotedcdim(G). Centralisers have the properties that, for all subsetsSandT ofG, ifS ⊆T thenC(S)≥C(T)andC(C(C(S))) =C(S).

Therefore if C1 < C2 <· · · is an ascending chain then· · ·> C(C2)> C(C1)is a descending chain and both chains are either infinite or of the same length. Thus cdim(G)is the maximum of the lengths of descending chains of centralisers in G, if such a maximum exists, and is infinite otherwise.

1.4. Partially Commutative Groups. Let Γ be a finite, undirected, simple graph. LetX =V(Γ)be the set of vertices ofΓand letF(X)be the free group on X. For elements g, hof a group we denote the commutator g⁻¹h⁻¹gh ofg andh by[g, h]. Let

R={[xi, xj]∈F(X)|xi, xj∈X and there is an edge fromxi toxj inΓ}.

We define thepartially commutative group with(commutation) graph Γto be the group G(Γ) with presentationhX |Ri. (Note that these are the groups which are called finitely generated free partially commutative groups in [3].)

LetΓ be a simple graph,G=G(Γ)and letw∈G. Denote bylg(w)the length of ageodesicword in X∪X⁻¹ that represents the elementw∈G: that is a word of minimal length amongst those representing w. We say that w∈G iscyclically minimal if and only if

lg(g⁻¹wg)≥lg(w) for everyg∈G.

The centraliser dimension of partially commutative groups is finite because all partially commutative groups are linear [10] and all linear groups have finite cen- traliser dimension, [13]. In [5] it is shown that the centraliser dimension of a partially

commutative group is easy to calculate and depends only on the centralisers of sub- sets ofX. IfY ⊆X then we call C(Y) a canonical paraboliccentraliser. It is not hard to prove that the intersection of two canonical parabolic centralisers is again a canonical parabolic centraliser and, as shown in [5], the supremum, in C(G), of two canonical parabolic centralisers is also a canonical parabolic centraliser. Hence the setC(X;G)of canonical parabolic centralisers forms a sublattice ofC(G). In [5, Theorem 3.3] it is shown that the centraliser dimension ofGis equal to the height of the latticeC(X;G). In [6] we give a short proof of this fact using the methods developed in this paper and give a characterisation of centralisers of arbitrary sub- sets of a partially commutative group. Moreover in [7, 8] we use these tools to give a description of the automorphism group of a partially commutative group.

2. The Lattice of Closed Subsets of a Graph

2.1. Orthogonal Systems, Closure and Closed Sets. As before letΓ be a fi- nite, undirected, simple graph, with vertices X, and letG=G(Γ)be the partially commutative group defined by Γ. Given vertices x, yin the same connected com- ponent ofΓ we define the distance d(x, y) from xto y to be the minimum of the lengths of paths fromxtoy. Ifxandy are in distinct connected components then we defined(x, y) =∞.

LetY andZ be subsets ofX. We define theorthogonal complement ofY in Z to be

O^Z(Y) ={u∈Z|d(u, y)≤1, for ally∈Y}.

By convention we set O^Z(∅) =Z. IfZ =X we call O^X(Y)the orthogonal com- plement ofY, and if no ambiguity arises then we shall sometimes writeY^⊥instead of O^X(Y). Also, if every vertex of Z is either in Y or is joined by an edge of Γ to every vertex of Y then we write [Y, Z] = 1. Thus [Y, Z] = 1 if and only if Z ⊆ O^X(Y) if and only if every element of Y commutes with every element of Z in the group G. For future reference we record some of the basic properties of orthogonal complements in the next lemma.

Lemma 2.1. Let Y,Y1,Y2 andZ be subsets ofX.

(1) IfY ⊆Z thenY ⊆ O^Z(O^Z(Y)).

(2) IfY ⊆Z thenO^Z(Y) =O^Z(O^Z(O^Z(Y))).

(3) IfY1⊆Y2 thenO^Z(Y2)⊆ O^Z(Y1).

(4) O^Z(Y1∩Y2)⊇ O^Z(Y1)∪ O^Z(Y2).

(5) O^Z(Y1∪Y2) =O^Z(Y1)∩ O^Z(Y2).

(6) Y is a simplex if and only ifY ⊆Y^⊥. (7) Y is a clique if and only ifY =Y^⊥.

In particular from 1 and 2 we have Y ⊆Y^⊥⊥ and Y^⊥ =Y^⊥⊥⊥, where we write Y^⊥⊥ for(Y^⊥)^⊥.

Proof. If y ∈ Y ⊆ Z then, for all u ∈ O^Z(Y), we have d(u, y) ≤ 1. Hence y ∈ O^Z(O^Z(Y)) and 1 follows. Statement 3 follows directly from the definition of orthogonal complement. Statement 2 follows from 1 and 3. Statement 4 follows from 3. To see 5 suppose first that Z =X. It follows from 3 that O^X(Y1∪Y2)⊆ O^X(Y1)∩ O^X(Y2). From 4 and 1 we haveO^X(O^X(Y1)∩ O^X(Y2))⊇Y1∪Y2. Hence, from 1 and 3, O^X(Y1)∩ O^X(Y2)⊆ O^X(O^X(O^X(Y1)∩ O^X(Y2))) ⊆ O^X(Y1∪Y2), so 5 holds in this case. In general, O^Z(Y1∪Y2) = O^X(Y1∪Y2)∩Z =O^X(Y1)∩ O^X(Y2)∩Z =O^Z(Y1)∩ O^Z(Y2), as required. If Y is a simplex and y ∈ Y then

a b c d

Figure 2.1. A path graph

d(y, z) = 1, for all z ∈ Y, z 6= y. Hence Y ⊂ Y^⊥. Conversely, if Y ⊆ Y^⊥ and y, z∈Y thend(y, z)≤1, soY is a simplex. Therefore 6 holds. IfY is a clique and x∈Y^⊥\Y thenY∪ {x}is a simplex, contrary to maximality ofY. Hence, using 6, Y =Y^⊥. Conversely, ifY =Y^⊥, then Y is a simplex and, by a similar argument, there is no simplex strictly containingY. Hence 7 holds.

Example 2.2. (1) In general the inclusions of Lemma 2.1 are strict. For in- stance, take Γ to be the graph of Figure 2.1, let Y1 = {a, c} and Y2 = {b, c, d}. Then Y₁^⊥ ={b}, Y₂^⊥ ={c} and (Y1∩Y2)^⊥ ={b, c, d}: so (Y1∩ Y2)^⊥6=Y₁^⊥∪Y₂^⊥. MoreoverY₁^⊥⊥={a, b, c} 6=Y1.

(2) The subgroup G(X^⊥)is the centre of the groupG=G(Γ).

(3) If X = X1 ⊔X2 is a disjoint union of X1 and X2 and Γ is the direct sum of graphsΓ(X1)and Γ(X2)thenG=G(X1)×G(X2). If O^X1(X1) = O^X2(X2) =∅ then the groupsG(Xi), i = 1,2 have trivial centre. In this caseO^X(X1) =X2 andO^X(X2) =X1.

The connection between orthogonal complements and centralisers is made ex- plicit in the following lemma.

Lemma 2.3. Let G=G(Γ) andY ⊆X. ThenCG(Y) =G(Y^⊥).

Proof.If x∈X then CG(x)⊇G(x^⊥). From [9, Lemma 2.4] we also haveCG(x)⊆ G(x^⊥). HenceCG(Y) =∩y∈YCG(y) =∩y∈YG(y^⊥) =G(∩y∈Yy^⊥) =G(Y^⊥).

For subsets Y and Z of X we define the closure of Y in Z to be cl^Z(Y) = O^ZO^Z(Y). When Z = X we write cl(Y) for cl^X(Y). The closure operator in Γ satisfies the following properties.

Lemma 2.4. Let Y,Y1,Y2 andZ be subsets ofX.

(1) Y ⊆cl(Y).

(2) cl(Y^⊥) =Y^⊥. (3) cl(cl(Y)) = cl(Y).

(4) IfY1⊆Y2 thencl(Y1)⊆cl(Y2).

(5) cl(Y1∩Y2)⊆cl(Y1)∩cl(Y2)andcl(Y1)∪cl(Y2)⊆cl(Y1∪Y2).

(6) IfZ= cl(Y) thenZ=U^⊥, for someU ⊂X, and thencl(U) =Z^⊥=Y^⊥. (7) Ifcl(Y1) = cl(Y2) thenY₁^⊥=Y₂^⊥.

(8) Y is a simplex if and only ifcl(Y)is a simplex if and only ifcl(Y)⊆Y^⊥. (9) IfY1⊆Y2 thencl(cl(Y1)∩Y2) = cl(Y1).

(10) cl(cl(Y1)∪cl(Y2)) = cl(Y1∪Y2).

(11) cl(cl(Y1)∩Y2)∩Y2= cl(Y1)∩Y2.

Proof. Statements 1 and 2 are restatements of Lemma 2.1, 1 and 2, respectively.

To see 3 apply the operatorO^X to both sides of 2. Statement 4 is a consequence of Lemma 2.1.3. Statement 5 follows from 4. If Z = cl(Y) then Z = U^⊥, where U =Y^⊥. If Z =U^⊥ then cl(U) = U^⊥⊥ =Z^⊥ = (cl(Y))^⊥ =Y^⊥, using Lemma 2.1.2. Hence 6 holds. To see 7 apply the operatorO^Xto bothcl(Y1)andcl(Y2)and

use Lemma 2.1.2. For 8, if cl(Y) is a simplex thencl(Y) ⊆cl(Y)^⊥, from Lemma 2.1.6, so from 1 and Lemma 2.1.2 cl(Y) ⊆ Y^⊥. If cl(Y) ⊆Y^⊥ then, from 1 and Lemma 2.1.6,Y ⊆Y^⊥ soY is a simplex, andcl(Y)⊆cl(Y^⊥) = cl(Y)^⊥, socl(Y)is a simplex.Y^⊥⊥⊆(Y^⊥⊥)^⊥ =Y^⊥ so Y ⊆Y^⊥⊥ ⊆Y^⊥; andY is a simplex. In the setting of 9 we have, from 1,Y1 ⊆cl(Y1)∩Y2, socl(Y1)⊆cl(cl(Y1)∩Y2). On the other hand cl(Y1)∩Y2 ⊆cl(Y1)so, from 3 and 4,cl(cl(Y1)∩Y2)⊆cl(Y1). To see 10 use the second part of 5 and then 3 to obtain cl(cl(Y1)∪cl(Y2))⊆cl(Y1∪Y2).

For the opposite inclusion use 1 to obtain Y1∪Y2 ⊆ cl(Y1)∪cl(Y2) and then 4 implies thatcl(Y1∪Y2)⊆cl(cl(Y1)∪cl(Y2)), as required. For 11 first note that 1 implies thatcl(Y1)∩Y2⊆cl(cl(Y1)∩Y2)∩Y2. Alsocl(Y1)∩Y2⊆cl(Y1)so 4 and 3 imply thatcl(cl(Y1)∩Y2)⊆cl(Y1). On intersection withY2this gives the inclusion

required to complete the proof.

Example 2.5. (1) Ifx∈X andY = cl(x) =x^⊥⊥thenY is a simplex.

(2) In terms of the group Gthe subsetY ofX is a simplex if and only ifG(Y) is Abelian. AsCG(Z) =G(Z^⊥), for any subsetZofX, Lemma 2.1.6 states thatG(Y)is Abelian if and only ifG(Y)⊆CG(Y). The content of Lemma 2.4.8 is thatG(Y)is Abelian if and only ifC_G²(Y)is Abelian if and only if C_G²(Y)⊆CG(Y).

Definition 2.6. A subsetY of X is calledclosed (with respect to Γ)ifY = cl(Y).

Denote by L(Γ)the set of all closed subsets of X.

We list some basic properties ofL(Γ).

Lemma 2.7. Let Y be a subset ofX. The following hold.

(1) cl(Y)∈L(Γ).

(2) X is the unique maximal element ofL(Γ).

(3) Y is closed if and only ifY =O^X(U), for someU ∈L(Γ).

(4) O^X(X)is the unique minimal element of L(Γ).

(5) IfY1, Y2∈L(Γ) thenY1∩Y2∈L(Γ).

Proof.

(1) This follows from Lemma 2.4.3.

(2) This is clear, given the previous statement and the fact thatX ⊆cl(X).

(3) It follows, from Lemma 2.4, 2 and 6, that Y ∈ L(Γ) if and only if Y = O^X(U), for some subset U of X. If Y is closed and Y = O^X(U) then Y = cl(Y) =O^X(cl(U))and, ascl(U)is closed, the result follows.

(4) From the previous statement it follows that O^X(X)∈L(Γ). If Y ∈ L(Γ) then Y = O^X(U), for some U ⊆ X. From Lemma 2.1 then O^X(X) ⊆ O^X(U) =Y, as required.

(5) From Lemma 2.4, 1 and 5, we have

Y1∩Y2⊆cl(Y1∩Y2)⊆cl(Y1)∩cl(Y2) =Y1∩Y2,

the last equality holding by definition of closed set. Therefore Y1∩Y2 = cl(Y1∩Y2).

The relation Y1 ⊆ Y2 defines a partial order on the set L(Γ). As the closure operatorclis inclusion preserving and maps arbitrary subsets ofX into closed sets we can makeL(Γ)into a lattice by defining the the infimum Y1∧Y2 ofY1 and Y2

byY1∧Y2= cl(Y1∩Y2) =Y1∩Y2 and the supremumY1∨Y2= cl(Y1∪Y2).

Proposition 2.8. The setL(Γ)with operations∧and∨above is a complete lattice.

Proof.As we have seenL(Γ)is a lattice. From Lemma 2.7 it has maximum element

X and minimum elementO^X(X), so is complete.

Proposition 2.9. The operator O^X maps L(Γ) to itself and is a lattice anti- automorphism.

Proof. If Y ∈ L(Γ) then, from Lemma 2.7, O^X(Y) ∈ L(Γ); so O^X maps L(Γ) to itself. From Lemma 2.1 O^X is inclusion reversing. Moreover, for Y ∈ L(Γ) we have O^X(O^X(Y)) =Y; so the restriction ofO^X to L(Γ)is a bijection. Hence this

restriction is a lattice anti-automorphism.

IfZ ⊆X andΓZ is the full subgraph of Γ with vertex set Z then, by abuse of notation, we writeL(Z)forL(ΓZ). As long as it is clear thatΓis fixed this should cause no confusion. We have O^Z(Y) =O^X(Y)∩Z so L(Z)consists of subsets Y ofZ such thatY = cl^Z(Y) =O^X(O^X(Y)∩Z)∩Z.

2.2. Disconnected Graphs and Joins of Graphs. Now suppose that X is a disjoint union X =X1⊔X2, where X1 and X2 are non-empty, andΓ = Γ(X1)⊔ Γ(X2) (that is no edge ofΓ joins a vertex of X1 to a vertex of X2). Write Γi for Γ(Xi),i= 1,2. We wish to describeL(Γ)in terms of the latticesL(Γi). First of all we note the following lemma.

Lemma 2.10. With the hypotheses above, ifU is a non-empty subset of Xi then O^Xi(U) =O^X(U).

Proof. By definition O^Xi(U) ⊆ O^X(U). We have O^X(U) = {x ∈ X|d(u, x) ≤ 1,∀u∈U}. Ifx /∈Xi then, asU 6=∅, there is someu∈U such that d(x, u) =∞.

Hencex∈ O^X(U)impliesx∈Xi, sox∈ O^Xi(U).

The relationship betweenL(Γ)and theL(Γi)is specified by the following propo- sition.

Proposition 2.11. LetΓ = Γ1⊔Γ2, as above.

(1) ∅ ∈L(Γ).

(2) A non-empty setY is in L(Γ)\{X, X1, X2} if and only ifY is in precisely one of L(Γi)\{Xi},i= 1or 2.

(3) IfO^Xi(Xi) =∅ then∅ ∈CS(Γi)andXi ∈/ CS(Γ).

(4) IfO^Xi(Xi)6=∅ then∅∈/ CS(Γi)andXi ∈CS(Γ).

Proof.

(1) AsXi is non-empty it follows that∅=O^X(X), so∅ ∈L(Γ).

(2) Let Y be a non-empty element of L(Γ)\{X, X1, X2}. Then Y = O^X(U), for some subsetU ofX. If U∩Xi 6=∅, for i= 1and2, thenO^X(U) =∅.

Hence U ⊆Xi, for i= 1or 2. IfU =∅ thenY =X, so U 6=∅ and, from Lemma 2.10,Y =O^Xi(U)so is inL(Γi). Note that in this caseY ⊆Xiand is non-empty; so cannot be inL(Γ_j),j6=i. Conversely ifY is a non-empty element ofL(Γi)\{X_i}thenY =O^Xi(U), for someU ⊆Xi. AsY 6=Xiwe haveU 6=∅ and so, from Lemma 2.10 again,Y ∈CS(Γ).

(3) From Lemma 2.7, ∅ ∈ L(Γi). From Lemma 2.10 we have∅ =O^Xi(Xi) = O^X(Xi). If Xi ∈ L(Γ) then Xi = O^X(U), for some U ∈ L(Γ). Hence

∅=O^X(Xi) =U which impliesXi=O^X(U) =X, a contradiction.

(4) As O^Xi(Xi) is the minimal element of L(Γi), in this case ∅ ∈/ L(Γi). We have Xi = O^Xi(U), for some U ∈ L(Γi), so U 6= ∅ and U ⊆ Xi. That Xi∈L(Γ)now follows from Lemma 2.10.

LetL=L(Γ),Li=L(Γi)andL^′_i=L(Γi)\{X_i}. Then Figure 2.2 illustrates the composition ofL(Γ)in terms of theL(Γ_i). Now suppose thatΓhas connected com-

X

L^′₂ L^′₁

∅ O^Xi(Xi) =∅,

i= 1,2

X

L1 L^′₂ X1

X₁^⊥

∅ O^X1(X1)6=∅, O^X2(X2) =∅,

X

L1

X1

X₁^⊥

L2

X2

X₂^⊥

∅ O^Xi(Xi)6=∅,

i= 1,2 Figure 2.2. The latticeLof closed sets in a disconnected graph

ponentsΓ1, . . . ,Γm, whereV(Γi) =Xi. Assume thatO^Xi(Xi)6=∅, fori= 1, . . . , r and that O^Xi(Xi) = ∅, for i > r. A straightforward induction using Proposition 2.11 shows that the latticeL(Γ)takes the form shown in Figure 2.3: where we use the obvious extension of the notation introduced above for the latticesL(Γi). We

... ...

X

L1 L^′_r+1

X1

X₁^⊥

Lr L^′_m

Xr

X_r^⊥

∅

Figure 2.3. The lattice L of the graph with connected compo- nentsΓ1, . . . ,Γm.

may often therefore reduce to the study ofL(Γ)whereΓis a connected graph.

Now suppose that X^⊥ 6= ∅ and set X^∗ = X\X^⊥. Let Γ(X^∗) = Γ^∗ the full subgraph ofΓwith vertex setX^∗.

Proposition 2.12. The set O^X∗(X^∗) = ∅ and the lattice L(Γ) is isomorphic to the latticeL(Γ^∗).

Proof.From the definitions it follows thatO^X(X^∗) =O^X(X). ThereforeO^X∗(X^∗) = O^X(X^∗)∩X^∗ = O^X(X)∩ X^∗ = ∅. If Y = O^X(U), where U ∈ L(Γ) then Y\X^⊥ = O^X(U)\O^X(X) = O^X∗(U\O^X(X)). Hence the map φ : Y → Y\X^⊥ mapsL(Γ)toL(Γ^∗).

Clearlyφis inclusion preserving. To see thatφis surjective, note that ifV ⊆X^∗ then O^X∗(V) = C\X^⊥, where C = O^X(V\O^X(X)). Therefore φ is a surjective homomorphism of partially ordered sets. SinceY ∈L(Γ)impliesX^⊥⊆Y it follows thatφis also injective; soφis an isomorphism of lattices.

The setO^X(X)is called thekernel of the graphΓ. Given the proposition above we may restrict to the study of lattices with the trivial kernel.

Now suppose that Γ = Γ(X1)⊕Γ(X2), for some partition X =X1∪X2 ofX (see Section 1.1). LetΓi = Γ(Xi)and letGi=G(Γi),i= 1,2; soG=G1×G2. Proposition 2.13. In the above notation, if Γ = Γ1⊕Γ2 then L(Γ) = L(Γ1)× L(Γ2).

In this case the study of the lattice L(Γ) reduces to the study of L(Γ1) and L(Γ2).

2.3. Adjoining Vertices. We now consider the effect on the lattice of closed sets of the addition toΓ, or removal fromΓ, of a vertex. In particular we shall see how the heights of these lattices are related and how to make restrictions on the way in which the new vertex is added to obtain isomorphism of the two lattices.

We shall see below that if we adjoin a single vertex toΓ then the height of the lattice of closed sets of the new graph is equal toh(L(Γ)) +k, wherek= 0,1or2.

As usualΓ is a graph withV(Γ) =X and edgesE(Γ). Lett be an element not in X and defineX =X ∪ {t}. Let Jtbe a subset of X. DefineΓ to be the graph with verticesX and edgesE(Γ)∪Et, where Etis the setEt={(t, x)|x∈Jt}. Let L=L(Γ)andL=L(Γ).

In order to understand howLandLare related we introduce a lattice intermedi- ate betweenLandL. This will help us to give a simple description of the structure of the latticeL in terms of the latticeL. Let

Lt={Y ⊆X|Y =C∩Jt, where C∈L}.

Now define the set of subsets L˜ ofX to be L˜ =L∪Lt. We shall see that L˜ is a lattice which embeds in the lattice L. Note that if Y ∈ Lt then Y = C∩Jt, for someC∈L, so

Y =Y ∩Jt⊆cl(Y)∩Jt⊆cl(C)∩Jt=C∩Jt=Y.

Hence Y = cl(Y)∩Jtand it follows thatcl(Y)is the minimal element ofLwhich intersects with Jt to give Y, for all Y ∈ Lt. Setting Z = cl(Y) this gives Z = cl(Y) = cl(cl(Y)∩J_t) = cl(Z∩J_t). Also ifY ∈L_t\Lthencl(Y)6=Y = cl(Y)∩J_t, so Z = cl(Y)*Jt. Conversely, given Z ∈L such that Z *Jt andZ = cl(Z∩Jt) thencl(Z∩Jt)6=Z∩Jt, so Z∩Jt∈Lt\L. Therefore

(2.1) Lt\L={Y =Z∩Jt|Z ∈L, Z*JtandZ = cl(Z∩Jt)}.

We define a closure operationicl^X = iclon subsets of X by icl(U) =

cl^X(U), ifU *Jt

cl^X(U)∩Jt, ifU ⊆Jt

, forU ⊆X. Thenicl(U)∈L, for all˜ U ⊆X.

Now assume that Y1 and Y2 are inL˜ and Y1 ⊆ Y2. If Y1 * Jt then icl(Y1) = cl^X(Y1) and icl(Y2) = cl^X(Y2) so icl(Y1) ⊆ icl(Y2). If Y1 ⊆ Jt then icl(Y1) = cl^X(Y1)∩J_t⊆cl^X(Y2)∩J_t⊆icl(Y2). Thereforeiclis an inclusion preserving map from subsets ofX toL. It also follows from the definition and 2.1 that˜ icl(U) =U, for all U ∈ L, so˜ L˜ is a retract ofX. We may therefore make L˜ into a lattice by defining

Y1∧Y2= icl(Y1∩Y2)andY1∨Y2= icl(Y1∪Y2), forY1, Y2∈L.˜

Lemma 2.14. IfU, V ∈L˜ thenU∧V =U∩V and U∨V =

cl(U∪V)∩Jt, if U∪V ⊆Jt

cl(U∪V), otherwise .

Proof.The expression forU∨V is merely a restatement of the definitions. IfU ∈L then icl(U) = cl^X(U). Therefore, for U and V in L we have (in the lattice L)˜ U∧V =U∩V. If either U or V belongs toLtthenU∩V ⊆Jtso

U∧V = cl(U∩V)∩Jt⊆cl(U)∩cl(V)∩Jt=U∩V ⊆cl(U∩V)∩Jt

and the Lemma follows.

Definition 2.15. Define β˜ to be the inclusion map of L into L˜ and γ˜ to be the map fromL˜ toLgiven by ˜γ(Y) = cl^X(Y), for Y ∈L.˜

Lemma 2.16. The mapsβ˜and˜γare homomorphisms of partially ordered sets and

˜

γβ˜= idL. We have β(Y˜ ∧Z) = ˜β(Y)∧β(Z), for all˜ Y, Z ∈L, and γ(U˜ ∨V) =

˜

γ(U)∨γ(V˜ ), for all U, V ∈ L. If˜ U, V ∈ L˜ such that U 6= V and ˜γ(U) = ˜γ(V) then (after interchanging U and V if necessary) U ∈ L\L_t and V ∈ Lt\L and U = cl^X(V).

Proof. The first statement is a direct consequence of the definitions, as is the fact thatβ˜respects the lattice infimum operation. For allU, V ∈L˜ we have

˜

γ(U)∨˜γ(V) = cl(cl(U)∪cl(V)) = cl(U∪V),

from Lemma 2.4.10. IfU∪V *Jtthenγ(U˜ ∨V) = cl cl(U∪V) = cl(U∪V). On the other hand, ifU∪V ⊆Jtthen˜γ(U∨V) = cl(cl(U∪V)∩Jt) = cl(U∪V), using Lemma 2.4.9. Hence˜γ(U)∨γ(V˜ ) = ˜γ(U∨V), for allU, V ∈L.˜

LetU, V ∈L. If˜ U, V ∈L thenγ(U˜ ) = ˜γ(V)impliesU =V. IfU, V ∈Lt then U = cl(U)∩JtandV = cl(V)∩Jtandcl(U) = cl(cl(U)∩Jt) = ˜γ(U)and similarly cl(V) = ˜γ(V). Thereforeγ(U) = ˜˜ γ(V)implies thatU = cl(U)∩J_t= cl(V)∩J_t=V. Therefore, ifU 6=V andγ(U˜ ) = ˜γ(V)then one ofU, V is inL\L_tand the other in Lt\L. Assume then thatU ∈L\L_tandV ∈Lt\L. In this caseU = ˜γ(U) = ˜γ(V) =

cl(cl(V)∩Jt) = cl(V).

In generalβ˜does not preserve supremums and ˜γdoes not preserve infimums.

a c b

e x y f

Figure 2.4. Example 2.17

Example 2.17. In the graph of Figure 2.4 the sets B = {b} and C = {c} are closed. The supremum B ∨C = cl(B ∪C) = {b, c, y} and setting Jt = {b, c}

we have β(B˜ ∨C) = {b, c, y} and β˜(B)∨β(C) = cl({b, c})˜ ∩ {b, c} = {b, c}. In the same graph cl(x) = {a, x, c} and cl(y) = {b, y, c}. Set Jt = {x, y} and then U = cl(x)∩Jt = {x} and V = cl(y)∩Jt = {y} are both elements of Lt. Now U∧V =∅ soγ(U˜ ∧V) = cl(∅) =∅. Howeverγ(U˜ )∧γ(V˜ ) = cl(x)∩cl(y) ={c}.

Next we show that the latticeL˜ is embedded, as a partially ordered set, inL.

Definition 2.18. Let β : ˜L → L and γ : L → L˜ be the maps given by β(Y) = cl^X(Y), for Y ∈L˜ andγ(Z) = icl(Z\{t}), for Z ∈L.

Lemma 2.19. The maps β and γ are homomorphisms of partially ordered sets andγβ= idL˜; soβ is injective andγ is surjective. We have γ(Z) =Z\{t}, for all Z∈L, and

(2.2) β(Y) =

Y ifO^X(Y)*Jt, Y ∪ {t} ifO^X(Y)⊆Jt , for allY ∈L.˜

If Z1 and Z2 are elements of L such that Z1 6=Z2 then γ(Z1) = γ(Z2) if and only if (after interchanging Z1 andZ2 if necessary)t∈Z1 andZ2=Z1\{t} ∈L.

Proof. Since the closure operations inL˜ andL preserve inclusion of sets it follows from the definitions thatβ andγ are homomorphisms of partially ordered sets.

Now letU ∈L. If˜ U *JtthenO^X(U) =O^X(U). On the other hand if U ⊆Jt

thenO^X(U) =O^X(U)∪ {t}. Therefore, ifU *Jtthen β(U) =O^XO^X(U) =

O^XO^X(U), ifO^X(U)*Jt

O^XO^X(U)∪ {t}, ifO^X(U)⊆J_t and (2.2) holds asU *J_timplies that U ∈L. IfU ⊆J_tthen

β(U) =O^X(O^X(U)∪ {t}) =O^X(O^X(U))∩(Jt∪ {t}) so

β(U) =

O^XO^X(U)∩Jt, ifO^X(U)*Jt

(O^XO^X(U)∩Jt)∪ {t}, ifO^X(U)⊆Jt .

In this case, as U ⊆Jt we have O^XO^X(U)∩Jt = cl^X(U)∩Jt =U. Thus, in all cases, (2.2) holds.

Now suppose that Z ∈ L and let Y ∈L such that Z =O^X(Y). Ift ∈Y then Z =O^X(Y)⊆ O^X(t) =Jt∪ {t}. Conversely ifZ⊆Jt∪ {t} thent∈Y =O^X(Z).

Hence Z\{t} ⊆Jtif and only ift ∈Y. SimilarlyY\{t} ⊆Jtif and only ift ∈Z.

To show thatγ(Z) =Z\{t} we consider various cases.

(1) Suppose that t ∈ Z and that t /∈ Y. Then Y ⊆ Jt and Z = O^X(Y) = O^X(Y)∪ {t}. Therefore Z\{t} = O^X(Y) ∈ L and, since Z\{t} * Jt, it follows thatγ(Z) = icl(Z\{t}) =Z\{t}.

(2) Assume that t∈Z andt∈Y. ThenY ⊆Jt∪ {t} and Z =O^X(Y) =O^X((Y\{t})∪ {t})

=O^X(Y\{t})∩ O^X(t)

= (O^X(Y\{t})∪ {t})∩(Jt∪ {t})

= (O^X(Y\{t})∩Jt)∪ {t}.

ThereforeZ\{t}=O^X(Y\{t})∩Jtand, sinceZ\{t} ⊆Jt, we have, using Lemma 2.4.11, icl(Z\{t}) = cl(O^X(Y\{t})∩Jt)∩Jt =O^X(Y\{t})∩Jt. Thereforeγ(Z) = icl(Z\{t}) =Z\{t}.

(3) Assume that t /∈ Z and t /∈ Y. In this case Z = O^X(Y) ∈ L and, since Z*Jt, it follows thatγ(Z) = cl(Z) =Z =Z\{t}.

(4) Assume that t /∈ Z and t ∈ Y. Since t /∈ Z this means that Z ⊆Jt and γ(Z) = cl(Z)∩Jt. Now

Z=O^X(Y) =O^X(Y\{t})∩(Jt∪ {t})

=O^X(Y\{t})∩Jt∈Lt,

asY\{t}*Jt. HenceZ = cl(Z)∩Jtand so γ(Z) =Z=Z\{t}.

Thusγ(Z) =Z\{t}, for allZ∈L.

Now suppose thatZ1, Z2∈Lsuch that Z1 6=Z2. Suppose thatγ(Z1) =γ(Z2).

Asγ(Z_i) =Z_i\{t}we must have, after interchangingZ1andZ2 if necessary,Z1= Z2∪ {t}; sot∈Z1∈LandZ1\{t} ∈L.

Definition 2.20. Let β:L→Lbe the map given by β(Y) = cl^X(Y), forY ∈L.

Let γ:L→L be the map given byγ(Z) = cl^X(X∩Z), for Z∈L.

Corollary 2.21. We haveβ =ββ˜and γ= ˜γγ. The mapsβ andγ are homomor- phisms of partially ordered sets. ForY ∈L

β(Y) =

Y ifO^X(Y)*Jt, Y ∪ {t} ifO^X(Y)⊆Jt . Moreover γβ= idL,β is injective and γis surjective.

2.4. The height of the extended lattice. In this section we determine the pos- sible differences in height between the latticesLandL. By astrong ascending chain in a partially ordered set L is meant a sequence C0, C1. . . of elements of L such that Ci < Ci+1, for all i ≥ 0. Strong descending chains are defined analogously, replacing< by>. The lengthof a finite strong chain C0, . . . , Cd is d. IfC0, C1. . . is a sequence of elements of L such that Ci ≤ Ci+1, for all i ≥ 0, then we call C0, C1. . .aweakascending chain. Weak descending chains are defined analogously.

Thelength of a weak chainC is the maximum of the lengths of strong chains ob- tained by taking subsequences ofC. We shall from now on use chain to mean either weak or strong chain, if the meaning is clear. We denote the length of a chainCby l(C). LetLandL^′ be partially ordered sets and letφ:L→L^′ be a homomorphism or anti-homomorphism of partially ordered sets. If C is a chain C0, . . . , Cd in L then we denote byφ(C)the chainφ(C0), . . . , φ(Cd), in L^′. Clearly the length ofC is greater than or equal to the length ofφ(C).

Definition 2.22. Theheighth(L)of a latticeLis the length of its maximal chain, if this exists, and is infinite otherwise.

The following is a corollary of Lemmas 2.16 and 2.19 Corollary 2.23. h(L)≤h( ˜L)≤h(L).

Proof. If C is a maximal chain in L then β(C)˜ is a chain in L. As˜ β˜ is injective β(C)˜ has the same length asCand the result follows. The second inequality follows

similarly.

Example 2.24. Let Γ be the graph of Figure 2.1 and let Jt = {a, c}. Then L consists ofX, the orthogonal complements (inX) ofa,b,candd, and also{b, c}= O^X{b, c}, {b} =O^X{a, c},{c}=O^X{b, d} and ∅. Therefore h(L) = 4. L˜ contains in addition the setJtand the set{a}=Jt∩O^X(a). It follows thath( ˜L) = 4as well.

Finally, the maximal proper subsets ofL are the orthogonal complements (in X) ofa,b,candt (asO^X(d)⊆ O^X(c)). The only one of these sets with4 elements is O^X(c). However, the intersection ofO^X(c)with any other proper maximal subset has at most 2 elements. Hence L can have height at most 4. As h( ˜L) = 4it now follows thath(L) =h( ˜L) =h(L) = 4.

Example 2.25. Let Γ be the graph of Figure 2.1 and Γ be the graph obtained by removing vertexc. Then, with t=c we haveX ={a, b, d} and Jt={b, d}. In this case Lconsists of the sets X, O^X(a),O^X(d)and∅, soh(L) = 2. Ltcontains in addition the setsJtandO^X(a)∩Jt={b}. Thus h( ˜L) = 3. Moreover, from the previous example h(L) = 4. (The semibraidgroup on ngenerators is the partially commutative groupGn with presentation

hx1, . . . , xn|[xi, xj] = 1, if|i−j| ≥2i.

The graphs of this example are those ofG3 andG4, see [5] for further details) In fact these two examples illustrate the two extremes in differences of height betweenLandL˜ and betweenL˜ andL: as the following propositions show.

Proposition 2.26. h( ˜L) =h(L) +m, wherem= 0 or1.

Proof.Let

C=Z0<· · ·< Zk

be a strictly ascending chain inL, with˜ k=h( ˜L). Then˜γ(C)is an ascending chain in L. IfZi ∈L for all ithen ˜γ(C) =C, so Lemma 2.23 implies thath( ˜L) =h(L).

Assume then that Zi ∈/ L, for somei, and let r be the smallest integer such that Zr ∈ L, for all i ≥r. Then Zi ⊆Jt, so Zi ∈Lt, for all i ≤r−1. Using Lemma 2.16,˜γ(Zr)<· · ·<γ(Z˜ k)and˜γ(Z0)<· · ·<γ(Z˜ r−1)are strictly ascending chains inL. The length ofγ(C)˜ is therefore at leastk−1 =h( ˜L)−1; soh(L)≥h( ˜L)−1,

and the lemma follows from Lemma 2.23.

Proposition 2.27. h(L) =h( ˜L) +m, wherem= 0 or1.

Proof. LetC=Z0<· · ·< Z_k be a strictly ascending chain in L. As γis inclusion preserving the sequenceγ(C)is ascending. Letrbe the least integer such thatt∈Zi

forr≥i. Then, from Lemma 2.19,

γ(Z0)<· · ·< γ(Zr−1)≤γ(Zr)< γ(Zr+1)<· · ·< γ(Zk),

a b c

d e

f

t Γ1

a b c

d e

f g

h i j

k

l

t

Γ2

Figure 2.5. Examples 2.29 and 2.30

soγ(C)has length at leastk−1.

Theorem 2.28. h(L) =h(L) +m, wherem= 0,1 or2.

The next two examples show that a difference of one between the heights of L andLmay occur and may be due either to a difference in height betweenLandL˜ or betweenL˜ andL.

Example 2.29. LetΓbe the graph obtained by removing vertextfrom the graph Γ = Γ1 of Figure 2.5 and letJt={a, b, c}. Thenh(L) = 4 and h(L) = 5. In this case the height of the latticeL˜ is5, with a maximal chain

X >O^X(d)> Jt>O^X(f)∩Jt>O^X(f)∩Jt∩ O^X(a)>∅.

Example 2.30. LetΓbe the graph obtained by removing vertextfrom the graph Γ = Γ2 of Figure 2.5 and again letJt={a, b, c}. Thenh(L) = 5andh( ˜L) = 5. In this case the maximal chains in the latticeL involve only the verticesg, h, i, j, k, l and the sets ofLtinvolve only verticesa, b, c. Therefore the latticeL˜ has some new chains of length5 but none of length6. However computation shows (see [5]) that h(L) = 6.

2.5. The structure of the extended lattice. Next we use the results of the Section 2.3 to describe the latticeLin terms of the latticeL. We make the following definition. Suppose thatLis a lattice which is a subset of a latticeL^′ and that the partial ordering inLis the restriction of the partial ordering inL^′. Assume thatL contains a subsetS such that there is an isomorphism of partially ordered sets,ρ, fromS to L^′\L. Then we say thatL^′ is obtained fromLbydoublingS alongρ.

Recall from Section 2.3 that if Z ∈L˜ and Z *Jt then Z ∈ L. This, together with (2.1), prompts the following definition.

Definition 2.31. Let

R={Z ∈L|Z˜ *Jtand cl(Z∩Jt) =Z}

and letρbe the map fromR toL˜ given byρ(Z) =Z∩Jt.

IfZ ∈R thenZ ∈Land Z /∈Lt, asZ *Jt. Furthermore, from (2.1),ρ(Z)∈ Lt\L= ˜L\L.

Proposition 2.32. L˜ is obtained from L⊆L˜ by doubling R along ρ.

Proof. As ρclearly preserves inclusion it suffices to show that ρ is a bijection. If ρ(Y) =ρ(Z), withY, Z ∈RthenZ = cl(Z∩Jt) = cl(Y∩Jt) =Y, soρis injective.

From (2.1) if follows thatρis also surjective.

The latticeL is obtained fromL˜ by a doubling on an appropriate subset of L.˜ To see this we use the following strengthening of the final part of Lemma 2.19. We remark that condition (2.3) of the lemma can be expressed more succinctly in terms of complements by noting that

(1) O^X(O^X(Y)∩Jt) =O^X(O^Jt(Y))and

(2) if Y ⊆Jtthen(O^X(O^X(Y)∩Jt))∩Jt= cl^Jt(Y)∈L(Jt).

Lemma 2.33. LetY ⊂X. ThenY andY∪{t}belong toLif and only ifO^X(Y)* J_t and

(2.3) Y =

O^X(O^X(Y)∩J_t), if Y *J_t O^X(O^X(Y)∩J_t)∩J_t, if Y ⊆J_t . Proof.Suppose thatO^X(Y)*Jt. IfY *Jt then

cl^X(Y ∪ {t}) =O^X(O^X(Y)∩Jt)

=O^X(O^X(Y)∩Jt)∪ {t}.

(2.4)

If, on the other hand,Y ⊆Jt thenO^X(Y ∪ {t}) = (O^X(Y)∩Jt)∪ {t} so cl^X(Y ∪ {t}) =O^X (O^X(Y)∩Jt)∪ {t}

= O^X(O^X(Y)∩J_t)∪ {t}

∩(J_t∪ {t})

= O^X(O^X(Y)∩Jt)∩Jt

∪ {t}.

(2.5)

In both cases, if in addition (2.3) holds thencl^X(Y∪{t}) =Y∪{t}andY∪{t} ∈L.

Now, given that O^X(Y) * Jt and (2.3) holds, choose x ∈ O^X(Y) such that x /∈ Jt. Then O^X(x) = O^X(x) ⊇ cl^X(Y) ⊇ Y and t /∈ O^X(x). From the above Y ∪ {t} ∈L, soY ∪ {t}=O^X(Z), for someZ∈L. ThenO^X(Z∪ {x}) =O^X(Z)∩ O^X(x) =Y; andY ∈L.

Conversely suppose thatY andY ∪ {t}belong toL. In this case ifO^X(Y)⊆Jt

thenO^X(Y)⊆ O^X(Y)∪ {t}socl^X(Y)⊇ O^X(O^X(Y))∩(Jt∪ {t}). Thust∈cl^X(Y) and Y /∈ L, a contradiction. ThusO^X(Y)*Jt. IfY *Jt then, from (2.4), Y = cl^X(Y ∪ {t})\{t} = O^X(O^X(Y)∩Jt). If, on the other hand, Y ⊆ Jt then (2.5) implies thatY = (O^X(O^X(Y)∩Jt))∩Jt, as claimed.

The lemma prompts the following definition.

Definition 2.34. Let

S1={Y ⊂X|Y *Jt,O^X(Y)*Jt, andY =O^X(O^X(Y)∩Jt)}

and

S2={Y ⊂X|Y ⊆Jt,O^X(Y)*Jt, andY = (O^X(O^X(Y)∩Jt))∩Jt}.

Let S=S1∪S2 and let T ={Y ∪ {t}|Y ∈S}. Letσbe the map from S toT given byσ(Y) =Y ∪ {t}.

From Lemma 2.33 it follows thatS∪T ⊆Land by definitionS⊆L. Moreover,˜ from Lemma 2.19,β(Y) =Y, for allY ∈S, so S=β(S)⊆β( ˜L)⊆L.

Proposition 2.35. The lattice L is obtained from β( ˜L)⊆L by doubling S along σ.

Proof. Using Lemma 2.19, ifY ∈S andY ∪ {t}=β(U), for some elementU ∈L,˜ then t ∈ β(U) implies that O^X(U) ∈ Jt. However Y ∪ {t} = β(U) = U ∪ {t}

so U = Y and O^X(Y) * J_t, a contradiction. Hence no element of T belongs to the image of β. If Z ∈ L and Z is not in the image of β then, from Lemma 2.19 again, γ(Z) = Z\{t} ∈ L˜ and so β(Z\{t}) 6= Z. Thus either t /∈ Z and β(Z\{t}) = β(Z) = Z ∪ {t} or t ∈ Z and β(Z\{t}) = Z\{t}. In the former case Z ∈ L and β(Z) = Z ∪ {t} ∈ L so Z ∈ S and Z ∪ {t} ∈ T ∩Im(β), a contradiction. Henceβ(Z\{t}) =Z\{t} ∈Landt∈Z. It follows from Lemma 2.33 that Z\{t} ∈ S so Z ∈ T. That is, T =L\β( ˜L). As σ is an inclusion preserving

bijection the result follows.

2.6. Extension along the complement of a simplex. In those cases whereγis injective it follows, from Corollary 2.21, thatγis a bijection and so an isomorphism of lattices. We now consider under which conditions this may occur. Let V = O^X(t) = Jt ∪ {t} ∈ L. If γ is injective then V = βγ(V) = cl^X(Jt)∪ {t}, so Jt = cl^X(Jt)∈L. Therefore Jt ∈L is a necessary condition for γ to be injective.

We shall show, in Section 2.8, that if J_t is closed then h(L) =h(L); but we shall also see in Lemma 2.37 that a further condition is required to ensure that γ is injective. First however we establish a simple form forγ whenJtis closed.

Lemma 2.36. If Jt∈L thenL˜ =Landγ(Z) =Z\{t}, for all Z∈L. Moreover, in the notation of Definition 2.34, S1 = ∅ so L is obtained from β(L) ⊆ L by doublingS2 along σ.

Proof. IfJt∈L thenLt is a subset ofL, soL˜ =L, as claimed. In this caseγ=γ andβ=β, so the first statement of the Lemma follows from Lemma 2.19. IfY ∈S1

then Y ∈Land Y =O^X(W), where W =O^X(Y)∩Jt∈L. However this means

O^X(Y) =W ⊆Jt, a contradiction.

Lemma 2.37. The mapγis an isomorphism of lattices if and only ifJt=O^X(S), whereS is a simplex ofΓ.

Proof. First assume that Jt = O^X(A), where A ⊆ X is a simplex. In this case, in the notation of Definition 2.34, Y ∈ S2 implies Y ∈ L(Jt), so Y = O^Jt(W), for some W ⊆Jt. NowW ⊆Jt=O^X(A) =O^Jt(A)which impliesO^Jt(O^Jt(A))⊆ O^Jt(W) =Y. AsAis a simplexA⊆JtsoA⊆ O^Jt(O^Jt((A))and thusO^X(Y)⊆Jt, contrary to the definition ofS2. ThereforeS1=S2=∅and from Lemma 2.36L=L.

On the other hand suppose thatJt=O^X(N), whereN is not a simplex. Then, from Lemma 2.1.6, there is s ∈ N such that s /∈ Jt. Therefore t /∈ O^X(N) and we haveJt=O^X(N)∈L. Henceγ(Jt) =Jt=γ(Jt∪ {t})and γ is not injective.

From the remarks at the beginning of the Section it follows that if Jt is not the orthogonal complement of a simplex inX thenγis not injective. (It is not difficult

to see that in this caseJt∈S2.)

As a consequence of this lemma we obtain the following theorem.

Theorem 2.38. The lattices L andL are isomorphic if and only ifJ_t=O^X(S), whereS⊂X is a simplex, in which case γis an isomorphism.

Proof. From Lemma 2.37, if Jt = O^X(S), where S ⊂ X is a simplex, then the lattices are isomorphic andγis an isomorphism. Now suppose thatJtis not of this form. The mapβ :L→Lis injective so |L| ≤ |L|. If|L|=|L| then, asγβ= idL, it follows thatγ is also injective, contrary to Lemma 2.37. Thus|L|<|L|and the

lattices are not isomorphic.

2.7. Abelian Inflation and Deflation. In this section we consider further the case where the setJtdefined above is the orthogonal complement of a simplex, as in the previous section. First we introduce some equivalence classes on subsets of verticesΓ. We say that two subsetsS andT ofX are⊥-equivalentinX and write S∼⊥T if and only ifS^⊥=T^⊥; that isO^X(S) =O^X(T).

Lemma 2.39. Let S andT be subsets ofX.

(1) S∼⊥T if and only if T ⊆cl^X(S) andS⊆cl^X(T).

(2) IfS∼⊥ T andY ∈L(Γ) thenS⊆Y implies that T ⊆Y.

(3) If S is a simplex and S ∼⊥ T then T is a simplex. In particular, in this case,G(Γ^′)is an Abelian group, whereΓ^′ denotes the full subgraph ofΓon S∪T.

Proof.To see the first statement note that, using Lemma 2.1,S∼⊥T if and only if cl^X(S) = cl^X(T). It follows thatS∼⊥ T implies thatS ⊆cl^X(T)andT ⊆cl^X(S).

Conversely if S ⊆cl^X(T) then S^⊥ ⊇ T^⊥⊥⊥ =T^⊥. Similarly if T ⊆cl^X(S) then T^⊥⊇S^⊥and the result follows. To prove the second statement note that by Lemma 2.4,S⊆Y andY closed impliescl^X(S)⊆Y. ThusT ⊆cl^X(T) = cl^X(S)⊆Y. For the third statement we have S ⊆ O^X(S) = O^X(T), since S is a simplex, and so T ⊆ O^X(S) =O^X(T). HenceT is a simplex and the result follows.

In the light of Lemma 2.39.3 we define theAbelian closure acl(S) of a simplex S to be the union of subsetsT of X such that S∼⊥T. ThenS ⊆acl(S)and it is easy to see then thatacl(S)is the unique maximal simplex such thatS∼⊥acl(S).

Now let ∆ be a graph with vertices V. Let S be a simplex of ∆ and y ∈ V with y /∈S and suppose thatS ∼⊥ {y} in ∆: that isO^V(S) =O^V(y). Let ∆_y =

∆\{y}. Then∆_y is called anelementary Abelian deflationof∆ and∆is called an elementary Abelian inflationof ∆y. In this case the subgroup of∆y generated by S is a free Abelian group of rank|S|and the subgroup of∆generated byS∪ {y}

is free Abelian of rank|S|+ 1.

If a graphΩcan be obtained from a graphΓby finitely many elementary Abelian inflations thenΩis called anAbelian inflationofΓandΓis called anAbelian defla- tionofΩ. The same terminology carries over to the respective partially commutative groups.

Proposition 2.40. If∆ is an Abelian inflation of Γ thenL(∆)≃L(Γ).

Proof.It suffices to prove the result in the case where ∆ is an elementary Abelian inflation of Γ. Suppose then that Γ = ∆t, for some vertex t of ∆. To be more explicit letV(∆) =X, assume thatt∈X,S ⊆X is a simplex,t /∈SandS∼⊥ {t}

in∆. LetX=V(Γ). Then, asΓ = ∆twe haveX =X∪ {t}andO^X(t) =O^X(S).

Let Jt = O^X(t)\{t}. Then, as S ⊆ X, we have O^X(S) = Jt ∈ L(Γ). As ∆ is obtained fromΓby adding the vertextwhich is joined to precisely those vertices in Jt=O^X(S), andS is a simplex, it follows from Theorem 2.38 that L(Γ)≃L(∆),

as claimed.

2.8. Extension along a closed set. We saw in Section 2.6 that ifJt is a closed set then, in the notation of Definition 2.34, L is obtained from β(L) by doubling S2 along σ. In this section we shall show that if Jt is closed then h(L) = h(L).

If Jt =O^X(S) where S is a simplex then Γ is an Abelian inflation of Γ, so this follows from Proposition 2.40. Therefore we assume that A ⊆X, such that A is not a simplex, andJt=O^X(A)∈L. AsA is not a simplex the set A^′ =A\Jt is non-empty. Fixa∈A^′.

Now let Y ∈L with t ∈Y. ThenY =O^X(Z), where Z ⊆Jt∪ {t}. There are two possibilities. Either

(1) Z⊆Jt, in which caseA∪ {t} ⊆ O^X(Z) =Y; or

(2) Z*Jt, in which caseZ=W∪ {t}, whereW ⊆Jt, soa /∈Y. In the latter case

Y =O^X(W ∪ {t})

= (O^X(W)∪ {t})∩(Jt∪ {t})

= (O^X(W)∩Jt)∪ {t}

whereas

O^X(W ∪ {a}) =O^X(W)∩ O^X(a)

= (O^X(W)∪ {t})∩ O^X(a)

=O^X(W)∩ O^X(a).

This prompts us to define a mapα:L→Lby α(Y) =

O^X(W∪ {a})ift∈Y, a /∈Y

Y otherwise .

Note that

(2.6) t /∈α(Y)andY\{t} ∪ {a} ⊆α(Y), ift∈Y anda /∈Y and that

(2.7) eithert /∈α(Y)or A∪ {t} ⊆α(Y)for allY ∈L.

Now letC=Z1<· · ·< Zk be a strong ascending chain inL. Letα(C) =α(Z1)≤

· · · ≤α(Zk).

Lemma 2.41. α(C)is a strong ascending chain in L.

Proof.Definer=r(C)to be the smallest integer such thatt∈Zr. If no suchrexists thenα(C) =C and there is nothing to prove. Suppose then that 1≤r≤k. Let s be the smallest integer such thatA∪ {t} ⊆Zs(and sets=k+ 1ifA∪ {t}*Zk).

Thenr≤s≤k+ 1. Forisuch that1≤i≤r−1ors≤i≤kwe haveα(Zi) =Zi. Therefore we need only check thatα(Zi)< α(Zi+1)fori such thatr−1≤i≤s.

Ifr=sthen alsoα(Zr) =Zr and soα(C) =C and the Lemma holds.