## S e MR

ISSN 1813-3304## СИБИРСКИЕ ЭЛЕКТРОННЫЕ МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ

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 ﬁnite 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 ﬁnite 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 deﬁne x^{⊥} to be the set of all vertices of Γ
connected withx. For a subsetY ⊆X we deﬁne

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 inﬂation and deﬂation 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, ﬁnite graph throughout this paper. If xand y are vertices of a graph then we deﬁne 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 inﬁmum and a unique supremum. We usually writes∧tands∨tfor the inﬁmum 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 ﬁnite chaina0 <· · ·< ak is said to bek.Descending chains

are deﬁned analogously. A lattice may be bounded and have inﬁnite ascending or descending chains (or both). Theheightof a latticeLis deﬁned 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 deﬁnes a partial order ‘≤’ on C(G). We deﬁne the inﬁmum 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 deﬁned 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 deﬁnitions 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 deﬁned 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 inﬁnite 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 inﬁnite otherwise.

1.4. Partially Commutative Groups. Let Γ be a ﬁnite, 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^{−}^{1}h^{−}^{1}gh ofg andh
by[g, h]. Let

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

We deﬁne thepartially commutative group with(commutation) graph Γto be the group G(Γ) with presentationhX |Ri. (Note that these are the groups which are called ﬁnitely 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^{−1} 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^{−}^{1}wg)≥lg(w)
for everyg∈G.

The centraliser dimension of partially commutative groups is ﬁnite because all partially commutative groups are linear [10] and all linear groups have ﬁnite 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 ﬁ- nite, undirected, simple graph, with vertices X, and letG=G(Γ)be the partially commutative group deﬁned by Γ. Given vertices x, yin the same connected com- ponent ofΓ we deﬁne 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 deﬁned(x, y) =∞.

LetY andZ be subsets ofX. We deﬁne 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 deﬁnition
of orthogonal complement. Statement 2 follows from 1 and 3. Statement 4 follows
from 3. To see 5 suppose ﬁrst 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_{1}^{⊥} ={b}, Y_{2}^{⊥} ={c} and (Y1∩Y2)^{⊥} ={b, c, d}: so (Y1∩
Y2)^{⊥}6=Y_{1}^{⊥}∪Y_{2}^{⊥}. MoreoverY_{1}^{⊥⊥}={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^{X}^{1}(X1) =
O^{X}^{2}(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 deﬁne the closure of Y in Z to be cl^{Z}(Y) =
O^{Z}O^{Z}(Y). When Z = X we write cl(Y) for cl^{X}(Y). The closure operator in Γ
satisﬁes 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_{1}^{⊥}=Y_{2}^{⊥}.

(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^{X}to 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 ﬁrst 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}^{2}(Y)is Abelian if and only if
C_{G}^{2}(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 deﬁnition of closed set. Therefore Y1∩Y2 = cl(Y1∩Y2).

The relation Y1 ⊆ Y2 deﬁnes 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 deﬁning the the inﬁmum 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 ﬁxed 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^{X}^{i}(U) =O^{X}(U).

Proof. By deﬁnition O^{X}^{i}(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^{X}^{i}(U).

The relationship betweenL(Γ)and theL(Γi)is speciﬁed 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^{X}^{i}(Xi) =∅ then∅ ∈CS(Γi)andXi ∈/ CS(Γ).

(4) IfO^{X}^{i}(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^{X}^{i}(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^{X}^{i}(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^{X}^{i}(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^{X}^{i}(Xi) is the minimal element of L(Γi), in this case ∅ ∈/ L(Γi). We
have Xi = O^{X}^{i}(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^{′}_{2}
L^{′}_{1}

∅
O^{X}^{i}(Xi) =∅,

i= 1,2

X

L1 L^{′}_{2}
X1

X_{1}^{⊥}

∅
O^{X}^{1}(X1)6=∅,
O^{X}^{2}(X2) =∅,

X

L1

X1

X_{1}^{⊥}

L2

X2

X_{2}^{⊥}

∅
O^{X}^{i}(Xi)6=∅,

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

ponentsΓ1, . . . ,Γm, whereV(Γi) =Xi. Assume thatO^{X}^{i}(Xi)6=∅, fori= 1, . . . , r
and that O^{X}^{i}(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_{1}^{⊥}

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 deﬁnitions 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 eﬀect 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 deﬁneX =X ∪ {t}. Let Jtbe a subset of X. DeﬁneΓ 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 deﬁne 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 deﬁne 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 deﬁnition 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
deﬁning

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 deﬁnitions. 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. Deﬁne β˜ 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 ﬁrst statement is a direct consequence of the deﬁnitions, as is the fact thatβ˜respects the lattice inﬁmum 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_{t}and the other in
Lt\L. Assume then thatU ∈L\L_{t}andV ∈Lt\L. In this caseU = ˜γ(U) = ˜γ(V) =

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

In generalβ˜does not preserve supremums and ˜γdoes not preserve inﬁmums.

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 deﬁnitions 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^{X}O^{X}(U) =

O^{X}O^{X}(U), ifO^{X}(U)*Jt

O^{X}O^{X}(U)∪ {t}, ifO^{X}(U)⊆J_{t}
and (2.2) holds asU *J_{t}implies that U ∈L. IfU ⊆J_{t}then

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

β(U) =

O^{X}O^{X}(U)∩Jt, ifO^{X}(U)*Jt

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

In this case, as U ⊆Jt we have O^{X}O^{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 diﬀerences 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 deﬁned analogously, replacing< by>. The lengthof a ﬁnite 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 deﬁned 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 inﬁnite 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 diﬀerences 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 diﬀerence of one between the heights of L andLmay occur and may be due either to a diﬀerence 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
deﬁnition. 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 deﬁnition.

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 suﬃces 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 ﬁnal 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^{J}^{t}(Y))and

(2) if Y ⊆Jtthen(O^{X}(O^{X}(Y)∩Jt))∩Jt= cl^{J}^{t}(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 deﬁnition.

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 deﬁnitionS⊆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 Deﬁnition 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 ﬁrst 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 Deﬁnition 2.34, Y ∈ S2 implies Y ∈ L(Jt), so Y = O^{J}^{t}(W),
for some W ⊆Jt. NowW ⊆Jt=O^{X}(A) =O^{J}^{t}(A)which impliesO^{J}^{t}(O^{J}^{t}(A))⊆
O^{J}^{t}(W) =Y. AsAis a simplexA⊆JtsoA⊆ O^{J}^{t}(O^{J}^{t}((A))and thusO^{X}(Y)⊆Jt,
contrary to the deﬁnition 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 diﬃcult

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 setJtdeﬁned 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 ﬁrst 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 deﬁne 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 deﬂationof∆ and∆is called an
elementary Abelian inﬂationof ∆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 ﬁnitely many elementary Abelian inﬂations thenΩis called anAbelian inﬂationofΓandΓis called anAbelian deﬂa- tionofΩ. The same terminology carries over to the respective partially commutative groups.

Proposition 2.40. If∆ is an Abelian inﬂation of Γ thenL(∆)≃L(Γ).

Proof.It suﬃces to prove the result in the case where ∆ is an elementary Abelian inﬂation 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 Deﬁnition 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 inﬂation 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 deﬁne 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.Deﬁner=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.