A MODEL THEORETIC STUDY OF RIGHT-ANGLED BUILDINGS

ANDREAS BAUDISCH, AMADOR MARTIN-PIZARRO AND MARTIN ZIEGLER

Abstract. We study the model theory of right-angled buildings with infinite residues. For every Coxeter graph we obtain a complete theory with a natural axiomatisation, which is ω-stable and equational. Furthermore, we provide sharp lower and upper bounds for its degree of ampleness, computed exclusively in terms of the associated Coxeter graph. This generalises and provides an alternative treatment of the free pseudospace.

Contents

1. Introduction 1 2. Buildings and geometries 4 3. Simply connected Γ-spaces 10 4. The Theory PS_{Γ} 18 5. Non-splitting reductions 22 6. Forking 26 7. Equationality 33 8. Ampleness 44 References 49

1. Introduction

A Coxeter group (W, Γ) consists of a group W with a fixed set Γ of generators and defining relations (γ · δ)^{m_{γ,δ}} = 1, where m_{γ,γ} = 1 and m_{γ,δ} = m_{δ,γ}, for γ ≠ δ, is either ∞ or an integer larger than 1. We will exclusively consider finitely generated Coxeter groups, with Γ finite. A word w is a finite sequence on the generators from Γ, and w is reduced if its length is minimal with respect to all words representing the same element of W. A chamber system (X, W, Γ) for the Coxeter group (W, Γ) is a set X, equipped with a family of equivalence relations (∼_{γ}, γ ∈ Γ). If w = γ_{1} ⋯ γ_{n} is a reduced word, a reduced path of type w from x to y in X is a sequence x = x_{0}, …, x_{n} = y such that x_{i−1} and x_{i} are ∼_{γ_{i}}-related and different for every 1 ≤ i ≤ n. A chamber system (X, W, Γ) is a building if each ∼_{γ}-class contains at least two elements and such that, for every pair x and y in X, there exists a element g ∈ W such that there is a reduced path of type w from x to y if and only if the word w represents g. It follows that g is uniquely determined by x and y, and that the reduced path connecting x and y is uniquely determined by its type w. We refer the reader to [6] for a pleasant introduction to buildings.

Date: August 12, 2015.

1991 Mathematics Subject Classification. Primary 03C45; Secondary 51E24.

Key words and phrases. Model Theory, ampleness, Coxeter, buildings.

The second author conducted research with support of programme ANR-09-BLAN-0047 Modig, ANR-13-BS01-0006 Valcomo as well as an Alexander von Humboldt-Stiftung Forschungsstipendium für erfahrene Wissenschaftler 3.3-FRA/1137360 STP.

The Coxeter group (W, Γ) is right-angled if for every γ ≠ δ, the value m_{γ,δ} is either 2 or ∞. So W is determined by its Coxeter diagram: a graph with vertex set Γ such that γ and δ have an edge connecting them, which we denote by R(γ, δ), if m_{γ,δ} = ∞. In an abuse of notation, we will denote this graph by Γ as well. The elements of Γ will be referred to as colours or levels. Note that, for involutions γ and δ, the relation (γ · δ)^{2} = 1 means that γ and δ commute. We call a word w′ a permutation of w if it can be obtained from w by a sequence of swaps of commuting consecutive generators. In right-angled Coxeter groups, a word w is reduced if and only if no permutation of w has the form w_{1} · γ · γ · w_{2}, for some generator γ. Every element of W is represented by a unique reduced word, up to permutation. In a building (X, W, Γ), the the class x/∼_{γ} is the γ-residue of x. A right-angled Coxeter group admits a unique (up to isomorphism) countable building B_{0}(Γ) with infinite residues [7, Proposition 5.1], which we call rich.

A right-angled building can also be described in terms of an incidence geometry or, as we will refer to, a coloured graph. The vertices of colour γ are equivalence classes of ∼^{γ}, the transitive closure of all ∼_{γ′}, for γ′ ≠ γ. Two vertices are connected by an edge if the corresponding classes intersect. The coloured graph associated to the rich building given by the diagram

\begin{matrix}[0, n] \\ 0 \\ 1 \\ 2 \\ n − 1 \\ n \end{matrix}

is, as noticed by Tent [15], the prime model of the theory of the free n-dimensional pseudospace. A model of a theory is prime if it elementarily embeds into every model. The n-dimensional pseudospace, also considered by the authors in [2], witnessed the strictness of the ample hierarchy for ω-stable theories. We are indebted to Tent for pointing out the connection between the free pseudospace and Tits buildings, which was the starting point of the present work.

Recall that a countable complete theory is ω-stable if there is a rank function R defined on the collection of definable sets of a (sufficiently saturated) model M with the following principle: If X ⊂ M^{n} is definable, then R(X) > α if and only if X contains an infinite family of pairwise disjoint definable sets Y_{i} with R(Y_{i}) ≥ α. The smallest rank function is called Morley rank. The Morley rank of a type is the smallest Morley rank of its formulae. This notion agrees with the Cantor-Bendixon rank on the space of types over an ω-saturated model, equipped with the Stone topology. For an algebraically closed field with no additional structure, definable sets are exactly the Zariski constructible ones, and Morley rank coincides with the Zariski dimension.

If M is a group of finite Morley rank, that is, it carries a definable group structure and the Morley rank is always finite, this notion of dimension is well-behaved. For example, given a definable fibration S ⊂ X ×Y → Y, the subset consisting of those y in Y such that the fibre over y has dimension k is definable for every k in N. If all fibres have constant Morley rank k, then RM(X) = RM(Y) + k.

Motivated by a famous conjecture about the structure of strongly minimal sets (that is, irreducible definable sets of rank 1), the Algebraicity Conjecture states that every simple group of finite Morley rank can be seen as an algebraic group over an algebraically closed field, which is itself interpretable in the mere group structure. Though the general conjecture on strongly minimal sets was proven to be false [9], work on the Algebraicity Conjecture, which remains open, has become a fruitful research area, combining ideas from model theory as well as the classification of simple finite groups.

If an ω-stable theory does not interpret a certain incidence configuration present in euclidean space, then it interprets neither infinite fields nor specific possible counterexamples to the Algebraicity Conjecture, called bad groups [12]. The notion of n-ampleness [13, 4] for a theory generalises the incidence configuration given in euclidean (n + 1)-space by flags of affine subspaces of increasing dimension, from a single point to a hyperplane. Ampleness introduces thus a geometrical hierarchy, according to which algebraically closed fields are n-ample for every n. The first two levels of this hierarchy suffice to describe the structure of definable groups [10, 12]: they are virtually abelian, if the ω-stable group is not 1-ample, and virtually nilpotent if the group has finite Morley rank and is not 2-ample. However, little is known from 2 onwards. In particular, whether the ample hierarchy was strict remained long unknown. Evans conjectured that his example could be accordingly modified to illustrate the strictness. Extending the construction in [3], where a 2-ample theory was produced which interprets no infinite group (and thus, no infinite field is interpretable), the aforementioned free n-dimensional pseudospace was constructed [2, 15] for every n, whose theory is ω-stable and n-ample yet not (n + 1)-ample. In particular, the n-dimensional pseudospace is a graph with n + 1 many colours, labelled from 0 to n such that the induced subgraph on consecutive colours is an infinite pseudoplane, whose theory was known to be 1-ample but not 2-ample.

In this article, we will provide an alternative approach to the above construction, which incorporates as well the rich buildings of every right-angled Coxeter group. As explained in Section 2, a right-angled building B can be recovered from its associated coloured graph M: The elements of B correspond to the flags of M, coloured subgraphs of M isomorphic to Γ. This article deals with the model theory of M_{0}(Γ), the coloured graph associated to the rich building B_{0}(Γ) given by Γ. Though models of the theory of M_{0}(Γ) need not arise from buildings, given flags F and G in a model, a notion of a reduced path between F and G can be defined, whose corresponding word consists of letters which are non-empty connected subsets of Γ. We show that the coloured graphs associated to rich buildings are simply connected: any two reduced paths between two given flags have the same word, up to permutation. A combinatorial study of the reduction of a path between two flags allows us to show the following crucial result (cf. Theorem 3.26):

Theorem A. Simple connectedness is an elementary property.

Let PS_{Γ} denotes the collection of sentences stating the following two elementary properties: Simple connectedness and that, given any flag G and a colour γ, there are infinitely many flags which differ from G only at the vertex of colour γ. The following theorem (cf. Theorem 4.12 and Corollaries 4.14 and 6.13) yields that PS_{Γ} axiomatises the complete theory of M_{0}(Γ):

Theorem B. The theory PS_{Γ} is complete and ω-stable of Morley rank ω^{(K−1)}, where K is the cardinality of a connected component of Γ of largest size. The coloured graph M_{0}(Γ), associated to the countable rich building B_{0}(Γ), is the unique prime model of PS_{Γ}.

Morley rank defines a notion of independence, which agrees in the ω-stable case with non-forking, as introduced by Shelah. A remarkable feature of non-forking independence, which rules out the existence of infinite definable groups, is total triviality: whenever we consider a base set of parameters D, given tuples a, b and c such that a is independent both from b and from c over D, then it is independent from b, c over D. Recall that a canonical basis of a type p over a model is some set, fixed pointwise by exactly those automorphisms α of a sufficiently saturated model N fixing the global non-forking extension p of p over N. If Cb(p) exists, then it is unique, up to interdefinability, though generally canonical bases only exist as imaginary elements in the expansion T^{eq} of an ω-stable theory T. Within the wider class of stable theories, there is a distinguished subclass consisting of the equational ones, where each definable set in every cartesian product N^{n} of a model N is a boolean combination of instances of n-equations φ(x, y), that is, the tuple x has length n and the family of finite intersections of instances φ(x, a) has the descending chain condition. Whilst all known examples of stable theories arising naturally in nature are equational, the only stable non-equational theory constructed so far [8] is an expansion of the free 2-dimensional pseudospace. We obtain the following (cf. Corollaries 7.25 and 7.28 and Proposition 7.26):

Theorem C. The theory PS_{Γ} is equational, totally trivial with weak elimination of imaginaries: every type over a model has a canonical basis consisting of real elements.

To conclude, we provide lower and upper bounds on the ample degree of the theory PS_{Γ}, which can be described in terms of the underlying Coxeter graph Γ. Set r to be the minimal valency of the non-isolated points of Γ and n the largest integer such that the graph [0, n], as before, embeds as a full subgraph of Γ. We deduce (cf. Theorem 8.6):

Theorem D. The theory PS_{Γ} is n-ample but not (|Γ| − r + 1)-ample

These bounds are sharp and attained by [0, n], by the circular graph on n+2 points or by the extremal case of the complete graph K_{N} on N ≥ 2 elements, whose theory is 1-ample but not 2-ample.

acknowledgements

We thank the referee for a careful reading and for providing many valuable comments, which helped us improve the presentation of this article.

2. Buildings and geometries

Definition 2.1. A graph consists of set of vertices together with a symmetric and irreflexive binary relation. Two vertices a and b are adjacent if the pair (a, b) lies in the relation.

Given a finite graph Γ, its associated right-angled Coxeter group (W, Γ) consists of the group W generated by the elements of Γ with defining relations:

γ^{2} = 1  for all γ in Γ
γδ = δγ  if γ and δ are not adjacent.

As a convention, no element γ commutes with itself.

From now on, all Coxeter groups are right-angled.

Fix a Coxeter group (W, Γ). A word v = γ_{1} ⋯ γ_{n} in the generators is reduced if there is no pair i ≠ j such that γ_{i} equals γ_{j} and commutes (i.e. is not adjacent) with every letter occurring between γ_{i} and γ_{j}. Two words are equivalent if they represent the same element of W. Clearly, every word is equivalent to a reduced one. A reduced word w commutes with γ ∈ Γ if every element of w does.

A word v′ is a permutation of v if it can be obtained from v by a sequence of commutations on pairs of commuting generators. A permutation of a reduced word is again reduced.

The following is easy to see.

Lemma 2.2. Two reduced words u and v are equivalent if and only if u is a permutation of v.

For s a subset of Γ, let ⟨s⟩ denote the subgroup of W generated by s.

Corollary 2.3. Given two subsets s and t of Γ,

⟨s ∩ t⟩ = ⟨s⟩ ∩ ⟨t⟩.

Definition 2.4. A chamber system (X, W, Γ) for the Coxeter group (W, Γ) consists of a set X equipped with a family of equivalence relations ∼_{γ} for each γ ∈ Γ. Given a word w = γ_{1} ⋯ γ_{n}, a path of type w from x to y in X is a sequence x = x_{0}, …, x_{n} = y such that x_{i−1} and x_{i} are different and ∼_{γ_{i}}-related for every 1 ≤ i ≤ n. A path of type w is reduced if w is.

A chamber system (X, W, Γ) is a building if each ∼_{γ}-class contains at least two elements, and such that, for every pair x and y in X, there exists a element g ∈ W with the property that there is a reduced path of type w from x to y if and only if the word w represents g.

We will refer to a chamber system (X, W, Γ) uniquely by the underlying set X if the corresponding Coxeter group (W, Γ) is clear. The following two lemmas can be easily shown.

Lemma 2.5. In a building X, a reduced path of type w connecting x and y is uniquely determined by w, x and y.

We will denote the existence of a path of type w connecting x to y by x ⟶^{w} y. In particular, we have that x ⟶^{γ} y if and only if x ≠ y are ∼_{γ}-related.

Lemma 2.6. A chamber system X is a building if and only if the following four conditions hold:

(a) Every ∼_{γ}-class has at least two elements.

(b) Every two elements of X are connected by a path.

(c) Given two commuting generators γ and δ, if the elements x and y are connected by a path of type γδ, then x and y are also connected by a path of type δγ.

(d) There is no non-trivial closed reduced path.

A chamber system satisfying conditions (b) and (c) is called strongly connected. A strongly connected chamber system is a quasi-building if it satisfies condition (d). Lemma 2.5 holds for quasi-buildings, as well.

Remark 2.7. Given elements b ⟶^{w} a in a quasi-building A and λ ∈ Γ commuting with w, if a ∼_{λ} a^{∗} ∈ A, then there is a unique b^{∗} in A with b ∼_{λ} b^{∗} ⟶^{w} a^{∗}.

Proof. Iterating 2.6 (c), the reduced path b ⟶^{w} a ∼_{λ} a^{∗} yields some element b^{∗} such that b ∼_{λ} b^{∗} ⟶^{w} a^{∗}. Furthermore, this element is uniquely determined by b, a^{∗} and the reduced word λ · w, by Lemma 2.5. □

We will now produce certain extensions of a given quasi-building A. Fix some λ in Γ and an equivalence class a/∼_{λ} in A. We will extend A to a quasi-building containing a new element in a/∼_{λ}. Let B be the set of elements x in A which are connected to a by a reduced path of type w, where w and λ commute. In particular, the generator λ does not occur in w. Furthermore, if b and c in B are ∼_{γ}-related, then λ and γ commute.

Observe that a lies in B. For every b ∈ B, introduce a new element b^{∗}. Denote

A(a^{∗}) = A ∪ {b^{∗}}_{b∈B},

and extend the chamber structure of A to A(a^{∗}) by setting

b^{∗} ∼_{γ} c^{∗} ⇔ b ∼_{γ} c

for all b, c in B, and

b^{∗} ∼_{γ} a′ ⇔ λ = γ and b ∼_{λ} a′,

for all b ∈ B and a′ ∈ A. In particular, if b is in B and b ⟶^{w} a, then we obtain a reduced path b^{∗} ⟶^{w} a^{∗}.

The extension A(a^{∗}) is called simple.

Lemma 2.8. The chamber system A(a^{∗}) is a quasi-building.

Proof. Properties (b) and (c) of Lemma 2.6 can be easily shown. For example, suppose that δ and γ_{1} commute, suppose b^{∗} ∼_{γ_{1}} d^{∗} ∼_{δ} c^{∗}. Then b ∼_{γ_{1}} d ∼_{δ} c, so there is some d′ in A such that b ∼_{δ} d′ ∼_{γ_{1}} c′, whence b^{∗} ∼_{δ} (d′)^{∗} ∼_{γ_{1}} c^{∗}. The other cases are treated in a similar fashion. For property (d), note first that any two elements of B are connected by a word which commutes with λ. Thus, a reduced path cannot change sides twice between A and A(a^{∗}) \ A, for otherwise it would contain a reduced subpath of the form γ ·w ·γ, where w commutes with γ. A closed reduced path is hence either fully contained in A – and thus trivial since A is a quasi-building – or fully contained in A(a^{∗}) \ A, in which case it is in bijection with a closed reduced path in A, which must be then trivial. □

Corollary 2.9. For every Coxeter group (W, Γ), there is a countable building in which all ∼_{γ}-equivalence classes are infinite.

We will now show that every subset of a quasi-building has a strongly connected hull, which is attained by a sequence of simple extensions.

Proposition 2.10. Given a strongly connected subset A of a quasi-building X and a^{∗} in X\A with a^{∗} ∼_{λ} a ∈ A, the smallest strongly connected subset of X containing A ∪ {a^{∗}} is isomorphic to A(a^{∗}).

Proof. Observe that A is a quasi-building, since X is. Let B ⊂ A be as in the construction of A(a^{∗}), that is, the set of elements b ∈ A, with b ⟶^{w} a and w commutes with λ.

Every b in B yields a unique b^{∗} in X such that b ⟶^{λ} b^{∗} ⟶^{w} a^{∗}, by Remark 2.7. Since w is uniquely determined, up to permutation, by b (and a), the element b^{∗} depends only on b. By symmetry, the element b is determined by b^{∗}. Thus, the elements b^{∗} are pairwise distinct. Note that none of the b^{∗}’s belong to A, since b^{∗} ⟶^{w} a^{∗} ⟶^{γ} a and A is strongly connected.

Therefore A(a^{∗}) may be identified with a subset of X, which is contained in every strongly connected extension of A ∪ {a^{∗}}. We need only show that the chamber structure of A ∪ {a^{∗}} agrees with the structure induced by X. Given distinct elements b and c in B with b ∼_{δ} c, we need only show that b^{∗} ∼_{δ} c^{∗}, since the converse follows by replacing a, b and c with a^{∗}, b^{∗} and c^{∗}.

The set A is strongly connected, so there are reduced words u and v such that

a ⟶^{u} b and a ⟶^{v} c in A.

Claim. Let a, b and c be distinct elements of a quasi-building X with b ∼_{δ} c. Suppose that a ⟶^{u} b and a ⟶^{v} c for reduced words u and v. Then there are three possibilities:

(1) u · δ is reduced.

(2) v · δ is reduced.

(3) There exists a reduced word w · δ and an element a′ such that a ⟶^{w} a′,

a′ ⟶^{δ} b and a′ ⟶^{δ} c.

The third case implies that both u and v are equivalent to w · δ

Proof of the claim: If u · δ is not reduced, up to permutation, we may assume that u = w · δ. Choose a′ in X with a ⟶^{w} a′ ⟶^{δ} b. Thus a′ ∼_{δ} c. Either a′ = c, so w is equivalent to v, which gives case (2), or a′ ⟶^{δ} c, which gives case (3). End of the proof of the claim.

If we apply the previous claim to our situation, we obtain three possibilities:

(1) The word u · δ is reduced. Up to permutation, we have that v = u · δ. In particular, the elements γ and δ commute. Since b ∼_{δ} c ∼_{γ} c^{∗}, there is some

c′ in X with b ∼_{δ} c′ ∼_{γ} c. Note that, since a^{∗} ⟶^{v} c^{∗} and a^{∗} ⟶^{u} b^{∗} ⟶^{δ} c′, we

have that a^{∗} ⟶^{v} c′ as well. Thus c^{∗} = c′, by Remark 2.7, so c^{∗} ∼_{δ} b^{∗}.

(2) The word v · δ is reduced, which is treated similar to the first case.

(3) For some reduced word w · δ, there is an a′ such that a ⟶^{w} a′, a′ ⟶^{δ} b and a′ ⟶^{δ} c. Since A is strongly connected, the element a′ lies in A. By the first case, we have that (a′)^{∗} ∼_{δ} b^{∗} and (a′)^{∗} ∼_{δ} c^{∗}, whence b^{∗} ∼_{δ} c^{∗}.

If b^{∗} ∼_{δ} a′ for some b in B and a′ in A, then the path b ∼_{λ} b^{∗} ∼_{δ} a′ cannot be reduced, since b^{∗} does not lie in A. Thus δ = λ and b^{∗} ∼_{λ} a′.

□

Corollary 2.9 and Proposition 2.10 yield immediately the following result:

Corollary 2.11. ( cf. [7, Proposition 5.1]) Every Coxeter group (W, Γ) has, up to isomorphism, a unique countable building B_{0}(Γ), in which all ∼_{γ}-equivalence classes are infinite.

We will study the model theory of buildings using the following expansion of the natural language:

Definition 2.12. Let X be a chamber system for (W, Γ) and s a subset of Γ. By ∼_{∅}, we denote the diagonal in X × X. Otherwise, for ∅ ≠ s ⊂ Γ, the relation ∼_{s} is the transitive closure of all ∼_{γ}, with γ ∈ s ⊂ Γ. The ∼_{s}-class of an element is called its s-residue. In particular, its γ-residue is its ∼_{γ}-class, which is often called γ-panel in the literature.

For γ in Γ, set ∼^{γ}=∼_{Γ\{γ}}. The chamber system (X, ∼^{γ})_{γ∈Γ} is called the associated dual chamber system of X.

It is easy to see that x ∼_{s} y if and only if x ⟶^{w} y for some w ∈ ⟨s⟩. If X is a quasi-building, the word w is uniquely determined as an element of W, so Corollary 2.3 implies

∼_{s_{1}∩s_{2}} =∼_{s_{1}} ∩ ∼_{s_{2}},

and particularly

(†)  ∼_{γ} = ⋂_{β≠γ} ∼^{β} .

Thus, for a quasi-building X, the chamber system (X, ∼_{γ})_{γ∈Γ} is definable in its associated dual chamber system (X, ∼^{γ})_{γ∈Γ}. Clearly, the latter is only definable if countable disjunctions are allowed. The aim of this article is to study the complete theory of B^{0}(Γ), the associated dual chamber system of B_{0}(Γ), which was defined in Corollary 2.11.

Lemma 2.13. The dual chamber system (X, ∼^{γ})_{γ∈Γ} of a quasi-building X has the following elementary properties:

(1) Given x and y in X with x ∼^{γ} y for all γ ∈ Γ, then x = y.

(2) If (x_{γ})_{γ∈Γ} is a coherent sequence in X, i.e. whenever γ and δ are adjacent, there exists some y_{γ,δ} in X with x_{γ} ∼^{γ} y_{γ,δ} ∼^{δ} x_{δ}, then there exists an element z ∈ X with z ∼^{γ} x_{γ} for all γ ∈ Γ.

Proof. Property (1) clearly follows from condition (†).

In order to show Property (2), note that any singleton is a quasi-building and has property (2). By Proposition 2.10, we need only show now that, if A is a quasi-building with Property (2), then so is A(a^{∗}).

Let (x_{γ})_{γ∈Γ} be a coherent sequence in A(a^{∗}), where a^{∗} ∼_{λ} a ∈ A. Each x_{γ} lies either in A or is ∼_{λ} connected to some element in A. Since only the ∼^{γ}-class of x_{γ} matters, we may assume that all x_{γ} belong to A, for γ ≠ λ. If x_{λ} is in A, then the result follows, since Property (2) holds in A. Otherwise, if x_{λ} does not belong to A, we have that x_{λ} ⟶^{w} a^{∗}, for a reduced word w which commutes with λ. Thus x_{λ} ∼^{λ} a^{∗} and we may assume that x_{λ} = a^{∗}.

By assumption, for every γ adjacent with λ, there is some y_{λ,γ} in A(a^{∗}) such that a^{∗} ∼^{λ} y_{λ,γ} ∼^{γ} x_{γ}. The element y_{λ,γ} cannot lie in A, for otherwise the reduced path a ∼_{λ} a^{∗} ∼^{λ} y_{λ,γ} implies that so is a^{∗}. Thus y_{λ,γ} is of the form b_{λ,γ}^{∗} for some b_{λ,γ} ∈ A.

It follows that a ∼^{λ} b_{λ,γ} ∼^{γ} x_{γ}. Replacing the element x_{λ} in the sequence (x_{γ}) by a, yields a new sequence contained in A and coherent. Thus, we find an element c in A such that c ∼^{λ} a and c ∼^{γ} x_{γ} for γ ≠ λ. Observe that c^{∗} ∼^{λ} a^{∗} and c^{∗} ∼^{γ} x_{γ}, so c^{∗} is the desired element.

□

Definition 2.14. A chamber system (X, ∼^{γ})_{γ∈Γ} is a dual quasi-building if it has properties (1) and (2) from Lemma 2.13.

The following remark can easily be verified.

Remark 2.15. A chamber system (X, ∼^{γ})_{γ∈Γ} is a dual quasi-building if and only if for every coherent sequence (x_{γ})_{γ∈Γ} there is a unique z with z ∼^{γ} x_{γ} for all γ ∈ Γ.

Definition 2.16. A Γ-graph M is a coloured graph with colours A_{γ}(M) for γ in Γ, and no edges between elements of A_{γ}(M) and A_{δ}(M) if γ and δ are not adjacent.

A flag F of the Γ-graph M is a subgraph F = {f_{γ}}_{γ∈Γ}, where each f_{γ} lies in A_{γ}(M), such that the map γ ↦ f_{γ} induces a graph isomorphism between Γ and F.

The Γ-graph M is a Γ-space if the following two additional properties are satisfied:

(1) Every vertex belongs to a flag of M.

(2) Any two adjacent vertices in M can be expanded to a flag of M.

In particular, if Γ is the complete graph 𝕂_{3}, then the following 𝕂_{3}-graph is not a 𝕂_{3}-space:

1 3 2 1 3 2

Theorem 2.17. The class of dual quasi-buildings for (W, Γ) and the class of Γspaces are bi-interpretable.

Proof. In a chamber system (X, ∼^{γ})_{γ∈Γ}, we interpret a Γ-graph M(X) as follows: for every γ ∈ Γ, the colour A_{γ} is X/ ∼^{γ}, the set of ∼^{γ}-classes of elements in X. We consider the A_{γ} as being pairwise disjoint. For the graph structure on M(X), we impose that two elements u and v are adjacent if u ∈ A_{γ} and v ∈ A_{δ}, the colours γ and δ are adjacent and there is some z ∈ X with z ∼^{γ} u and z ∼^{δ} v.

Since every x ∈ X gives rise to the flag ϕ(x) = {x/∼^{γ} | γ ∈ Γ} of M(X), it is straight-forward to see that M(X) is a Γ-space.

Given a Γ-graph M, we define a chamber system (X (M), ∼^{γ})_{γ∈Γ}, whose underlying set is the collection of flags of M. Two flags F and G are ∼^{γ}-related if their γ-vertices agree.

We will first show that X (M) is a dual quasi-building. We need only check Property (2). Assume that (F_{γ}) is a coherent system of flags. Let f_{γ} denote the γ-vertex of F_{γ}. If γ and δ are adjacent, there is a flag G such that F_{γ} ∼^{γ} G ∼^{δ} F_{δ}. In particular, the flag G contains an edge between f_{γ} and f_{δ}. So H = (f_{γ}) is a flag of M and H ∼^{γ} F_{γ} for all γ ∈ Γ.

For a chamber system (X, ∼^{γ})_{γ∈Γ}, the correspondence x ↦ ϕ(x) defines a map ϕ : X → X ((M(X)). It is easy to see that ϕ(x) ∼^{γ} ϕ(y) if and only if x ∼^{γ} y. If X is a dual quasi-building, Property (1) implies that ϕ is injective and Property (2) that ϕ is surjective. Thus X and X ((M(X)) are definably isomorphic.

Given a Γ-graph M, the correspondence a : M(X (M)) → M which associates to each class F/ ∼^{γ} the γ-vertex of F is a bijection between M(X (M)) and the collection of vertices of M which belong to a flag of M. For adjacent γ and δ, there is an edge between F/ ∼^{γ} and G/ ∼^{δ} if and only if a(F/ ∼^{γ}) and a(G/ ∼^{δ}) belong to a common flag of M. This shows that a is a definable isomorphism if M is a Γ-space.

Thus, the classes of dual quasi-buildings and of Γ-spaces are bi-interpretable, as desired. □

In order to describe the model-theoretical properties of the dual quasi-building B^{0}(Γ) (introduced right before Lemma 2.13), we may therefore consider the firstorder theory of

M_{0}(Γ) = M(B^{0}(Γ)),

its associated Γ-space. Our reason to do this is that Γ-spaces, for certain Coxeter groups Γ, will be familiar to the readers of [3, 15, 2]. In particular, many of the tools developped in [2] can be easily generalised and adapted to this context. However, the whole model-theoretical study of B^{0}(Γ) could be done without passing to its corresponding Γ-space.

3. Simply connected Γ-spaces

Recall that by a Coxeter group we mean a right-angled finitely generated Coxeter group. From now on, fix a Coxeter group (W, Γ), which we will denote simply by W, with underlying Coxeter graph Γ. In order to describe the first-order theory of the structure M_{0}(Γ) obtained before, we will need to study non-standard paths between flags.

Notation. A letter is a non-empty connected subset of the graph Γ. Characters such as s and t will exclusively refer to letters. A word u is a finite sequence of letters.

Every generator γ in Γ defines the letter {γ}. In this way, every word in the generators can be considered as a word in the above sense.

Definition 3.1. Two letters s and t commute if s ∪ t is not a letter, i.e. if the elements of s commute with all elements of t. In particular, no letter commutes with itself. Two words commute if their letters respectively do. A word is commuting if it consists of pairwise commuting letters. A permutation of a word is obtained by repeatedly permuting adjacent commuting letters. Two words u and v are equivalent, denoted by u ≈ v, if one can be permuted into the other.

The following is easy to see.

Remark 3.2. A commuting word w = s_{1} ⋯ s_{n} is determined up to equivalence by its support

|w| = s_{1} ∪ ⋯ ∪ s_{n},

where the s_{i}’s are the connected components of |w|.

We will often write w instead of |w| if w is a commuting word.

Throughout this section, we will work inside some ambient Γ-space.

Definition 3.3. A weak flag path P from the flag F to the flag G is a finite sequence F = F_{0}, F_{1}, …, F_{n} = G of flags such that the colours where F_{i+1} and F_{i} differ form a letter s_{i+1}. To such a path, we associate the word u = s_{1} ⋯ s_{n} and denote this

by F ⟶_{u} G.

In the light of Theorem 2.17, we transfer to Γ-spaces Definition 2.12 and say that two flags F and G are A-equivalent,

F ∼_{A} G,

if the set of colours where F and G differ is contained in A ⊂ Γ. Similarly as in [2, Lemma 6.3], by decomposing any subset of Γ as a disjoint union of its connected components, we obtain the following.

Lemma 3.4. Two flags F and G are A-equivalent if and only if they can be connected by a weak flag path whose word consists of letters contained in A. In particular, setting A = Γ, any two flags can be connected by a weak flag path.

Proof. For F = {f_{γ} | γ ∈ Γ} and G = {g_{γ} | γ ∈ Γ}, let s_{1}, …, s_{n} be the connected components of {γ ∈ Γ | f_{γ} ≠ g_{γ}}. Set

F_{i} = {f_{γ} | γ ∉ s_{1} ∪ … ∪ s_{i}} ∪ {g_{γ} | γ ∈ s_{1} ∪ … ∪ s_{i}}.

Then F_{0}, …, F_{n} is a weak path which connects F and G, and it has word s_{1} ⋯ s_{n}.

□

The proof yields the following two corollaries.

Corollary 3.5. Given flags F and G, there exists a commuting word u, unique up to equivalence, such that F ⟶_{u} G. For every permutation u′ of u, there is a unique weak flag path from F to G with word u′.

Uniqueness of u follows from fact that the letters of u are the connected components of the set of colours where F and G differ.

Corollary 3.6. In a path F ⟶_{u} H ⟶_{v} G, where u and v commute, the flag H is uniquely determined by F, G, u and v.

To each relation F ⟶_{s} G associate the natural bijection A_{s}(F) → A_{s}(G). It is easy to see, that a weak flag path P : F_{0} ⟶_{s_{0}} F_{1} ⋯ F_{n−1} ⟶_{s_{n−1}} F_{n} is completely

determined by F_{0} (likewise by F_{n}) and the sequence of associated maps. If s_{1} ⋯ s_{n} is commuting, this sequence of maps is equivalent to the collection A_{s_{i}}(F_{0}) → A_{s_{i}}(F_{n}), which gives an alternative proof of 3.5. More generally, the following lemma holds.

Lemma 3.7 (Permutation of a path). Given a weak flag path P : F_{0} ⟶_{u} F_{n} and a permutation u′ of u, there is a unique weak flag path P′ : F_{0} ⟶_{u′} F_{n} such that the associated map of each letter in P is the same as the associated map of the corresponding occurrence of that letter in P′.

Such a path P′ is a permutation of P.

Definition 3.8.

• A splitting of a letter s is a (possibly trivial) word, whose letters are properly contained in s. Given words u and v, we say that u ≺ v if u is equivalent to a word obtained from v by replacing at least one occurrence of a letter in v by a splitting. We write u ⪯ v if either u ≺ v or u ≈ v.

• Whenever F ⟶_{s} G and there is no weak flag path from F to G whose word is a

splitting of s, write F ⟶^{s} G. A flag path from F to G with word u = s_{1} ⋯ s_{n}, denoted by F ⟶^{u} G, is a weak flag path F = F_{0}, …, F_{n} = G such that F_{i} ⟶^{s_{i+1}} F_{i+1} for i = 0, …, n − 1.

It is easy to see that the relation ≺ is transitive, irreflexive and well-founded (cf. [2, Lemma 5.26].) A permutation of a flag path is again a flag path. If F ⟶_{s} G,

whether F ⟶^{s} G depends on the ambient Γ-space.

Lemma 3.9. If F ⟶_{u} G, then F ⟶^{v} G for some v ⪯ u.

Proof. Suppose F ⟶_{u} G. If this is not a flag path, it contains a step F′ ⟶_{s} G′ which can be replaced by F′ ⟶_{w} G′, where w is a splitting of G. This yields a weak flag path F ⟶_{u′} G with u′ ≺ u. Since ≺ is well-founded, this procedure stops with

a flag path F ⟶^{v} G for some word v ⪯ u. □

Notation. The notation s ⊂ t means that s is a subset of t, possibly with s = t. We will use the notation s ⊊ t to emphasise that s is a proper subset of t.

Definition 3.10.

• A word v = s_{1} ⋯ s_{n} is reduced if there is no pair i ≠ j such that s_{i} ⊂ s_{j} and s_{i} commutes with all letters in v between s_{i} and s_{j}.

• A flag path is reduced if its associated word is.

• The reduced word v is a reduct of u if it can obtained from u by the following rules

Commutation: Permute consecutive commuting letters.

Absorption: If s is contained in t, replace a subword s · t (or t · s) by t.

Splitting: Replace a subword s · s by a splitting of s.

We will denote this by u ⟶^{∗} v (cf. [2, Definition 5.24]). Clearly u ⟶^{∗} v implies v ⪯ u.

It is easy to see that a word u is reduced if and only if any permutation of u is. Similarly, a path P is reduced if and only if any permutation of P is.

Consider indexes i ≠ j in a word v = s_{1} ⋯ s_{n} such that s_{i} ⊂ s_{j} and s_{i} commutes with all letters in v between s_{i} and s_{j}. Using Commutation and Absorption, we can delete the occurrence of the letter s_{i}. If s_{i} = s_{j}, we may also replace s_{j} by a splitting of s_{j}. We call such an operation a generalised Absorption or Splitting. It is easy to see that every reduct of a word can be obtained by a sequence of generalised Absorptions and Splittings, followed by a permutation.

Lemma 3.11. If F ⟶^{u} G, then F ⟶^{v} G for some reduced v with u ⟶^{∗} v.

Proof. If the path F ⟶^{u} G is not reduced, possibly after permutation, we may assume that it contains a subpath F′ ⟶^{s} H′ ⟶^{t} G′, where s ⊂ t (or t ⊂ s). One of the following reduction steps now applies:

Proper Absorption: If s ⊊ t, remove H′ since F′ ⟶^{t} G′, for otherwise, there would be a a splitting x of t such that F′ ⟶_{x} G′, which implies

H′ ⟶_{s·x} G′, contradicting H′ ⟶^{t} G′.

Absorption/Splitting: If s = t, note that F′ ∼_{s} G′. Lemmata 3.4 and 3.9 yield:

Absorption: F′ ⟶^{s} G′, or

Splitting: F′ ⟶^{x} G′ for some splitting x of s. Therefore, the flag H′ can be removed.

Note that both Absorption and Splitting yield words which are ≺-smaller than u. Thus, the process must eventually stop. □

Remark 3.12. We will see in Remark 4.15 that, for every reduction u ⟶^{∗} v, there is a flag path of word u in a suitable Γ-space which can be reduced to a path with word v by the above procedure.

Corollary 3.13. Any two flags can be connected by a reduced path.

The following property of the ambient space will ensure that all reduced paths between two given flags have equivalent words (cf. Proposition 3.19).

Definition 3.14. A Γ-space M is simply connected if there are no non-trivial closed reduced flag paths.

Lemma 3.15. The Γ-space M is simply connected if and only if the word of any closed flag path can be reduced to the trivial word 1.

Proof. Suppose the condition on the right holds. Given a closed reduced flag path with word u, since u ⟶^{∗} 1, then u = 1, as u is already reduced. For the other direction, given a closed path P with word u, apply Lemma 3.11 to obtain a closed reduced path whose word v is a reduct of u. If M is simply connected, the word v must be 1, thus u ⟶^{∗} 1. □

Theorem 3.16. The Γ-space M_{0}(Γ) is simply connected.

Proof. By the definition of M_{0}(Γ), as explained in the proof of 2.17, two flags F and G in M_{0}(Γ) have the same γ-vertex if they can be connected by a flag path, whose letters are singletons different from γ. Thus, if F ⟶^{s} G, then s must be a singleton. All paths are singleton paths. Since B_{0}(Γ) is a building, there are no non-trivial closed reduced singleton paths. □

An interesting feature of simply connected Γ-spaces is that the word of a reduced flag path connecting two given flags is unique, up to equivalence. For the proof of the following proposition, we need a definition and a lemma.

Definition 3.17. The letter t is (properly) left-absorbed by the word s_{1} ⋯ s_{n}, resp. right-absorbed, if and only if t is (properly) contained in some s_{i} and commutes with s_{1} ⋯ s_{i−1}, resp. with s_{i+1} ⋯ s_{n}. A word u is left-absorbed, resp. right-absorbed, by v if each letter in u is.

A word is reduced if and only if it cannot be written as u · t · v, where t is either right-absorbed by u or left-absorbed by v. The word u = s_{1} ⋯ s_{n} left-absorbs t if and only if u^{−1} right-absorbs t, where u^{−1} = s_{n} ⋯ s_{1}.

Lemma 3.18. Let u · s be reduced and x be a splitting of s. Every reduct of u · x is equivalent to u · x_{1} for some x_{1} ⪯ x.

Proof. Since u · s is reduced, a generalised Absorption or Splitting for u · x cannot happen for a pair s_{i} ⊂ s_{j}, where s_{i} is contained in u. So letters contained in u will never be deleted. □

Proposition 3.19. If the flags F and G in a simply connected Γ-space M are connected by reduced flag paths with respective words u and v, then u ≈ v.

Proof. We prove it by ≺-induction on u and v. If F = G, the claim is equivalent to simple connectedness. We may therefore assume that F ≠ G. Since u · v^{−1} belongs to a closed non-trivial flag path, it cannot be a reduced word. So assume that u = u_{1} · s and s is right-absorbed by v. Splitting the first path accordingly,

F ⟶^{u_{1}} F_{1} ⟶^{s} G,

we distinguish two cases:

(1) The letter s is properly right-absorbed by v. Then v is the only reduct of v · s and therefore F ⟶^{v} G ⟶^{s} F_{1} gives F ⟶^{v} F_{1}.

\begin{matrix}F \\ F_{1} \\ G \\ u_{1} \\ s \\ v \\ v \end{matrix}

Since u_{1} ≺ u, induction yields that u_{1} ≈ v. In particular, the letter s is right-absorbed by u_{1}, contradicting that u is reduced.

(2) After a permutation v has the form v_{1} · s. We split the second path as

F ⟶^{v_{1}} G_{1} ⟶^{s} G.

We have then either G_{1} ⟶^{s} F_{1} or G_{1} ⟶^{x} F_{1} for a reduced splitting x of s. If G_{1} ⟶^{s} F_{1}, then F ⟶^{v} F_{1}, which contradicts as before that F ⟶^{u_{1}} F. So

G_{1} ⟶^{x} F_{1}.

\begin{matrix}F \\ F_{1} \\ G_{1} \\ G \\ u_{1} \\ s \\ v_{1} \\ s \\ x \end{matrix}

By Lemma 3.18 the path F ⟶^{v_{1}} G_{1} ⟶^{x} F_{1} reduces to a path F ⟶^{v_{1}·x_{1}} F_{1} with x_{1} ⪯ x. Since v_{1} · x_{1} ≺ v, induction yields that v_{1} · x_{1} ≈ u_{1}. So v_{1} · x_{1} · s ≈ u is reduced, which is only possible if x_{1} = 1. Whence v_{1} ≈ u_{1} and therefore v ≈ u.

□

Definition 3.20. Given F and G flags in a simply connected Γ-space A, we say that the word u connects F and G, if u is the word of a reduced path from F to G. Since u is uniquely determined up to equivalence we denote it by w_{A}(F, G)

In order to show that simple connectedness is an elementary property, we will first give a general description of a reduction of a flag path.

For i ≠ j, a pair of letters s_{i}, s_{j}, occurring in v is called reduced if either s_{i} and s_{j} are not comparable, or neither s_{i} nor s_{j} commute with all letters in between s_{i} and s_{j}. The word v is reduced if and only if all pairs of letters occurring in v are. A pair of two disjoint subwords w_{1} and w_{2} of a word v, possibly not reduced, is reduced in v if all pairs of letters s and t, where s occurs in w_{1} and t occurs in w_{2}, are reduced in v. By a sequence of generalised Absorptions and Splittings applied to letters in w_{1} and w_{2}, replace w_{1}, w_{2} by a pair w_{1}^{∗}, w_{2}^{∗}, which is reduced in the resulting word v^{∗}. We call such a process a reduction of w_{1}, w_{2} in v. If v is the word of a flag path, we call a corresponding transformation of the path also a reduction of w_{1}, w_{2}.

Lemma 3.21 (Reduction Lemma). Let w_{1}·w·w_{2} be the (possibly non-reduced) word of a flag path, where both w_{1} and w_{2} are reduced. Then there are words u_{1}, v_{1}, u_{2}, v_{2} and a reduction of w_{1}, w_{2} in the path with resulting word w_{1}^{∗} · w · w_{2}^{∗}, such that:

• w_{1} ≈ u_{1} · v_{1} and v_{2} · u_{2} ≈ w_{2},

• w_{1}^{∗} = u_{1} · x_{1} for some x_{1} ⪯ v_{1} and x_{2} · u_{2} = w_{2}^{∗} for some x_{2} ⪯ v_{2},

• v_{1} and v_{2} commute with w,

• |v_{1}| and |v_{2}| are contained in |w_{1}| ∩ |w_{2}|.

Proof. Since both w_{1} and w_{2} are reduced, we may assume that the words w_{1}^{∗} and w_{2}^{∗} are obtained by a sequence of generalised Absorptions and Splitting, each one involving a letter in the first word and a letter in the last word, where after every step we apply a reduction on both the first and the last word. It is enough to show by induction that, at every intermediate step of the reduction, the word w′_{1} · w · w′_{2} satisfies the conclusion of the lemma. Start by setting u_{j} = w_{j} and v_{j} = x_{j} the empty word, for j = 1, 2. Assume that u_{1}, v_{1}, x_{1}, v_{2}, u_{2}, x_{2} witness this at the i^{th} step. In particular w′_{1} = u_{1} · x_{1} and x_{2} · u_{2} = w′_{2}, where x_{i} ⪯ v_{i} for i = 1, 2.

We will treat the case of a generalised Splitting and leave to the reader the easier case of a generalised Absorption. Suppose hence that w′′_{1} · w · w′′_{2} is obtained from w′_{1} · w · w′_{2} by a generalised Splitting followed by a reduction of the first and last word. Then there is a letter s occurring both in w′_{1} and w′_{2}, which commutes with w as well as with the letters of w′_{1} on its right (resp. the letters of w′_{2} on its left). Suppose furthermore that the word w′′_{1} is obtained from w′_{1} by deleting s. Note that w′′_{1} is reduced.

The word w′′_{2} is obtained from w′_{2} by replacing s by a splitting y of s followed by a further reduction. By Lemma 3.18, we may assume that w′′_{2} is reduced and obtained, up to a permutation, by replacing s with some word y_{2} ⪯ y ≺ s. If s occurred in u_{2}, then set u′_{2} the word obtained by removing s from u_{2} as well as v′_{2} = v_{2} · s and x′_{2} = x_{2} · y_{2}. If s occurred in x_{2}, then replace s by y_{2} and leave v_{2} and u_{2} unchanged.

Likewise, modify the words u_{1}, v_{1} and x_{1} accordingly. □

Definition 3.22. Given a letter s and a natural number n, the reduced word w satisfies E(s, n) if |w| ⊂ s and no permutation of w is a product of n many words u_{i}, with |u_{i}| ⊊ s.

The properties E(s, n) get stronger as n increases. In particular, the word w satisfies E(s, 0) if and only if |w| ⊂ s and w ≠ 1. Similarly, the word w satisfies E(s, 1) if and only if |w| = s.

Corollary 3.23. Let u = s_{1} ⋯ s_{n} be a reduced word and w_{1}, …, w_{n} reduced words with |w_{k}| = s_{k}. Consider two indices i < j and a reduction w_{i}^{∗}, w_{j}^{∗} of the pair w_{i}, w_{j} in w_{i} ⋯ w_{j} as in the Reduction Lemma 3.21. Then the following holds

(1) If w_{i} satisfies E(s_{i}, m) for some m > 0, then w_{i}^{∗} satisfies E(s_{i}, m−1), similarly for w_{j} and w_{j}^{∗}.

(2) Assume that w_{i} and w_{j} satisfy E(s_{i}, 2) and E(s_{j}, 2), respectively. If a pair w_{i′}, w_{j′} is already reduced in w = w_{1} ⋯ w_{n}, then the corresponding pair remains reduced in w^{∗} = w_{1} ⋯ w_{i}^{∗} ⋯ w_{j}^{∗} ⋯ w_{n}.

Proof. In order to prove (1), choose u_{i}, v_{i}, x_{i}, u_{j}, v_{j}, x_{j} as in the Reduction Lemma. Since |v_{i}| is contained in s_{i} ∩ s_{j} and v_{i} commutes with s_{i+1} ⋯ s_{j−1}, then |v_{i}| is a proper subset of s_{i}, for otherwise the pair s_{i}, s_{j} would not be reduced in u. As w_{i} ≈ u_{i} · v_{i}, if w_{i} has property E(s_{i}, m), then u_{i} has property E(s_{i}, m − 1), and so does w_{i}^{∗}.

For (2), assume that w_{i} and w_{j} satisfy E(s_{i}, 2) and E(s_{j}, 2), respectively. Therefore w_{i}^{∗} and w_{j}^{∗} have property E(s_{i}, 1) and E(s_{j}, 1), respectively, so |w_{i}^{∗}| = s_{i} and |w_{j}^{∗}| = s_{j}. Suppose now that the pair w_{i′}, w_{j′} is reduced in w. Since the words w_{i}^{∗} and w_{j}^{∗} commute with the same letters as w_{i} and w_{j}, respectively, the pair w_{i′}, w_{j′} remains reduced in w^{∗} if {i′, j′} and {i, j} are disjoint. By symmetry, it suffices to consider the following three other cases:

Case i′ < j′ = i. We have to show that the pair w_{i′}, u_{i} · x_{i} is reduced in w^{∗} if the pair w_{i′}, u_{i} · v_{i} is reduced in w. This follows easily from |x_{i}| ⊂ s_{i} = |u_{i}|, since w_{i} satisfies E(s_{i}, 2).

Case i = i′ < j′ < j. Here we have to show that the pair u_{i} · x_{i}, w_{j′} is reduced in w^{∗} if the pair u_{i} · v_{i}, w_{j′} is reduced in w. This follows easily from the fact that v_{i} and x_{i} commute with w_{j′}.

Case i = i′ < j < j′. Again we have to show that the pair u_{i} ·x_{i}, w_{j′} is reduced in w^{∗} if the pair u_{i}·v_{i}, w_{j′} is reduced in w. This follows easily from |x_{i}|, |v_{i}|, |v_{j}| ⊂ |u_{j}|.

□

Proposition 3.24. Let u = s_{1} ⋯ s_{n} be a reduced word. Given reduced flag paths F_{i−1} ⟶^{w_{i}} F_{i} such that each w_{i} has property E(s_{i}, n), then the path

F_{0} ⟶^{w_{1}} F_{1} ⋯ F_{n−1} ⟶^{w_{n}} F_{n}

has a reduction of length ≥ n.

Proof. Choose any enumeration of all pairs i < j of indices between 1 and n and apply the Reduction Lemma to each pair in order. Observe that k occurs in at most n − 1 reductions. At every step of the reduction, the resulting words satisfy E(s_{k}, 2), so the resulting path

F_{0} ⟶^{w_{1}^{∗}} F_{1}^{∗} ⋯ F_{n−1}^{∗} ⟶^{w_{n}^{∗}} F_{n},

is reduced, by Corollary 3.23 (2). None of the words w_{i}^{∗} is trivial, by Corollary 3.23 (1).

□

Together with Remark 4.15, the previous proposition will imply the following (a priori) stronger form.

Remark 3.25. Let u = s_{1} ⋯ s_{n} be a reduced word and w_{1}, …, w_{n} reduced words with property E(s_{i}, n). Then every reduct of w_{1} ⋯ w_{n} has length at least n.

Theorem 3.26. Simple connectedness is an elementary property for Γ-spaces.

Proof. For each natural number n and letter s, consider the following elementary property of two given flags F and G: Though F ∼_{s} G, there exist no proper subsets A_{1}, …, A_{n} of s and flags F_{1}, …, F_{n−1} such that

F ∼_{A_{1}} F_{1} ∼_{A_{2}} ⋯ ∼_{A_{n−1}} F_{n−1} ∼_{A_{n}} G.

We denote this by F ⟶^{s,n} G. Observe that, if F ⟶^{s,n} G, then there is a path F ⟶^{w} G for some reduced w, which satisfies property E(s, n). Indeed, since F ∼_{s} G, there exists a reduced word w with support contained in s connecting F to G. Any such word satisfies E(s, n).

If suffices hence to show that a Γ-space M is simply connected if and only if for all natural numbers n and all non-trivial reduced words u = s_{1} ⋯ s_{n}, there is no

sequence F_{0} ⟶^{s_{1},n} F_{1} ⋯ F_{n−1} ⟶^{s_{n},n} F_{n} = F_{0}.

Clearly, right-to-left is obvious, since F ⟶^{s} G implies F ⟶^{s,n} G, by Lemma 3.4. Suppose now that M is simply connected and let F_{0} ⟶^{s_{1},n} F_{1} ⋯ F_{n−1} ⟶^{s_{n},n} F_{n} be a weak flag path for some non-trivial reduced word u = s_{1} ⋯ s_{n}. By the above discussion, there are words w_{i}, each satisfying property E(s_{i}, n), respectively, such that

F_{0} ⟶^{w_{1}} F_{1} ⋯ F_{n−1} ⟶^{w_{n}} F_{n}

Proposition 3.24 yields that this path has a reduction of length at least n, so F_{0} ≠ F_{n}, since M is simply connected. □

Simple connectedness allows us to generalise [2, Remark 4.9], which will be needed for the proof of Proposition 4.7.

Lemma 3.27. Given two adjacent colours γ and δ, if M is a simply connected Γ-space, the subgraph A_{γ,δ}(M) = A_{γ}(M) ∪ A_{δ}(M) has no non-trivial circles.

Proof. Since any edge in A_{γ,δ} lies within a flag in M, by property (2) of Definition 2.16, a path with no repetitions in A_{γ,δ} induces a (possibly non-reduced) flag path of the form

F_{0} ⟶^{w_{1}} F_{1} ⟶^{w_{2}} ⋯ F_{n},

where the reduced words w_{1}, …, w_{n} have the following properties:

(a) δ ∈ |w_{2k+1}| ⊂ Γ \ {γ},
(b) γ ∈ |w_{2k}| ⊂ Γ \ {δ}.

By repeatedly applying Lemma 3.21 to each pair w_{i}, w_{j} for i ≠ j, it is easy to see that the above conditions remain in the reduct w_{1}^{∗} ⋯ w_{n}^{∗} of the word w_{1} ⋯ w_{n}. In particular, the word w_{1}^{∗} ⋯ w_{n}^{∗} is not trivial and thus F_{0} ≠ F_{n}. Hence, the original path in A_{γ,δ} was not closed.

□

4. The Theory PS_{Γ}

Definition 4.1. In the language of graphs enriched with unary predicates for the colours {A_{γ}}_{γ∈Γ}, let the theory PS_{Γ} be a collection of sentences stating that the structure is a Γ-space with the following properties:

(1) simple connectedness,

(2) for any colour γ in Γ, the ∼_{γ}-class of any flag G is infinite (Observe that the relation ∼_{γ} is definable in this language).

Axiom (1) is a first-order property, by Theorem 3.26. Clearly, so is Axiom (2). The Γ-space M_{0}(Γ), as defined on page 10, is a model of PS_{Γ} by Theorem 3.16, so PS_{Γ} is consistent.

The rest of this section is devoted to proving the completeness of PS_{Γ}.

We first generalise [2, Definition 4.3].

Definition 4.2. Fix some letter s, and let F be a flag in a Γ-graph A. Create a new flag F^{∗} = {f_{γ}^{∗}}_{γ∈Γ} which agrees with F on the colours of Γ \ s but f_{γ}^{∗} ∉ A for γ ∈ s. We define a Γ-graph

A(F^{∗})

with vertices A ∪ F^{∗} and edges those of A and of F^{∗}. A Γ-graph B ⊃ A is a simple extension of A of type s, F if it is A-isomorphic to A(F^{∗}).

Note that F^{∗} ⟶_{s} F by construction.

Remark 4.3. If A is a Γ-space, then so is A(F^{∗}).

These simple extensions generalise those simple extensions defined after Remark 2.7, as the following easy remark shows.

Remark 4.4. Let ∂s = s ∪ {δ ∈ Γ | adjacent to some γ ∈ s} denote the set of all γ in Γ which do not commute with s. Let H be a flag in A which agrees with F on the colours in ∂s. For each γ ∈ s, replace h_{γ} in H by f_{γ}^{∗} in order to obtain a flag H^{∗} of A(F^{∗}). It is easy to see, since s is connected, that that this construction defines a a 1-to-1-correspondence between the flags H of A with H ∼_{Γ\∂s} F and the new flags H^{∗} of A(F^{∗}). Note that H^{∗} is uniquely determined by

H^{∗} ∼_{Γ\∂s} F^{∗} and H^{∗} ∼_{s} H.

In order to prove that the theory PS_{Γ} is complete, we will need the appropriate interpretation of a strongly connected subset in this context.

Definition 4.5. A non-empty subgraph D of a Γ-space M is nice if it satisfies the following conditions:

• Any point a in D lies in a flag in D.

• Given flags F and G in D and a letter s, if F ⟶^{s} G in D, then F ⟶^{s} G in M.

Any nice set is the union of all the flags contained in it. Niceness is a transitive property. Proposition 3.19 yields that a non-empty subset D of a simply connected Γ-space M is nice if and only if the following hold:

• Any point a in D lies in a flag in D.

• Given flags F and G in D and a reduced word u, if F ⟶^{u} G in M, then

there exists such a path in D with the same word. In particular, if D is nice in M, then D is simply connected whenever M is.

Remark 4.6. (1) The Γ-space A is nice in A(F^{∗}).

(2) A nice subset of a Γ-space is itself a Γ-space.

Proof. For (1), given flags G and H in A with G ⟶^{t} H in A, suppose there is a splitting x = t_{1} ⋯ t_{n} of t such that

G = F_{0} ⟶_{t_{1}} F_{1} ⋯ F_{n−1} ⟶_{t_{n}} F_{n} = H

in A(F^{∗}). We replace each F_{i} by a flag F′_{i} in A as follows: If F_{i} belongs to A, set F′_{i} = F_{i}. Otherwise, by Remark 4.4, the flag F_{i} has the form H_{i}^{∗} and we set F′_{i} = H_{i}. Note that F′_{i−1} ∼_{t_{i}} F′_{i}, so G and H can be connected in A be a weak flag path whose word is ⪯-smaller than t_{1} ⋯ t_{n}, contradicting G ⟶^{t} H. In order to show (2), consider two elements a and b in a nice subset A of M, connected by a flag G in M. Choose flags F and H in A containing a and b respectively. Let γ be the colour of a and δ the colour of b. Since F ∼_{Γ\{γ}} G ∼_{Γ\{δ}} H, there is a reduced path F ⟶^{u} G′ ⟶^{v} H in M such that γ does not occur in u and δ does not occur in v. By niceness, we may therefore assume that G′ belongs to A. Clearly G′ contains a and b. □

We can now prove the analogue version of [2, Lemma 4.21].

Proposition 4.7. Given a flag F in a nice subset A of a simply connected Γ-space M, and a flag F^{∗} in M which is s-equivalent to F for some letter s, the following are equivalent:

(a) The Γ-graph A ∪ F^{∗} is a simple extension of A of type s, F and is nice in M.

(b) Whenever G is a flag in A and x a splitting of s, then F^{∗} −̸ →_{x} G in M.

Proof. (a) → (b): Set B = A ∪ F^{∗}. If

F^{∗} ⟶_{x} G

in M, then we cannot have that F^{∗} ⟶^{s} G in B, for B is nice. Thus, there is a splitting x′ of s such that F^{∗} ⟶^{x′} G in B. All flags in B which are s-equivalent to F are either F^{∗} itself or contained in A, by Remark 4.4, so F^{∗} ∼_{t} G′ for some G′ in A, where t ⊊ s is the first letter of x′. This is impossible, for no vertex of F^{∗} with colour in s lies in A.

(b) → (a): Since F lies in A, the hypothesis implies that F^{∗} ⟶^{s} F. We will first show that, for any flag G in A, if F^{∗} ⟶^{u} G in M, then s ⪯ u. We may assume that u is reduced. Since A is nice, there is a reduced path connecting F ⟶^{v} G in A, which remains reduced in M. The word u is thus a reduct of s · v. If in the reduction splitting ever occurs, it produces a flag in A which connects to F^{∗} by a splitting of s, contradicting the assumption. Thus, the reduction involves only commutation and possibly absorption of s by u. Hence s ⪯ u.

In particular, for any flag G in A with F^{∗} ⟶^{u} G, there exists a letter t in u containing s. Actually, by Lemma 3.9 it suffices to assume F^{∗} ⟶_{u} G.

In order to show that B = A ∪ F^{∗} is a simple extension of A, we need to show that there is no new edge consisting of an element b in A_{γ}(B) \ A and some a in A_{δ}(A) \ F. Suppose otherwise that there exists a flag F′ in M passing through a and b. Take a flag G in A containing a.

Note that γ is in s. Suppose first that δ lies in s as well. Since F^{∗} ∼_{Γ\{γ}} F′ ∼_{Γ\{δ}} G, we obtain reduced words u and v such that γ does not occur in u, the colour δ does not occur in v and

F^{∗} ⟶^{u} F′ ⟶^{v} G.

The reduction F^{∗} ⟶^{w} G in M satisfies that every letter in w does not contain either γ or δ, contradicting the previous discussion.

If δ does not lie in s, then, with the choice of flags as before, we obtain the following path

F ⟶^{s} F^{∗} ⟶^{u} F′ ⟶^{v} G

As before, since A is nice, this implies that F ⟶^{w} G in A, where each letter in w avoids either γ or δ. This induces a path in A_{γ,δ}(A) between a′ and a, where a′ is the δ-vertex of F. This, together with the connection a − b − a′, yields a non-trivial circle, contradicting Lemma 3.27.

Let us now show that B is nice in M. Given flags G_{1} ⟶^{t} G_{2} in B, we distinguish the following cases:

• Both flags lie in A. Then G_{1} ⟶^{t} G_{2} also in A, and thus in M, since A is nice.

• None of the flags lies in A. By Remark 4.4, we have G_{1} ∼_{Γ\∂s} G_{2} and whence t ⊂ Γ \ ∂s. Thus we find H_{1} and H_{2} in A such that H_{1} ∼_{Γ\∂s} H_{2} and G_{i} ∼_{s} H_{i} for i = 1, 2. This implies H_{1} ⟶^{t} H_{2} in B and also in A. Therefore H_{1} ⟶^{t} H_{2} in M, for A is nice, which implies that G_{1} ⟶^{t} G_{2} in M as well.

• Exactly one flag, say G_{1}, is not fully contained in A. Again by Remark 4.4, we have that F^{∗} ⟶^{w} G_{1} for a word w which commutes with s and a flag H_{1} in A with G_{1} ⟶_{s} H_{1}. Since F^{∗} ⟶_{w·t} G_{2}, some letter of w · t must

contain s, so s ⊂ t. If s = t but G_{1} ⟶^{x} G_{2} in M for some x ≺ t = s, then F^{∗} ⟶^{w} G_{1} ⟶^{x} G_{2} in M, whose reduction yields a word where no letter contains s. Thus G_{1} ⟶^{t} G_{2} in M. Otherwise, if s ⊊ t, then H_{1} ⟶^{t} G_{2} in B. Since A is nice, we have H_{1} ⟶^{t} G_{2} in M, which implies G_{1} ⟶^{t} G_{2} in M.

□

In particular, setting s = {γ}, for γ in Γ, we deduce the following result.

Corollary 4.8. Given a flag G in a nice subset A of a simply connected Γ-space M and γ in Γ, if the flag F is {γ}-equivalent to G and the γ-vertex of F does not lie in A, then the set B = A ∪ F is nice and a simple extension of A of type {γ}, G.

The next proposition shows that a simply connected space is the increasing union of simple extensions of nice subsets. sets (cf. [2, Theorem 4.22]).

Proposition 4.9. Given a nice subset A of a simply connected Γ-space M and b in M, there exists a nice subset B containing b which can be obtained from A by a finite number of simple extensions.

Proof. Given a flag F in M containing b, choose a reduced path

F = F_{0} ⟶^{s_{1}} F_{1} ⋯ ⟶^{s_{n}} F_{n}

connecting F with a flag F_{n} in A such that the word u = s_{1} ⋯ s_{n} is ≺-minimal. We prove the claim by ≺-induction on u. If u = 1, there is nothing to show. Otherwise, minimality of u implies that there is no path which connect F_{n−1} to a flag in A whose word is a splitting of s_{n}. It follows from Proposition 4.7 that A′ = A∪F_{n−1} is a simple extension of A of type s_{n}, F_{n}, so A′ is nice in M. Now F can be connected to some flag in A′ by a reduced word path, whose word u′ is ≺-minimal such, with u′ ⪯ s_{1} ⋯ s_{n−1} ≺ u. By induction, the element b is contained in a nice set B which can be obtained from A′ (and thus, from A) by a finite number of simple extensions. □

Lemma 4.10. Let s be a letter in Γ which is not a singleton. There are γ and γ′ in s distinct such that both s \ {γ} and s \ {γ′} are connected.

Proof. By repeatedly removing edges, it is enough to prove it for a spanning tree s, that is, whenever we remove an edge between two points in s, the resulting graph is no longer connected. In particular, such an s contains no cycles. The assertion now follows, since any non-trivial tree has at least two extremal points. □

Corollary 4.11. Given a letter s and a flag G contained in some finite nice subset A of an ω-saturated model M of PS_{Γ}, then M contains a simple extension of A of type s, G which is nice in M.

Proof. For s = {γ}, pick any flag G^{∗} which is γ-equivalent to G and its γ-vertex does not lie in (the finite set) A, by property (2). The set A ∪ G^{∗} is nice in M and a simple of A type s, G, by Corollary 4.8.

Suppose now that |s| ≥ 2. By Proposition 4.7 and saturation, it is enough to produce, for every n, a flag G_{n} with G_{n} ⟶_{s} G and G_{n} −̸ →_{x} G′, whenever G′ is a flag in A and x a splitting of s of length at most n.

By Lemma 4.10, find two subletters s_{0} and s_{1} of s of cardinality |s| − 1 and not commuting with each other. Since A contains only finitely many flags, simple connectedness yields an upper bound N for the length of the word of any reduced flag path between any two flags in A. Set A_{0} = A and G_{0} = G. By induction on |s|, there is a sequence of pairs {(G_{i}, A_{i})}_{i≤N+n} such that G_{i} is a flag in the (finite) nice set A_{i} and A_{i+1} = A_{i} ∪ G_{i+1} is a simple extension of type s_{f(i)}, G_{i}, where f(i) in {0, 1} is the residue of i modulo 2. The flag path

G_{N+n+1} ⟶^{s_{f(N+n)}} G_{N+n} ⋯ G_{1} ⟶^{s_{0}} G_{0}

is reduced, since s_{0} and s_{1} do not commute.

Clearly G_{N+n+1} ⟶_{s} G_{0}. Suppose there is some flag G′ in A such that

G_{N+n+1} ⟶_{x} G′

in A for some splitting x of s of length at most n. Reducing this path, we obtain a reduced path G′ ⟶^{u} G, where u is also a splitting of s. By niceness of A, we may assume that this path lies in A, so u has length at most N. Proposition 3.19 implies that x · u ⟶^{∗} s_{f(N+n)} ⋯ s_{0}. However, at every step of the reduction, the number of letters of size exactly |s| − 1 is bounded by N + n, contradicting our choice of s_{f(N+n)} ⋯ s_{0}. □

We can now conclude that the theory PS_{Γ} is complete and that the type of a nice set is determined by its quantifier-free type.

Theorem 4.12. Any two ω-saturated models of PS_{Γ} have the back-and-forth property with respect to the collection of partial isomorphisms between finite nice substructures. In particular, any partial isomorphism f : A → A′ between two finite nice subsets of two models of PS_{Γ} is elementary. The theory PS_{Γ} is complete.

Proof. Let M and M′ be two ω-saturated models and let f : A → A′ be a partial isomorphism between two finite nice substructures. Given b in M, Proposition 4.9 yields a nice subset B containing A ∪ {b} such that A ≤ B in finitely many steps. By ω-saturation of M′ and Corollary 4.11 (finitely many times), we obtain a nice subset B′ of M′ containing A′ such that f extends to isomorphism between B and B′.

Since any model M is nice in any elementary extension, replacing the models by appropriate saturated extensions, we produce a back-and forth system. Completeness of PS_{Γ} then follows, since any two flags have the same quantifier-free type. □

Corollary 4.13. The type of a nice set A is determined by its quantifier-free type.

Proof. For finite sets, this follows from Theorem 4.12. For infinite nice sets, note that they are direct unions of finite nice subsets. □

Corollary 4.14. The theory PS_{Γ} is ω-stable and the model M_{0}(Γ) is the unique (up to isomorphism) countable prime model.

Proof. In order to show that PS_{Γ} is ω-stable, we need to count 1-types over a countable subset of A, which we may assume nice inside a given saturated model (cf. [16, Theorem 5.2.6]). Every simple extension of A is uniquely determined, up to A-isomorphism, by its type s, G, by Corollary 4.13. Therefore, if A is countable, there are, up to A-isomorphism, only countably many simple extensions. Now, every 1-type is realised in a finite tower of simple extensions over A, by Proposition 4.9, so there are only countably many types, as desired.

In order to show that the countable model M_{0}(Γ) is the the prime model of PS_{Γ}, it suffices to show that it is constructible. It follows from the proof of Theorem 3.16 that the only words of reduced paths in M_{0}(Γ) are finite products of singletons. Given γ in Γ and a flag G in a nice subset A, the type over A of the simple extension B = A ∪ F of type {γ}, G is determined by its quantifier-free type, which amounts to saying, by Corollary 4.8, that F and G are γ-equivalent but that the γ-vertex of F does not lie in A. Therefore, if A is finite, the type of B over A is isolated. □

Uniqueness of prime models and Theorem 2.17 yield the uniqueness result in Corollary 2.11.

Remark 4.15. Let M be an ω-saturated model of PS_{Γ}. For every word v, there is a path F ⟶^{v} G in M. Whenever a (possibly non-reduced) word u can be reduced to v, then there is a flag path from F to G with word u.

5. Non-splitting reductions

In order to describe the geometrical complexity of PS_{Γ}, we will need several auxiliary results on the combinatorics of reduction of words when no splitting occurs, generalising some of the results of [2]. For the sake of self-containment, we will provide, whenever possible, different proofs.

Definition 5.1. A letter s is a beginning (resp. end) of the word u if u ≈ s · v (resp. u ≈ v · s). The initial segment (resp. final segment) of u is the commuting subword whose letters are beginnings (resp. ends) of u.

By abuse of the language, we say that the word u is an initial subword of v if u is an initial subword (in the proper sense) of some permutation of v. Likewise for final subword. The initial segment of v is the largest commuting initial subword of v. Inductively on the sum of their lengths, it is easy to see that any two words u and v have a largest common initial subword, resp. a largest common final subword, none of which need be commutative.

Common initial subwords can be removed, as seen easily.

Lemma 5.2. If u·v′ ≈ u·v′′, then v′ ≈ v′′. Likewise, if v′ ·u ≈ v′′ ·u, then v′ ≈ v′′.

Lemma 5.3. Let a be a final subword of c · d such that every end of a commutes with d. Then a and d commute and a is a final subword of c.

Proof. Proceed by induction on the length of a. If a is the trivial word, there is nothing to show. Otherwise, write a = s · a_{1}. By induction, the subword a_{1} commutes with d and is a final subword of c ≈ c′ · a_{1}. Since c · d ≈ c′ · d · a_{1}, Lemma 5.2 implies that s is an end of c′ · d.

If s occurs in d, then s and a_{1} commute, so s is an end of a and hence it must commute with d, by hypothesis, which is a contradiction, since no letter commutes with itself. Therefore, the letter s must occur in c′, so in particular it must commute with d. Thus, the word a commutes with d and is a final subword of c, as desired. □

Definition 5.4. A non-splitting reduction of the word u, denoted by u → v, is a reduced word v obtained from u by a reduction process, where only Commutation and Absorption occur (cf. Definition 3.10).

By induction on the length of the reduction u → v, the following can be easily shown.

Lemma 5.5. If v is a non-splitting reduction of u, then every u′ ⪯ u has a nonsplitting reduction v′ ⪯ v.

Corollary 5.6 (cf. [2, Corollary 5.3]). Every word admits exactly one non-splitting reduction, up to permutation.

Proof. Assume that v_{1} and v are two non-splitting reducts of u. In particular v_{1} ⪯ u, so v_{1} → v′ for some v′ ⪯ v, by Lemma 5.5. Thus v′ must be equivalent to v_{1}, and hence v_{1} ⪯ v. Similarly, we obtain v ⪯ v_{1}, so v_{1} ≈ v. □

Notation. Given reduced words u and v, we denote by [u · v] the non-splitting reduct of u · v, which is defined up to permutation.

Corollary 5.7 (cf. [2, Lemma 5.29]). Given reduced words u, v and x with x ⪯ v, then [u · x] ⪯ [u · v].

Corollary 5.8. If u and v are reduced words, then u ⪯ [u · v]. □

Recall (cf. Definition 3.17) that a letter t is properly left-absorbed, resp. rightabsorbed, by the word s_{1} ⋯ s_{n} if and only if t is properly contained in some s_{i} and commutes with s_{1} ⋯ s_{i−1}, resp. with s_{i+1} ⋯ s_{n}.

Proposition 5.9. (Symmetric Decomposition Lemma, cf. [2, Corollary 5.23]) Given two reduced words u and v, there are unique decompositions (up to permutation):

u = u_{1} · u′ · w  w · v′ · v_{1} = v,

such that:

(a) w is a commuting word,

(b) u′ is properly left-absorbed by v_{1},

(c) v′ is properly right-absorbed by u_{1},

(d) u′, w and v′ pairwise commute,

(e) u_{1} · w · v_{1} is reduced. Furthermore,

[u · v] = u_{1} · w · v_{1}.

Proof. We show the existence of such a decomposition by induction on the sum of the lengths of u and v. If u · v is already reduced, then set u_{1} = u and v_{1} = v, and define v′, u′ and w to be the trivial word.

Otherwise, up to permutation and changing the roles of u and v , we may assume that u = ũ · s, where s is left-absorbed by v. In particular [s · v] = v. By induction, we find words ũ_{1}, ũ′, w̃, ṽ′ and ṽ_{1} with the desired properties such that

ũ = u_{1} · ũ′ · w̃  w̃ · v′ · ṽ_{1} = v.

Observe that s cannot be left-absorbed by w̃ nor by ṽ′, for u is reduced. Thus s commutes with w̃ · ṽ′ and is absorbed by ṽ_{1}. There are two possibilities:

(1) The letter s is properly absorbed by ṽ_{1}. Set u′ = ũ′ · s, w = w̃ and v_{1} = ṽ_{1}.

(2) Up to permutation, the letter s is a beginning of ṽ_{1} = s · v_{1}^{∗}. Set u′ = ũ′,

w = w̃ · s and v_{1} = v_{1}^{∗}.

Let us finish by showing the uniqueness of the above decomposition. Note first that [u·v] = u_{1} ·w·v_{1}, since u·v → u_{1} ·w·v_{1}. The word w is exactly the intersection of the final segments of u and v^{−1}, since u_{1} · w · v_{1} is reduced. Furthermore, the word u_{1}·w is the largest common initial subword of u and [u, v], for otherwise, there exists a letter s with v_{1} = s · ṽ_{1} and u′ = s · ũ′, contradicting that u′ is properly left-absorbed by v_{1}. Similarly, the word w · v_{1} is the largest common final subword of v and [u, v], providing the desired result. □

Corollary 5.10 (cf. [2, Corollary 5.14]). Let u and v be reduced words. Then u is left-absorbed by v if and only if [u · v] = v.

Proof. Note that [u · v] = v if and only if u_{1} · w · v_{1} ≈ v′ · w · v_{1}. Lemma 5.2 implies u_{1} ≈ v′. So u_{1} is properly right-absorbed by itself, which can only happen if u_{1} = 1. Thus u ≈ u′ · w is left-absorbed by v. □

Corollary 5.11 (cf. [2, Corollary 5.22]). A reduced word is commuting if and only if it left-absorbs itself.

Proof. Suppose first that we have two reduced words u and v, such that u rightabsorbs v and v left-absorbs u. The proof of 5.10 yields both u_{1} = v′ = 1 = v_{1} = u′, so u = v = w is commuting. The statement now follows easily, since Corollary 5.10 yields that if u left-absorbs itself, then it also right-absorbs itself. □

Corollary 5.12. If the reduced word u is left-absorbed by the reduced word v, we can write (up to permutation) :

u = u′ · w  w · v_{1} = v,

such that (1) w is a commuting word,

(2) u′ is properly left-absorbed by v_{1},

(3) u′ and w commute.

□

Corollary 5.13. Given reduced words u, v and x such that [u · v] = u · x, then x is a final subword of v. In particular, the word x commutes with any word commuting with v.

Proof. Decompose

u = u_{1} · u′ · w  w · v′ · v_{1} = v,

as in Proposition 5.9. Hence u_{1} · w · v_{1} = [u · v] = u_{1} · w · u′ · x, so v_{1} ≈ u′ · x, by Lemma 5.2. Thus u′ = 1 and x is a final subword of v, as desired. □

Lemma 5.14. If the reduced word u is left-absorbed by v_{1} · v_{2}, then u ≈ u_{1} · u_{2}, where each u_{i} is left-absorbed by v_{i}, and u_{2} commutes with v_{1} (and therefore with u_{1}).

Proof. If u is empty, there is nothing to show. Otherwise, write u = u′ · s. By induction on the length of u, obtain a decomposition u′ ≈ u′_{1} · u′_{2}, such that u′_{i} is absorbed by v_{i} and u′_{2} commutes with v_{1}. We distinguish two cases: If s is absorbed by v_{1}, then u′_{2} commutes with s, so decompose u ≈ (u′_{1} · s) · u′_{2}. Otherwise, the letter s commutes with v_{1} and is left-absorbed by v_{2}. Set u ≈ u_{1} · (u_{2} · s). □

Corollary 5.15. Given a reduced word u ≈ u_{1}·ũ, where ũ denotes the final segment of u, then [u · u^{−1}] = u_{1} · ũ · u_{1}^{−1}.

Proof. It suffices to show that the word u_{1} · ũ · u_{1}^{−1} is reduced. Otherwise, there is an end s of u_{1} which commutes with ũ. In that case, the letter s is an end of u and hence it occurs in ũ, which is a contradiction. □

For the proof of the next lemma, we will require the following notation: Recall (cf. Remark 4.4) that Γ \ ∂s is the set of those colours commuting with s. For a letter t, denote by C_{t}(s) the commuting word with support t \ ∂s (cf. Remark 3.2). For a word v = t_{1} ⋯ t_{n}, set

C_{v}(s) = C_{t_{1}}(s) ⋯ C_{t_{n}}(s).

Lemma 5.16. (Division Lemma) Given reduced words u ⪯ v, there exists a reduced word w, unique up to permutation, such that for every reduced word x,

[x · u] ⪯ v ⇔ x ⪯ w.

We denote it by v/u. Since v/u ⪯ v/u, Corollary 5.8 implies that v/u ⪯ v. Furthermore, since 1 ⪯ v/u, the condition u ⪯ v is necessary for the existence of v/u.

Proof. Note that we may assume that u consists of a single letter: given u = u_{1}·u_{2}, suppose that the statement holds for both u_{1} and u_{2}. Since u ⪯ v, we have u_{2} ⪯ v, so v/u_{2} exists. Now u_{1} · u_{2} ⪯ v implies u_{1} ⪯ v/u_{2}. Thus, set v/u = (v/u_{2})/u_{1}, which exists. Note that

[x · u] = [[x · u_{1}] · u_{2}] ⪯ v ⇔ [x · u_{1}] ⪯ v/u_{2} ⇔ x ⪯ v/u,

as desired. Therefore, assume u = s ⪯ v.

We can write v = v_{1} · t · v_{2}, such that s ⊂ t and no letter in v_{2} contains s. Set w = [v_{1} · t · C_{v_{2}}(s)]. No letter in v_{1} · t is left-absorbed during the non-splitting reduction v_{1} · t · C_{v_{2}}(s) → w, for v is reduced.

Clearly [w · s] = w ⪯ v. Given x ⪯ w reduced, Corollary 5.7 implies that [x·s] ⪯ [w·s] ⪯ v, which gives one implication. For the other, assume that [x·s] ⪯ v. We distinguish two cases : if s is absorbed by x, then x = [x·s] ⪯ v = v_{1}·t·v_{2}, so we may decompose x ≈ x_{1} · x_{2}, where x_{1} ⪯ v_{1} · t· and x_{2} ⪯ v_{2}. Since x_{2} does not rightabsorb s, Lemma 5.14 implies that x_{2} commutes with s, which is right-absorbed by x_{1}. This implies x_{2} ⪯ C_{v_{2}}(s) and thus x ⪯ w.

If s is not absorbed by x, then Proposition 5.9 yields a decomposition x ≈ x_{1} ·x′, where x′ is properly absorbed by s and [x · s] = x_{1} · s. The word x_{1} · s rightabsorbs s, so x_{1} · s ⪯ w by the previous discussion. Since x′ ≺ s, we conclude that x ≈ x_{1} · x′ ⪯ w, as desired. □

Definition 5.17. According to Lemma 5.16, we denote by S_{R}(u) the largest reduced word, unique up to permutation, such that for every reduced word x,

[u · x] ⪯ u ⇔ x ⪯ S_{R}(u).

Corollary 5.18. Given a reduced word u, the word S_{R}(u) ⪯ u is commutative. A reduced word x is right-absorbed by u if and only if x ⪯ S_{R}(u).

In particular, if ũ denotes the final segment of u, then ũ ⪯ S_{R}(u).

Proof. Note that x is right-absorbed by u if and only if [u·x] = u. Since u ⪯ [u·x], by Corollary 5.8, this is equivalent to [u · x] ⪯ u, that is x ⪯ S_{R}(u).

In particular, the word S_{R}(u) is right-absorbed by u. Thus [u · [S_{R}(u) · S_{R}(u)]] = [[u · S_{R}(u)] · S_{R}(u)] = [u · S_{R}(u)] = u, so S_{R}(u) ⪯ [S_{R}(u) · S_{R}(u)] ⪯ S_{R}(u), which implies that S_{R}(u) is commutative, by Corollary 5.11. □

6. Forking

We work inside a big sufficiently saturated model M of the theory PS_{Γ}, as a universal domain. Recall, by Corollary 4.14, that PS_{Γ} is ω-stable,. Given a finite tuple a and subsets C ⊂ B of M, the extension tp(a/C) ⊂ tp(a/B) is non-forking, if RM(tp(a/B)) = RM(tp(a/C)). More generally, given subsets A, B and C of M, the set A is independent from B over C, denoted by

A | ⌣_{C} B,

if, for every finite tuple a in A, the extension tp(a/C) ⊂ tp(a/B ∪C) is non-forking. This gives rise to a well-behaved notion of independence, which has, among many other, the following remarkable properties (cf. [16, Corollary 8.5.4 and Theorem 8.5.5]):

Symmetry: If A | ⌣_{C} B, then B | ⌣_{C} A.

Extension: Given a tuple a and subsets C ⊂ B of M, there is a non-forking extension of tp(a/C) to B ∪ C, that is, there is some realisation of tp(a/C) which is independent from B over C.

Stationarity: Every type p over an elementary substructure N of M is stationary, that is, given a subset B of M, there is a unique non-forking extension of p to N ∪ B.

Invariant Extension: Given a type p over a sufficiently saturated elementary substructure N of M which is invariant over a small subset C ⊂ N, that is, every automorphism of N fixing C fixes p (as a collection of formulae), then p is the unique non-forking extension of p↾C to N.

Indeed, the last property follows from the fact that a global type, which is invariant over C, does not fork over C [16, Exercise 7.1.4], plus the fact that collection of non-forking extensions of p ↾ C to N are conjugate under automorphisms of N [16, Theorem 8.5.6].

In a similar fashion as in [2, Section 7], we will describe non-forking over nice sets and canonical bases in PS_{Γ}. We will also show that this theory, which has weak elimination of imaginaries, has trivial forking and furthermore is totally trivial, as defined in [5].

Recall the terminology introduced in Definition 3.20: A word u connects the flag F to the flag G if it is the word of a reduced path from F to G. This word is unique, up to permutation, and denoted by w(F, G).

The following result describes the type of a flag over a nice set and will help us to determine the nature of non-forking.

Proposition 6.1. Given a flag F and a reduced path with word u which connects F to a flag G lying in a nice set D, the following are equivalent:

(a) For any flag G′ in D,

w(F, G′) = [u · w(G, G′)],

that is, the word connecting F to G′ is equivalent to [u·v], the non-splitting reduct of u · v, where v is the reduced word connecting G to G′.

(b) The word u is the ⪯-smallest word connecting F to some flag in D.

(c) The word u is ⪯-minimal among words connecting F to some flag in D.

This generalisation of [2, Proposition 7.2] has essentially the same proof. Note that a word u satisfying Property (b) is unique, up to permutation, for ≺ is irreflexive.

Proof. (a)→(b) follows from Corollary 5.8. The implication (b)→(c) is trivial.

For (c)→(a), let v be the word of a reduced path from G to some flag G′ in D. By niceness, we may assume that the path is fully contained in D. Choose a decomposition u = u_{1} · u′ · w and w · v′ · v_{1} = v, as in Proposition 5.9, with corresponding paths

F ⟶^{u_{1}·u′} F_{1} ⟶^{w} G ⟶^{w} G_{1} ⟶^{v′·v_{1}} G′,

where G_{1} is some flag in D. The word b connecting F_{1} to G_{1} is a reduct of w · w, so b ⪯ w. The word c connecting F with G_{1} is hence a reduct of u_{1} · u′ · b, so

c ⪯ u_{1} · u′ · b ⪯ u_{1} · u′ · w ⪯ u.

Minimality of u implies that c ≈ u, so b ≈ w. Hence, in the reduction of the path F ⟶ G′, no splitting occurred and the resulting word is u_{1} · w · v_{1} = [u · v], by Proposition 5.9. □

Definition 6.2. A base-point of the flag F over the nice set D is a flag G in D such that any of the conditions of Proposition 6.1 hold.

Recall Definition 5.17 of S_{R}(u). By Corollaries 5.10 and 5.18, we easily conclude the following:

Corollary 6.3. Let G be a base-point of F over the nice set D and u the word which connects F to G. Let v be a reduced word connecting G to some flag G_{1} in D. The flag G_{1} is a base-point of F over D if and only if v is right-absorbed by u if and only if u = [u · v] if and only if v ⪯ S_{R}(u).

Lemma 6.4. ( cf. [2, Lemma 7.4]) Let G be a base-point of F over the nice set D and denote by P a reduced path F = F_{0}, …, F_{n} = G with word u. Then D ∪ P is nice. It is uniquely determined by G and u in the following strong sense: If P′ = F′_{0}, …, F′_{n} is a second path with word u from F to G, then there is a (unique) isomorphism D ∪ P → D ∪ P′ which is the identity on D and maps each F_{i} onto F′_{i}.

We will express the last property by saying that the ”extension F_{0} ⋯ F_{n}/D” is uniquely determined, up to isomorphism.

Proof. If u is trivial, there is nothing to show. Otherwise, write u = u′ · s. Minimality of u yields that no splitting of s can connect F_{n−1} to a flag in D. Thus Proposition 4.7 implies that the set D′ = D ∪ F_{n−1} is nice and a simple extension of D of type s, G.

We will now show that F_{n−1} is a base-point of F over D′, by Proposition 6.1 (c). Otherwise, there is a reduced word v ≺ u′ which connects F to a flag H′ in D′. By minimality of u, the flag H′ cannot lie in D. By Remark 4.4, there exists some flag H in D such that H′ ⟶^{s} H. This gives a reduced path from F to H whose word is some reduction of v · s, contradicting the minimality of u.

By induction, if P_{0} denotes the subpath F = F_{0}, …, F_{n−1}, then the set D′∪P_{0} is nice and the extension F_{0} ⋯ F_{n−1}/D′ is uniquely determined, up to isomorphism, by G′ and u′. Therefore, the extension F_{0} ⋯ F_{n}/D is uniquely determined, up to isomorphism, by G and u. □

Corollary 6.5. Given a reduced word u and a flag G in a nice set D, there is a flag F such that u connects F to G, which is a base-point of F over D. The type of F over D is uniquely determined by G and u.

Recall that the word w(F, G) is determined only up to a permutation. So the tp(F/D) depends only on the equivalence class of u.

Proof. Observe that, if such a flag F exists and P denotes the reduced path from F to G with word u, Lemma 6.4 and Corollary 4.13 imply that the type of P over D is uniquely determined by G and u.

Thus, we need only show existence of such a flag F, by induction on the length of u. If u = 1, there is nothing to do. Otherwise, write u = s · u′ and choose a flag F′ connecting to G by u′ such that G is a base-point of F′ over D. Let P′ denote the reduced path F′ ⟶^{u′} G. By Lemma 6.4, the set D′ = D ∪ P′ is nice. Corollary 4.11 yields a simple extension D′ ∪ F of type s, F′. Proposition 4.7 implies that F′ is base-point of F over D′. We need only show that G is a base-point of F. Hence, let G′ be an arbitrary flag in D ⊂ D′. We have

w(F, G′) = [s · w(F′, G′)] = [s · [u′ · w(G, G′)]] = [u · w(G, G′)],

as desired. □

If we denote the type of F over G, resp. over D, by

p_{u}(G) resp. p_{u}(G)|D,

we conclude the following.

Proposition 6.6. Let G be a flag in the nice set D and u a reduced word, then p_{u}(G)|D is the unique non-forking extension of p_{u}(G) to D.

Proof. By the Extension principle, we may replace D by a sufficiently saturated elementary substructure containing it, which is again nice in M. Since p_{u}(G)|D is invariant over G, the Invariant Extension principle yields the desired result. □

Since the type p_{u}(G) admits a non-forking extension to D, which must coincide with p_{u}(G)|D, by the previous result, we obtain the following immediate observation.

Corollary 6.7. ( cf. [2, Lemmata 7.4 and 7.6]) Given a flag F and a nice set D, the flag G in D is a base-point of F over D if and only if F | ⌣_{G} D.

Recall that the canonical base Cb(p) of a stationary type p is some set, fixed pointwise by exactly those automorphisms of M fixing the global non-forking extension p of p to M. If Cb(p) exists, then it is unique, up to interdefinability, and p is the unique non-forking extension to M of its restriction to Cb(p). Furthermore, if p is a stationary type over B and Cb(p) exists, then p does not fork over A ⊂ B if and only if Cb(p) is algebraic over A.

Canonical bases exist as imaginary elements in the expansion T^{eq} of an ω-stable theory T [16, Chapter 8.4].

As in Remark 3.2, given a reduced word u, we do not distinguish between the word S_{R}(u) and its support. For a flag G, the class of G modulo S_{R}(u) can be identified with a subset of the real sort, namely with the set of vertices of G whose colours do not belong to S_{R}(u). To simplify the notation, we will denote this class by G/S_{R}(u).

Corollary 6.8. The class G/S_{R}(u) is a canonical base of p_{u}(G).

Proof. Two types p_{u}(G) and p_{u}(G_{1}) have a common global non-forking extension if and only if p_{u}(G)|D = p_{u}(G_{1})|D for some nice set D which contains G and G_{1}. This is equivalent, by Corollary 6.3, to w(G, G_{1}) ⪯ S_{R}(u), which is equivalent to G_{1} ∼_{S_{R}(u)} G. □

Definition 6.9. Given reduced words u and v, we say that u is a proper left-divisor of v if u ≉ v and there is a reduced word w such that [u · w] = v.

If u is a proper left-divisor of v, it follows that u ≺ v. In particular, being a proper left-divisor is a well-founded relation. Let R_{div} be its foundation rank, and likewise let R_{≺} denote the foundation rank of reduced words with respect to ≺.

The foundation rank of types associated to the forking relation is called Lascar rank, denote by U-rank. This means that a type has Lascar rank at least α + 1 if and only if it has a forking extension of Lascar rank at least α.

The following result can be proved exactly as [2, Theorem 7.10 and Lemma 7.11]

Lemma 6.10. For every flag G and every reduced word u,

U(p_{u}(G)) = R_{div}(u) ≤ RM(p_{u}(G)) ≤ R_{≺}(u).

In general R_{div}(u), RM(p_{u}(G)) and R_{≺}(u) need not agree (cf. [2, Remark 7.14]). They coincide however in the following special case, the proof of which is a straightforward modification of the proof of [2, Lemma 7.12], together with Lemma 4.10.

Lemma 6.11. ( cf. [2, Corollary 7.13]) For every reduced word u = s_{1} ⋯ s_{n}, with |s_{i}| ≥ |s_{i+1}| for i = 1, …, n − 1,

R_{div}(u) = R_{≺}(u) = ω^{|s_{1}|−1} + ⋯ + ω^{|s_{n}|−1}.

Remark 6.12. For an arbitrary reduced word u, the Morley rank of the type p_{u}(G) can be easily computed thanks to the following observation: The rank of p_{u}(G) is strictly larger than α if and only if either

(1) the word u has a proper left-divisor v such that p_{v}(G) has at least rank α, or

(2) the type p_{u}(G) is an accumulation point of a family of types p_{v}(G), each of rank at least α.

Corollary 6.13. The theory PS_{Γ} is ω-stable of Morley rank ω^{K−1}, where K is the cardinality of a connected component of Γ of largest size.

Proof. Decompose Γ = ⋃_{i=1}^{n} Γ_{i} into its connected components. Similarly as in Corol-

lary 8.4, it is easy to see that each restriction M_{i} = A_{Γ_{i}}(M) is a model of PS_{Γ_{i}}. The structure M can be considered as the disjoint union of the structures M_{i}’s, so the Morley rank of M is the maximum of the Morley ranks of the structures M_{i}. We may therefore assume that Γ is connected.

Given any vertex a, choose a flag F containing a as well as a flag G independent from F over ∅. If p_{u}(G) is the type of F over G, then the word u must be equal to Γ, since the canonical base G/S_{R}(u) is algebraic over the empty set. By Lemma 6.11, we have

U(F) = RM(F) = R_{≺}(Γ) = ω^{K−1}.

By Lascar inequalities (cf. [16, Exercise 8.6.5]), we have that U(F/a) + U(a) ≤ U(F) = ω^{K−1}, so U(a) = ω^{K−1}, since U(a) > 0. Since

ω^{K−1} = U(a) ≤ RM(a) ≤ RM(F) = ω^{K−1},

we have equality, as desired. □

Two types p and q, possibly over different sets of parameters, are non-orthogonal, if there is a common extension C of both sets of parameters, and two realisations a and b of the corresponding non-forking extensions of p and q to C such that a forks with b over C. As in [2, Theorem 7.15], we conclude the following.

Remark 6.14. Every type over a nice set D is non-orthogonal to some p_{s}(G)|D, where G lies in D.

Given a reduced flag path P : F ⟶^{u} G, we will conclude this section by describing the flags one can obtain from the collection of vertices of the flags occurring in P, as well as describing how the flags in P can vary (or wobble), whilst the endpoints are fixed.

Lemma 6.15. ( cf. [2, Lemma 6.18]) Let A be the set of vertices of the flags occurring in a reduced flag path P. Then any flag in A occurs in some permutation of P ( cf. Lemma 3.7).

Proof. Write P : F ⟶^{u} G and note first that G is the base-point of F over G. If u = 1, then F = G is the only flag in A, so there is nothing to prove. Otherwise, write u = s · v and decompose the path P as F ⟶^{s} H ⟶^{v} G. If we denote by B the set of vertices of the flags occurring in the reduced path H ⟶^{v} G, Lemma 6.4 yields that B is nice. By induction and Proposition 4.7, the nice set B ∪ F is a simple extension of B of type s, H.

Given any flag K in A, we distinguish two cases: if K lies in B, by induction K occurs in some permutation of H ⟶^{v} G, which induces a permutation of P. Otherwise, by Remark 4.4, there exist a reduced word w commuting with s and a flag K_{1} in B such that F ⟶^{s} H ⟶^{w} K_{1} and F ⟶^{w} K ⟶^{s} K_{1}. By Corollary 3.6, we may assume that the second path is a permutation of the first. By induction, the flag

K_{1} belongs to a permutation H ⟶^{w} K_{1} ⟶^{v_{2}} G of H ⟶^{v} G. So F ⟶^{w} K ⟶^{s} K_{1} ⟶^{v_{2}} G

is a permutation of P. □

The following generalises Remark 4.4 and Lemma 6.15.

Lemma 6.16. Let G be a base-point of F over the nice set D and P be a reduced path connecting F to G. For every flag K′ in the nice set D ∪ P, there are flags K occurring in some permutation of P and G′ in D, such that w = w(K, G) commutes

with v = w(G, G′) and K ⟶^{v} K′ ⟶^{w} G′.

Proof. If P is trivial, set K = G and G′ = K′. Otherwise, decompose P into F ⟶^{s} F′ ⟶^{u′} G and set P′ : F′ ⟶^{u′} G. Note that G is also a base-point of F′ over D. If K′ is contained in D ∪ P′, find, by induction on the length of P, a flag K occurring in some permutation of P′ and G′ in D, as desired. Otherwise, Remark 4.4 implies the existence of a flag K′_{1} in D ∪ P′ such that w′ = w(F′, K′_{1})

commutes with s and F ⟶^{w′} K′ ⟶^{s} K′_{1}. By induction, we find a flag K_{1} occurring in a permutation of P′ and a flag G′ in D such that w_{1} = w(G, G′) commutes with

v_{1} = w(K_{1}, G) and K_{1} ⟶^{w_{1}} K′_{1} ⟶^{v_{1}} G′.

Let P_{1} : K_{1} ⟶^{v_{1}} G be the part of a permutation of P′ which connects K_{1} to G. Lemma 6.4 implies that the set D_{1} = D ∪ P_{1} is nice. Furthermore, the flag K_{1} is a base-point of F′ over D_{1}. Set u_{1} = w(F′, K_{1}). Since F′ ⟶^{u_{1}} K_{1} ⟶^{w_{1}} K′_{1}, we conclude that w′ = [u_{1} · w_{1}]. In particular, the letter s must commute with both u_{1} and w_{1}. Since F ⟶^{s} F′ ⟶^{u_{1}} K_{1}, there exists thus a unique flag K such that F ⟶^{u_{1}} K ⟶^{s} K_{1}. Clearly, the flag K occurs in a permutation of P with word u_{1} · s · v_{1} and w(K, G) = s · v_{1} = w(K′, G′). We need only show that w(K, K′)

commutes with s·v_{1}. Since K ⟶^{u_{1}^{−1}} F ⟶^{w′} K′, the word w(K, K′) is some reduction of u_{1}^{−1} · w′ (possibly with splitting), so w(K, K′) commutes with s, since both u_{1} and w do. The flag path K ⟶^{s} K_{1} ⟶^{w_{1}} K′_{1} ⟶^{s} K′ must reduce to one with word w(K, K′), which commutes with s, so the word

s · w_{1} · s ≈ w_{1} · s · s

must reduce to w_{1} = w(K, K′), which commutes with s · v_{1}, as desired. □

Corollary 6.17. Let A be the nice set consisting of the vertices of the flags occurring in a reduced flag path P : F ⟶^{u} G. Every flag K in A is uniquely determined by w(K, G). Thus, the only automorphism of A fixing one of the endpoints of P is the identity.

Proof. Given flags K and K′ in A with w(K′, G) = w(K, G) = w, Lemma 6.15

shows that there are permutations Q : F ⟶^{v} K ⟶^{w} G and Q′ : F ⟶^{v′} K′ ⟶^{w′} G of P. Since w ≈ w′, Lemma 5.2 implies that v′ ≈ v. We may therefore permute Q′ in order to decompose it as Q_{1} : F ⟶^{v} K′ ⟶^{w} G. The correspondence between permutations of a flag path and permutations of the associated word in Lemma 3.7 implies that Q = Q_{1}, so K′ = K. □

Definition 6.18. The wobbling of a reduced product u · v is Wob(u, v) = S_{R}(u) ∩ S_{R}(v^{−1}), that is, the collection of those γ in Γ which are both right-absorbed by u and left-absorbed by v.

Note that Wob(u, v) cannot be equal to |u| nor to |v|, for u · v is reduced.

Lemma 6.19. (Wobbling Lemma cf. [2, Lemma 7.4]) Given two reduced paths between the flags F and G with the same word u = s_{1} ⋯ s_{i} ⋯ s_{n},

H_{1}  ⋯  H_{n−1}
F  G,
H′_{1}  ⋯  H′_{n−1} s_{1} s_{1} s_{n} s_{n}

then H_{i} and H′_{i} are Wob(s_{1} ⋯ s_{i}, s_{i+1} ⋯ s_{n})-equivalent for every i in {1, …, n−1}.

In particular, the tuple H_{i}/Wob(s_{1} ⋯ s_{i}, s_{i+1} ⋯ s_{n}) enumerating the vertices of H_{i} with colours in Γ \ Wob(s_{1} ⋯ s_{i}, s_{i+1} ⋯ s_{n}) lies in dcl(F, G).

Proof. Given two different flag paths as in the above picture, we prove the statement by induction on the index i < n. For i = 1, let w_{1} be the reduced word connecting H_{1} to H′_{1}. Since H_{1} ⟶^{s_{1}} F ⟶^{s_{1}} H′_{1}, it follows that w_{1} ⪯ s_{1} and w_{1} is right absorbed by s_{1}. If w_{1} = s_{1}, it contradicts Proposition 3.19, since H_{1} ⟶^{s_{2}···s_{n}} G. Therefore, the word w_{1} is a proper splitting of s_{1}. Furthermore, since w_{1} · s_{2} ⋯ s_{n} ⟶^{∗} s_{2} ⋯ s_{n}, no letter from s_{2} ⋯ s_{n} can be absorbed during the reduction, for the word u is reduced. Corollary 5.10 implies that w_{1} is completely absorbed by s_{2} ⋯ s_{n}, so |w_{1}| ⊂ Wob(s_{1}, s_{2} ⋯ s_{n}), as desired.

Let now H_{i} ⟶^{w_{i}} H′_{i}, resp. H_{i+1} ⟶^{w_{i+1}} H′_{i+1}. By induction, the word w_{i} has support in Wob(s_{1} ⋯ s_{i}, s_{i+1} ⋯ s_{n}). Lemma 5.14 yields that w_{i} ≈ w_{i}^{1} · w_{i}^{2}, where w_{i}^{1} is left-absorbed by s_{i+1} and w_{i}^{2} commutes with s_{i+1} in order to be left-absorbed by s_{i+2} ⋯ s_{n}. Thus w_{i}^{1} ≺ s_{i+1}. Since

s_{i+1} · w_{i} · s_{i+1} → w_{i}^{2} · s_{i+1} · s_{i+1}

reduces to w_{i+1}, we conclude that w_{i+1} ≈ w_{i}^{2} · x, where x ⪯ s_{i+1}. Note that x ≺ s_{i+1}, since H_{i+1} ⟶^{s_{i+2}···s_{n}} G, so x is a splitting of s_{i+1} which must be absorbed by s_{i+2} ⋯ s_{n} and so is w_{i+1}. The word w_{i}^{2} is right-absorbed by s_{1} ⋯ s_{i}, by induction, and commutes with s_{i+1}. Since x is a proper splitting of s_{i+1}, we have that and s_{1} ⋯ s_{i+1}·w_{i}^{2}·x → s_{1} ⋯ s_{i+1}, so w_{i+1} is right-absorbed by s_{1} ⋯ s_{i+1}, as desired. □

Lemma 6.20. (Base-point Lemma cf. [2, Lemma 7.18]) Given a flag H with basepoint G in the nice set A, let H ⟶^{v} G be a reduced flag path connecting H to G. If H/W lies in acl(A) for some subset W ⊂ Γ, then |v| ⊂ W.

Proof. Choose a flag H′ ⊧ tp(H/acl(A)) with H | ⌣_{A} H′. Note that G is a basepoint in A for H′ as well. Thus Proposition 6.6 and transitivity of non-forking imply that H | ⌣_{G} H′. Furthermore, the flags H and H′ are W -equivalent, so the reduced word w connecting H to H′ has support in W. By Proposition 6.1, the word w is the non-splitting reduct of v · v^{−1} and equals v_{1} · ṽ · v_{1}^{−1}, where ṽ is the final segment of v ≈ v_{1} · ṽ, by Corollary 5.15. Thus, the set |v| is contained in |w| ⊂ W, as desired. □

Corollary 6.21. Nice sets are algebraically closed.

Proof. Let b be algebraic over the nice set A. Suppose that b has colour γ and choose some flag H containing it. Pick some base-point G for H over A, and let P : H ⟶^{u} G be a reduced flag path connecting H to G. By assumption, the set H/(Γ \ {γ}) = {b} lies in acl(A), so |u| ⊂ Γ \ {γ}, by Lemma 6.20, that is, the element b equals the γ-vertex of G, which lies in A. □

7. Equationality

In this section, we will show that the theory PS_{Γ} is equational.

Definition 7.1. A parameter-free formula φ(x, y), where the tuple x has length n, is an n-equation if the family of finite intersections of instances φ(x, a) (where a belongs to a sufficiently saturated model N) has the descending chain condition (DCC).

A complete theory T is n-equational if every definable set in N^{n} is a Boolean combination of instances of n-equations. A theory is equational if it is n-equational for every n in ℕ.

Stability, a wider class class containing ω-stable theories [16, Section 8.2], is preserved under naming parameters and bi-interpretability. The same holds for equationality [11]. However, it is unknown whether equationality follows from 1equationality, which itself implies stability for formulae φ(x, y), where x is a single variable, and thus stability [14]. The rest of this section is devoted to showing that the theory PS_{Γ} is equational. As in the previous section, let M denote a sufficiently saturated model of PS_{Γ}, inside of which we work.

Definition 7.2. Given a word u = s_{1} ⋯ s_{n} and a flag G in M, let P_{u}(X, G) be the formula stating the existence of a sequence X = F_{0}, …, F_{n} = G of flags with F_{i−1} ∼_{s_{i}} F_{i} for 1 ≤ i ≤ n.

It follows from Lemmata 3.4, 3.7 and 3.9 that M ⊧ P_{u}(F, G) if and only if there

exists some reduction u′ ⪯ u with F ⟶^{u′} G. Thus, if w ⪯ u, then the sentence ∀X∀Y (P_{w}(X, Y) → P_{u}(X, Y)) holds in all Γ-spaces. When the word w is reduced, the converse holds on models of PS_{Γ}, as shown below.

Remark 7.3. Let w be a reduced word and w_{1}, …, w_{n} be arbitrary words. Then

PS_{Γ} ⊧ ∀X∀Y (P_{w}(X, Y) → ⋁_{i=1}^{n} P_{w_{i}}(X, Y))

if and only if w ⪯ w_{i} for some i.

Proof. We need only prove left-to-right. By Corollary 6.5, there are flags F and G in our saturated model M such that F ⟶^{w} G. Thus P_{w_{i}}(F, G) for some i, so

F ⟶^{w′} G for some reduced w′ ⪯ w_{i}. Proposition 3.19 implies that w ≈ w′, so w ⪯ w_{i}. □

Lemma 7.4. Given two arbitrary words u and v, there is a finite collection of reduced words w_{1}, …, w_{n} such that, for any reduced word w,

w ⪯ u, v ⟺ ⋁_{i=1}^{n} w ⪯ w_{i}.

In particular, the words w_{i} ⪯ u, v for all i.

Proof. In M, the formula P_{u}(F, G) ∧ P_{v}(F, G) implies that P_{w}(F, G) for some reduced word w ⪯ u, v. By compactness, there is a finite set w_{1}, …, w_{n} of reduced words satisfying that w_{i} ⪯ u, v for i = 1, …, n and

PS_{Γ} ⊧ ∀X∀Y (P_{u}(X, Y) ∧ P_{v}(X, Y) → ⋁_{i=1}^{n} P_{w_{i}}(X, Y)).

Thus, if w ⪯ u, v, the formula P_{w}(X, Y) implies ⋁_{i=1}^{n} P_{w_{i}}(X, Y). Whence w ⪯ w_{i} for some i, by Remark 7.3. □

Lemma 7.5. Given flags G_{1} and G_{2} in M, and reduced words u_{1} and u_{2} such that neither P_{u_{1}}(X, G_{1}) nor P_{u_{2}}(X, G_{2}) imply the other, if P denotes a reduced path from G_{1} to G_{2}, then the conjunction P_{u_{1}}(X, G_{1}) ∧ P_{u_{2}}(X, G_{2}) is equivalent to

⋁_{i=1}^{n} P_{w_{i}}(X, H_{i})

for some flags H_{1}, …, H_{n} occurring in some permutation of P and reduced words w_{1}, …, w_{n} ≺ u_{1}, u_{2}.

If P_{u_{1}}(X, G_{1}) and P_{u_{2}}(X, G_{2}) are disjoint, set n = 0. If G_{1} = G_{2}, this is the content of Lemma 7.4.

Proof. Choose any realisation F ⊧ P_{u_{1}}(X, G_{1}) ∧ P_{u_{2}}(X, G_{2}) and a basepoint H of F over the nice set determined by the reduced path P. The flag H occurs in some permutation of P, by Lemma 6.15.

Set x = w(F, H) and v_{i} = w(H, G_{i}) for i = 1, 2. Observe that w(F, G_{i}) ⪯ u_{i} for i = 1, 2. Proposition 6.1 implies that [x · v_{i}] = w(F, G_{i}) ⪯ u_{i}, so x ⪯ u_{i}/v_{i} for i = 1, 2, by Lemma 5.16. We obtain the following diagram: In particular, a flag F realises P_{u_{1}}(X, G_{1}) ∧ P_{u_{2}}(X, G_{2}) if and only if there is some flag H occurring in some permutation of P with

P_{u_{1}/v_{1}}(F, H) ∧ P_{u_{2}/v_{2}}(F, H).

Lemma 7.4 applied to u_{1}/v_{1} and u_{2}/v_{2} yields reduced words w_{1}, …, w_{n} describing the above intersection. We need only show that w_{j} ≺ u_{1}, u_{2} for j = 1, …, n.

\begin{matrix}G_{1} \\ G_{2} \\ F \\ H \\ ⪯ u_{1} \\ ⪯ u_{2} \\ x \\ v_{2} \\ v_{1} \end{matrix}

Clearly w_{j} ⪯ u_{i}/v_{i} ⪯ u_{i}. Suppose however that w_{j} ≈ u_{1} for some j = 1, …, n, so u_{1} ⪯ u_{i}/v_{i} and thus u_{1} ⪯ [u_{1} · v_{1}] ⪯ u_{1}. Hence P_{u_{1}}(X, G_{1}) = P_{u_{1}}(X, H). Also u_{1} ⪯ [u_{1} · v_{2}] ⪯ u_{2}, so P_{u_{1}}(X, G_{1}) = P_{u_{1}}(X, H) ⊂ P_{u_{2}}(X, H) ⊂ P_{u_{2}}(X, G_{2}), contradicting our hypothesis. □

Since the relation ≺ is well-founded, we conclude the following.

Corollary 7.6. The formulae P_{u}(X, Y) are equations.

By bi-interpretatibility, in order to conclude that the theory PS_{Γ} is equational, we need only show that every formula whose free variables enumerate flags is a Boolean combination of formulae P_{u}(X, G). For that, we will first introduce the notion of nice hulls.

A colour-preserving graph homomorphism f : A → B between two Γ-spaces induces a homomorphism χ(f) : χ(A) → χ(B) between the chamber systems of flags of A and B. It is easy to see that this defines an isomorphism between the category of Γ-spaces and the category of dual quasi-buildings. (cf. Theorem 2.17)

Definition 7.7. Suppose that both A and B are simply connected. Given X ⊂ χ(A) and Y ⊂ χ(B), the map ϕ : X → Y is contracting if and only if for any two flags F and G in X,

w_{B}(ϕ(F), ϕ(G)) ⪯ w_{A}(F, G).

We say that ϕ is an isometry if

w_{B}(ϕ(F), ϕ(G)) = w_{A}(F, G).

The following is easy to see:

Lemma 7.8. If A and B are simply connected, a map χ(A) → χ(B) is contracting if and only if it is an homomorphism of chamber systems.

Definition 7.9. If A ⊂ B are Γ-spaces, a specialisation from B to A is a homomorphism f : B → A such that f↾_{A}= Id_{A}.

Remark 7.10. If B = A ∪ F is a simple extension of A of type s, G, then the map f fixing all elements of A which sends the γ-vertex of F to the γ-vertex of G, for γ in s, is a specialisation.

Lemma 7.11. Given Γ-spaces A ⊂ B, with B simply connected, the subspace A is nice in B if and only if B can be specialised to A.

Proof. Suppose that B can be specialised to A, and let P : F ⟶^{u} G be a reduced path in B connecting two flags F and G in A. The specialisation maps P to a connecting path P′ in A between F and G with word u′ ⪯ u, so A is nice in B.

If A is nice in B, observe that A specialises to itself. Choose then a maximal specialisation f : C → A, with C ⊂ B nice in B. If C ≠ B, Proposition 4.9 yields a proper simple extension C′ of C, which is again nice in B. By the remark 7.10, there is a specialisation C′ → C. Composing it with f contradicts the maximality of f. □

Given two nice subsets N_{1} and N_{2} of our fixed saturated model M, an isomorphism means a bijection f : N_{1} → N_{2} such that both f and f^{−1} are homomorphisms of Γ-spaces. If N_{1} and N_{2} have a common subset A , we say that they are A-isomorphic, denoted by N_{1} ≃_{A} N_{2}, if there is an isomorphism between N_{1} and N_{2} fixing all elements in A.

Definition 7.12. Let N ⊂ M be nice and A be some subset of N.

(1) We say that N is a nice hull of A if every nice subset of M containing A has a nice subset N′ which is A-isomorphic to N.

(2) The Γ-space N is incompressible over A if every A-homomorphism f : N → N is an automorphism of N.

(3) The nice subset N is strongly incompressible over A if every A-homomorphism f : N → M induces an isomorphism of N with a nice subset of M.

We will see in Proposition 7.18 that, if N is incompressible over A, then the only A-endomorphism of N is the identity.

Lemma 7.11 implies the following easy observation.

Remark 7.13. If N is incompressible over A, then it contains no proper nice subset A ⊂ N′ ⊊ N. Likewise if N is strongly incompressible over A.

Lemma 7.14.

(1) If the nice set N is strongly incompressible over A, then it is incompressible and a nice hull of A.

(2) If N is a nice hull of A and N′ is incompressible over A, then N ≃_{A} N′.

Proof. For (1), let N be strongly incompressible over A. To show that N is incompressible over A, consider an A-homomorphism f : N → N. This must induce an A-isomorphism with a nice subset N_{1} of N containing A, so N_{1} = N by Remark 7.13.

Let us now show that N is a nice hull. Given any nice subset N′ of M containing A, choose a specialisation f : M → N′, by Lemma 7.11. The map f↾_{N} must then induce an A-isomorphism of N with a nice subset of N′, as desired.

Suppose now N and N′ are as stated in (2). Since N is a nice hull, there is some nice subset N′′ of N′ which is A-isomorphic to N. We conclude that N′′ = N′ by the Remark 7.13. □

We now have all the necessary ingredients to conclude the following result.

Theorem 7.15. Every subset A of M has a unique, up to A-isomorphism, strongly incompressible extension. If A is finite, so is this extension.

Proof. We give the proof for A finite, and leave the general case to reader.

Proceed by induction over |A|. If A is empty, then any flag is strongly incompressible over ∅. Otherwise, write A = A_{0} ∪ {a} and choose, by induction, a finite strongly incompressible extension N_{0} of A_{0}. Among all flags passing through a, choose one, say F, with ⪯-minimal word u = w_{M}(F, G), where G is some basepoint of F over N_{0}. Assume furthermore that u is ⪯-minimal among all possible A_{0}-copies of N_{0}. Let P : F ⟶^{u} G be a reduced flag path connecting F to G. Set N = N_{0}∪P, which is a finite nice subset of M, by Lemma 6.4. In order to show that N is strongly incompressible over A, consider an A-homomorphism f : N → M. By induction, the map f↾_{N_{0}} induces an A_{0}-isomorphism between N_{0} and the nice set f(N_{0}), so f(N_{0}) is also strongly incompressible over A_{0}. The map f is contracting, by Lemma 7.8, so w(f(F), f(G)) ⪯ u. Since a is contained in f(F), minimality of u implies that w(f(F), f(G)) = u, thus f(G) is a base-point of f(F) over f(N_{0}). Therefore, the set f(P) determines a reduced path from f(F) to f(G). Hence, the set f(N) is nice, by Lemma 6.4, and f is an A-isomorphism, as desired. □

Together with Lemma 7.14, we conclude:

Corollary 7.16. Every set A has a nice hull N(A), which is incompressible and unique, up to A-isomorphism. If A is finite, then so is N(A).

Thus, the three notions in Definition 7.12 coincide.

Corollary 7.17. The algebraic closure acl(A) of a finite set A is finite and contained in N(A).

Proof. Let N(A) be the nice hull of a finite set A. Nice sets are algebraically closed, by Corollary 6.21. Thus, the set acl(A) is contained in N(A), which is finite. □

Proposition 7.18. The nice hull N(A) is rigid over A, that is, its only automorphism fixing A pointwise is the identity.

Proof. Again, we leave the case of infinite A to the reader and assume A finite.

If A is empty, recall that N(∅) consists of a single flag, so the result is obvious. By the proof of Theorem 7.15, if A = A_{0} ∪ {a}, then N(A) = N_{0} ∪ P, where N_{0} is a nice hull of A_{0} and P is a reduced flag path connecting a flag F containing a to its basepoint G over N_{0}. Furthermore, the word w(F, G) is ⪯-minimal among all words w(F, G′), where G′ has the same type as G over A_{0}. If γ denotes the colour of a, then u has a unique beginning s, which contains γ.

By Remark 7.10, choose a specialisation ϕ : N_{0} ∪ P → N_{0}, collapsing the whole path P onto G. Let now f be some automorphism of N(A) fixing A. The map (ϕ ∘ f)↾_{N_{0}}, which is an A_{0}-automorphism, by strong incompressibility of N_{0}, must then be the identity, by induction on |A|. Thus f is the identity on N_{0} \ G.

Since f is an automorphism, we have that w(f(F), f(G)) = w(F, G) = u. As the flag f(F) lies in N_{0} ∪ P, Lemma 6.16 yields some flag K with P : F ⟶^{u_{1}} K ⟶^{u_{2}} G where w(K, f(F)) and u_{2} commute. If P′ denotes the subpath K ⟶^{u_{2}} G, the flag K is a base-point of F over N_{0}∪P′. Thus, the word w(F, f(F)) equals [u_{1}·w(K, f(F))]. Since a is contained in f(F), the flags F and f(F) are (Γ \ {γ})-equivalent, so γ does not occur in w(F, f(F)). If u_{1} is not trivial, then s must be its beginning, for u has only s as a beginning, and hence, either s or a larger letter containing it must occur in w(F, f(F)). Thus, we conclude that u_{1} = 1 and the word w(F, f(F)) commutes with u.

As flag f(G) lies in N_{0}∪P, by Lemma 6.16 there is a flag K_{1} with P : F ⟶^{v_{1}} K ⟶^{v_{2}} G such that w(K, f(G)) and v_{2} commute. We have the following permutations:

v_{1}·v_{2}·w(F, f(F)) ≈ w(F, f(F))·u ≈ w(F, f(F))·w(f(F), f(G)) ≈ [v_{1}·w(K, f(G))].

Corollary 5.13 implies that v_{2} · w(F, f(F)) is a final subword of w(K, f(G)), which commutes with v_{2}. We conclude that v_{2} = 1 and hence f(G) lies in N_{0}. The map f maps N_{0} to itself, so it is the identity on N_{0}. Since f induces a permutation of P, Corollary 6.17 implies that f is the identity on N. □

Corollary 7.19. The algebraic closure acl(A) of A is rigid over A, so it equals dcl(A).

Proof. Note that acl(A) is contained in N(A), by Corollary 7.17, so N(A) = N(acl(A)). Every A-automorphism of acl(A) extends to an automorphism of N(A), which must then be the identity, by Proposition 7.18. □

Proposition 7.20. All types are stationary.

This needs no longer hold if we consider types over subsets of M^{eq}.

Proof. We need only prove the statement for 1-types, and thus it suffices to prove it for types of a single flag. Let p be the type of a flag F over the parameter set A and consider q a global non-forking extension of p to M. Since q = p_{u}(G)|M for some flag G in A, its canonical parameter is B = G/S_{R}(u), by Corollary 6.8, which is interdefinable with a set of real elements. Since B is algebraic over A, it is hence definable over A, by Corollary 7.19. The type p is thus stationary. □

We will show that the theory PS_{Γ} is equational, by proving that the type of finitely many flags is determined by the collection of words connecting each pair of flags. For two flags this follows from Lemma 6.4: A reduced path P : F ⟶^{u} G determines a nice subset, whose type is determined by u. For three flags F, G and H as below:

G ; H ; F ; \begin{matrix}u \\ v \end{matrix} ; w

we need the following Proposition.

Proposition 7.21. (1) Given u, v and w reduced words with u · v ⟶^{∗} w, there is a decomposition:

u ≈ u_{1} · α^{−1} · c^{−1},
v ≈ c · β · v_{1},
w ≈ u_{1} · x · v_{1},

such that α, β and x pairwise commute, the word x is properly right-absorbed by c, the word α is properly left-absorbed by v_{1}, and β is right-absorbed by u_{1}. The words u_{1}, v_{1}, c, x, α and β are unique up to permutation.

(2) Assume further that F, G and H are flags such that w(G, F) = u, w(F, H) = v and w(G, H) = w. Then there is a reduced path P : G ⟶^{w} H, and a base-point K of F over P such that:

w(G, K) = u_{1}
w(K, H) = x · v_{1},
w(F, K) = c · α · β

G H F K u_{1} · α^{−1} · c^{−1} c · β · v_{1} c · α · β x · v_{1} u_{1}

Observe that the existence of a decomposition as in (1) implies u · v ⟶^{∗} w. Indeed, since x is properly right-absorbed by c = t_{m} ⋯ t_{1}, Lemma 5.14 implies that x ≈ x_{1} ⋯ x_{m}, where x_{i} is a splitting t_{i} and commutes with t_{j}, whenever j < i. Thus,

c^{−1} · c = t_{1} ⋯ t_{m} · t_{m} ⋯ t_{1} ⟶^{∗} t_{1} ⋯ t_{m−1} · x_{m} · t_{m−1} ⋯ t_{1} ⟶^{∗}

⟶^{∗} t_{1} ⋯ t_{m−1} · t_{m−1} · x_{m} · t_{m−2} ⋯ t_{1} ⟶^{∗} ⋯

can be reduced to x. Therefore,

u · v ≈ u_{1} · α^{−1} · c^{−1} · c · β · v_{1} ⟶^{∗} u_{1} · α^{−1} · x · β · v_{1} ⟶^{∗}

⟶^{∗} u_{1} · β · x · α^{−1} · v_{1} ⟶^{∗} u_{1} · x · v_{1} ≈ w.

By Lemma 6.15, we may assume in (2) that the flag K occurs in the path P.

Proof. Let us first prove the existence of such a decomposition. By Remark 4.15, find flags F, G and H such that G ⟶^{u} F ⟶^{v} H and G ⟶^{w} H. Let P be a reduced flag path connecting G to H. By Lemma 6.15, we may choose a base-point K of F over P which occurs in the path P. Set w(G, K) = w_{1}, w(K, H) = w_{2}, and w(F, K) = y. Assume that y is ⪯-minimal among all choices of P, which implies

(‡)  No end of y is contained in Wob(w_{1}, w_{2}).

Indeed, if y = y′ · s, with s ⊂ Wob(w_{1}, w_{2}), decompose F ⟶^{y′} K′ ⟶^{s} K for some flag K′. Observe that K is also a base-point for K′ over the nice set determined by P, so by Proposition 6.1 the reduction of s · w_{1}^{−1}, resp. s · w_{2}, is non-splitting and equals w_{1}^{−1}, resp. w_{2}. Replacing K by K′, we obtain a permutation P′ of P, so that F connects to P′ with word y′, contradicting the minimality of y.

Proposition 6.1 implies that [y · w_{1}^{−1}] = u^{−1} and [y · w_{2}] = v. By Proposition 5.9, up to permutations of w_{1} and u, write:

w_{1} = u_{1} · x′,
y ≈ c_{1}^{−1} · β,
u = u_{1} · c_{1}

where x′ and β commute, the word x′ is properly left-absorbed by c_{1} and β is right-absorbed by u_{1}. Let K′ be a flag in P such that G ⟶^{u_{1}} K′ ⟶^{x′} K. Since x′ is right-absorbed by y, the flag K′ is also a base-point of F over P by Corollary 6.3. Replacing K′ by K, we may assume that x′ = 1.

Likewise, write

w_{2} = x · v_{1},
y ≈ c_{2} · α,
v = c_{2} · v_{1}

where x and α commute, the word x is properly right-absorbed by c_{2} and α is left-absorbed by v_{1}.

Note that y = c_{2} · α ≈ c_{1}^{−1} · β. However, no end of α can be an end of β, by (‡). Thus, every end of α commutes with β and Lemma 5.3 yields that α commutes with β and is a final subword of c_{1}^{−1}. Likewise for β and c_{2}. After possible permutations of c_{1} and c_{2}, write:

c_{1}^{−1} = c · α,
c_{2} = c · β.

Let us now show that β and x commute. Otherwise, write x = x_{1} · s · x_{2}, where x_{1} and β commutes, but β and s do not. Since x is right-absorbed by c_{2} = c · β, the letter s must be absorbed by β, and therefore right-absorbed by u_{1}. Since s commutes with x_{1}, the word w = u_{1} · x · v_{1} is not reduced, which is a contradiction. Hence, the word x is properly right-absorbed by c.

We have now

u = u_{1} · α^{−1} · c^{−1},
v = c · β · v_{1},
w = w_{1} · w_{2} = u_{1} · x · v_{1},
y = c · α · β.

The only property left to show is that α is properly left-absorbed by v_{1}. Otherwise, apply Corollary 5.12 to produce, up to permutation, the following decompositions:

α = α′ · ω  ω · v_{2} = v_{1},

where ω is a commuting word, the word α′ is properly left-absorbed by v_{2}, and α′ and ω commute. Since w_{2} ≈ ω · x · v_{2}, there is a flag K′ in some permutation of P such that K ⟶^{ω} K′ ⟶^{x·v_{2}} H. Now, the word ω is right-absorbed by y ≈ c · β · α′ · ω, so the flag K′ is also a base-point of F over P, by Corollary 6.3. Replacing K by K′, and substituting:

u_{1} ⇝ u_{1} · ω
v_{1} ⇝ v_{2}
α ⇝ α′
β ⇝ β · ω

gives that the new words u_{1}, v_{1}, c, x, α, β and the new base-point K have the desired properties.

For uniqueness, let u_{1}·a be the largest common initial subword of u = u_{1}·α^{−1}·c^{−1} and w = u_{1} · x · v_{1} (cf. the discussion after Definition 5.1). Since α and x commute and each one is properly left absorbed by v_{1}, resp. c^{−1}, the word a must commute with α and x, and is an initial subword of both c^{−1} ≈ a · c′ and v_{1} ≈ a · v′_{1}. In particular, the words α · c′ and x · v′_{1} are uniquely determined, up to a permutation, for u_{1} · a is.

Observe that c′ is the largest common final subword of α · c′ and v^{−1} = v′_{1}^{−1} · a^{−1} ·β^{−1} ·a·c′, for otherwise, the largest common final subword would then contain a letter s from α, which is an end of v′_{1}^{−1} · a^{−1} · β^{−1} · a, contradicting that α is properly left-absorbed by v′_{1}. Therefore, the words α and a^{−1} · β · a · v′_{1} are uniquely determined.

Since x and a^{−1} ·β ·a commute, the word v′_{1} is the largest common final subword of x · v′_{1} and a^{−1} · β · a · v′_{1}, so x and a^{−1} · β · a are uniquely determined. The result now follows by applying the following auxiliary result to the words u_{1} · a and a^{−1} · β · a, in order to determine u_{1}, a and β, as desired.

Claim. Given reduced words e ≈ u · a and f ≈ a^{−1} · b · a, where u right-absorbs b, then a, u and b are uniquely determined by e and f.

Proof of the claim: We proceed by induction on the length of f. Clearly, if f = 1, then b = a = 1 and thus e = u.

Otherwise, note that e right-absorbs f if and only if a = 1, in which case e = u and f = b. Therefore, if e does not right-absorb f, write a = a′ · s. In particular, the word e has an end which is simultaneously a beginning and an end of f.

We show first that the only possible ends t of e which are both a beginning and an end of f are exactly the ends of a. If not, the end t must be an end of u which commutes with a. Likewise b ≈ t · b′ · t, which contradicts that u right-absorbs b, since b′ and t do not commute.

Removing s yields the reduced words u · a′ and a′^{−1} · b · a′, and the result now follows by induction. End of the proof of the claim.

□

Corollary 7.22. The type tp(F, G, H) of three flags F, G and H is uniquely determined by w(F, G), w(G, H) and w(F, H).

Proof. Proposition 7.21 yields a reduced path P : G ⟶^{w_{1}} K ⟶^{w_{2}} H from G to H, where K is a base-point of F over the nice set determined by P, such that w_{1}, w_{2} and w(F, K) are uniquely determined, up to permutation, by the words w(F, G), w(G, H) and w(F, H). By Corollary 6.5, the type of F over P is uniquely determined by w(F, K) and K. Note that H is a base-point of G over the nice set H, so Lemma 6.4 yields that the type of P = G, …, K, …, H is determined by the word w_{1} · w_{2}. Thus, the type of GKH is determined by the equivalence classes of w_{1} and w_{2}, as desired. □

To extend this result to arbitrary sets of flags, we need the following lemma. Given a Γ-space A, recall that χ(A) denotes the chamber system of the flags in A (cf. the discussion before Definition 7.7).

Lemma 7.23. A non-empty collection X of flags of M equals χ(A) for some nice subset A of M if and only if, whenever F and G in X are connected by a reduced word u in M, then there is path in X with word u connecting F to G.

If X = χ(A), the remark after Definition 4.5 implies that A is the union of the flags in X.

Proof. One direction is an equivalent definition of niceness, so we need only show that, if X satisfies the right-hand condition, then X = χ(A) for some nice subset A. Set A the collection of all vertices of flags in X. In order to show that X = χ(A) and that A is nice, it suffices to show that any flag in A is a flag from X, that is, we need only show, by induction on |S|, that given a collection of elements S in A lying in a flag H in M, there is a flag in X containing S. If S is a singleton, there is nothing to prove. Otherwise, enumerate S = {a_{1}, …, a_{r}} and set T ⊂ Γ the collection of colours of a_{1}, …, a_{r−1}, and γ the colour of a_{r}. Choose a flag F in X containing a_{r} and, by induction, a flag G in X containing a_{1}, …, a_{r−1}. Observe that

F ∼_{Γ\{γ}} H ∼_{Γ\T} G,

so there are reduced words u and v, such that γ does not occur in u, the support of v is disjoint from T and F ⟶^{u} H ⟶^{v} G. Reducing this path in M gives a word w_{1} · w_{2}, where γ does not occur in w_{1} and each letter in w_{2} is disjoint from T. By assumption, there is a reduced path in X of the form F ⟶^{w_{1}} H′ ⟶^{w_{2}} G. Clearly, the path H′ lies in X and contains the set S, as desired. □

We will now extend Corollary 7.22 to arbitrarily many flags.

Theorem 7.24. The type tp(F_{1}, …, F_{n}) of a sequence of flags is uniquely determined by w(F_{i}, F_{j}) for 1 ≤ i ≠ j ≤ n.

Proof. Recall the notion of isometry, as in Definition 7.7. Given two collections of flags X and X′, we will show that a surjective isometry ϕ : X → X′ induces an elementary map between nice subsets of M.

Suppose first that X satisfies the conditions of Lemma 7.23. Then so does X′, and there are nice subsets A and A′ such that X = χ(A) and X′ = χ(A′). In particular, the map ϕ induces a graph isomorphism f : A → A′, for two flags F and G in A are γ-equivalent if and only if w(F, G) does not contain γ. By Remark 4.6 (2), nice subsets are Γ-spaces, so f is an elementary map, by Corollary 4.13.

Thus, we need only show that ϕ can be extended to some supersets of flags, which satisfy the conditions of 7.23. Given flags F and G in X, with respective images F′ and G′ in X′, if w(F, G) = u, then choose reduced paths P : F ⟶^{u} G

and P′ : F′ ⟶^{u′} G′ with

X | ⌣_{F,G} P and X′ | ⌣_{F′,G′} P′.

Let ψ be the isometry P → P′ which maps (F, G) to (F′, G′). In order to show that ϕ ∪ ψ is a well-defined isometry between X ∪ P and X′ ∪ P′, consider some flag H in X. It suffices to show that ϕ∪ψ induces an isometry H ∪P → ϕ(H)∪P′. By Corollary 7.22, the map ϕ↾_{H,F,G} is elementary. So is ψ, by Lemma 6.4. As the type tp(H/F, G) is stationary, by Proposition 7.20, it follows that ϕ↾_{H,F,G} ∪ ψ is an elementary map and thus an isometry.

Iterating the above process countably many times, we obtain the desired superset satisfying 7.23. □

The above result together and Corollary 7.6 yield the following, by compactness.

Corollary 7.25. The theory PS_{Γ} is equational.

Equationality, or rather, Theorem 7.24 allows us to show total triviality and hence weak elimination of imaginaries.

Proposition 7.26 (cf. [2, Lemma 7.22]). The theory PS_{Γ} is totally trivial: over any set of parameters D, given tuples a, b and c such that a is independent both from b and from c over D, then a is independent from b, c over D.

By induction on the length of the tuples (cf. [5, Lemma 4]), it is easy to see that it suffices to check total triviality for singletons a, b and c.

Proof. By taking a non-forking extension to a small submodel containing D, we may assume that D is nice. Since every element is contained in a flag, it suffices to show total triviality when a, b and c enumerate three flags F, H and K.

Let G be a base-point of F over D. In particular, we have F | ⌣_{G} H and F | ⌣_{G} K. Choose another realisation F′ of tp(F/G) such that F′ | ⌣_{G} H, K. Then w(F′, G) =

w(F, G) and

w(F′, H) = [w(F′, G) · w(G, H)] = [w(F, G) · w(G, H)] = w(F, H),

since F | ⌣_{G} H. Likewise for w(F, K). Theorem 7.24 implies that F and F′ have the same type over G, H, K, so F | ⌣_{G} H, K, as desired. □

Since PS_{Γ} is ω-stable, we conclude by [5, Proposition 7] the following.

Corollary 7.27. The theory PS_{Γ} is perfectly trivial, that is, given given any set of parameters D and tuples a, b and c such that a and b are both independent over D, then so are they over D ∪ {c}.

An ω-stable theory T has weak elimination of imaginaries if the canonical base of every stationary type can be chosen to be a subset of the real sort. In this case, types over algebraically closed sets are always stationary.

Corollary 7.28. The theory PS_{Γ} has weak elimination of imaginaries, and given any stationary type tp(a_{1}, …, a_{n}/B), then

Cb(tp(a_{1} … a_{n}/B)) = Cb(tp(a_{1}/B)) ∪ ⋯ ∪ Cb(tp(a_{n}/B)).

Proof. Considering a small elementary substructure N, we may assume that the stationary type p = tp(a_{1}, …, a_{n}/N). Suppose that the canonical base of every unary type over N is interdefinable with a finite subset of the real sort. Thus, we may choose finite subsets C_{1}, …, C_{n} such that Cb(tp(a_{i}/N)) is interdefinable with C_{i}. Total triviality (Proposition 7.26) implies that p does not fork over C = C_{1} ∪ ⋯ ∪ C_{n}. By Proposition 7.20, the restriction of p to C is stationary, so C is interdefinable with Cb(p).

Therefore, we need only show that the canonical base of every unary tp(a/N) over the nice set N is interdefinable with a finite subset of the real sort. Given a flag F containing a independent from N, the type tp(F/a) is stationary, so Cb(tp(a/N)) is interdefinable with Cb(tp(F/N)). Corollary 6.8 yields now the desired result.

□

Corollary 7.29. The canonical base of a type is algebraic over two independent realisations.

Proof. Again by Proposition 7.26 and taking small elementary substructures, we need only consider a unary type p over some nice set A. Let a and a′ be two independent realisations of p. Choose a flag F containing a independent from A over a. Since the type of F over a is stationary, it follows that Cb(a/A) is interdefinable with Cb(F/A). By automorphisms, we may find a flag F′ containing a′ with the same type than F over A and

F′ | ⌣_{a′} AF.

In particular, we have that

F F′ | ⌣_{a,a′} A

and

F | ⌣_{A} F′,

thus, if Cb(F/A) ⊂ acl(F, F′) ∩ A, then Cb(a/A) = Cb(F/A) ⊂ acl(a, a′), as desired.

Therefore, we need only prove the statement for the type of a flag F over A. Let F′ | ⌣_{A} F and choose a base-point G of F over A. Suppose that P : F ⟶^{u} G and let ũ be the final segment of u ≈ u_{1} · ũ. Then w(F, F′) = [u · u^{−1}] = u_{1} · ũ · u_{1}^{−1}, by Corollary 5.15.

We obtain the following diagram:

G K K′ F′ F ũ u_{1}^{−1} u_{1} ũ ũ

Since Wob(u_{1}, ũ · u_{1}^{−1}) ⊂ S_{R}(u), Lemma 6.19 implies that K/ ∼_{S_{R}(u)} lies in acl(F, F′). Observe that K ∼ũ G and ũ ⪯ S_{R}(u), by Corollary 5.18. Thus, the canonical base Cb(F/A) is contained in acl(F, F′) as well.

□

8. Ampleness

Recall the definition of n-ampleness [13, 4].

Definition 8.1. A stable theory T is n-ample if, working inside a sufficiently saturated model and possibly over parameters, there are real tuples a_{0}, …, a_{n} satisfying the following conditions:

(1) acl^{eq}(a_{0}, …, a_{i}) ∩ acl^{eq}(a_{0}, …, a_{i−1}, a_{i+1}) = acl^{eq}(a_{0}, …, a_{i−1}) for every

0 ≤ i < n,

(2) a_{i+1} | ⌣_{a_{i}} a_{0}, …, a_{i−1} for every 1 ≤ i < n,

(3) a_{n} |̸ ⌣ a_{0}.

Note that T is n-ample if and only if T^{eq} is [2, Corollary 2.4]. Furthermore, if T is n-ample, it is (n − 1)-ample. A theory is 1-based if and only if it is not 1-ample. It is CM-trivial if and only if is not 2-ample.

In order to find an upper bound for the ample degree of PS_{Γ}, we will use the following result.

Lemma 8.2. ([2, Remarks 2.3 and 2.5]) If T is n-ample, there are tuples a_{0}, …, a_{n} enumerating small elementary substructures of an ambient saturated model such that for every 0 ≤ i < n − 1

(a) a_{n} | ⌣_{a_{i−1}} a_{i}.

(b) acl^{eq}(a_{i}, a_{i+1}) ∩ acl^{eq}(a_{i}, a_{n}) = acl^{eq}(a_{i}).

(c) a_{n} |̸ ⌣_{acl^{eq}(a_{i})∩acl^{eq}(a_{i+1})} a_{i}.

Recall that, given a subset X (of some cartesian power) of a structure M, the induced structure on X is the set of all relations on every cartesian power of X which are definable in M without parameters.

Lemma 8.3. Let X be a subset, definable without parameters, of a model M of a stable theory T. If the theory of X equipped with the induced structure is n-ample, then so is T.

Proof. We may assume that M is sufficiently saturated. Let a_{0}, …, a_{n} in X witness that X is n-ample for some n in ℕ. Since X is equipped with the full induced structure from M, properties (2) and (3) hold, when we consider these tuples in M. Furthermore, working in M, we have that

acl^{eq}(a_{0}, …, a_{i}) ∩ acl^{eq}(a_{0}, …, a_{i−1}, a_{i+1}) ∩ X^{eq} = acl^{eq}(a_{0}, …, a_{i−1}) ∩ X^{eq},

where X^{eq} denotes those imaginary elements of M^{eq} having some representative in X. The following result together with (1) yield the desired result.

Claim. If A and B are subsets of X, then

acl^{eq}(A) ∩ acl^{eq}(B) = acl^{eq} (acl^{eq}(A) ∩ acl^{eq}(B) ∩ X^{eq}) .

Proof of the claim: If e lies in acl^{eq}(A)∩acl^{eq}(B), it is witnessed by finite definable sets E_{a} = φ(x, a), resp. F_{b} = ψ(x, b), with a in A, resp. b in B. The canonical parameter d of the finite set E_{a} ∩ F_{b}, which contains e, belongs to X^{eq}, since X^{eq} is definably closed in M^{eq}. It lies in acl^{eq}(A), resp. acl^{eq}(B), because, if E_{a}, resp. F_{b}, is fixed, there are only finitely many possibilities for the subset E_{a} ∩ F_{b}. End of the proof of the claim.

□

As in the previous sections, we will work inside a sufficiently saturated Γ-space M, a model of PS_{Γ}.

A subgraph Y ⊂ Γ is full if, whenever two vertices x and y in Y are adjacent in Γ, then so are they in Y.

Corollary 8.4. Let Γ′ be a full subgraph of Γ and F a fixed flag in M. Consider the Γ′-residue of F

X = {F′ flag in M | F′ ∼_{Γ′} F }.

The set X is the collection of flags of some nice set A. The restriction M′ = A_{Γ′}(A) to vertices with colours in Γ′ is a model of PS_{Γ′}.

If PS_{Γ′} is n-ample, so is PS_{Γ}.

Proof. If two flags from X are connected by a reduced flag-path P with word u, the |u| is a subset of Γ′, by simple connectedness. Thus, all flags in P belong to X, so X = χ(A), for some nice subset A, by Lemma 7.23.

The restriction G ↦ G′ = G↾_{Γ′} is a bijection between the flags in A (i.e. the elements of X) and the flags of M′. Since Γ′ is full, the Coxeter group generated by Γ′ is a subgroup of (W, Γ), so a reduced word on the letters of Γ′ remains so as a word in Γ. It follows that M′ is a simply connected Γ′-space. For every γ ∈ Γ′ and G in X, every flag in M which is γ-equivalent to G belongs again to X. Thus M′ is a model of PS_{Γ′}.

In order to show that, if PS_{Γ′} is n-ample, so is PS_{Γ}, we need only show, by Lemma 8.3, that the induced structure on M′ (as an definable subset of M with parameters in F) coincides with the structure of M′ as a model of PS_{Γ′}. That is, that every definable relation on M′ which is definable in M over F is then F - definable in the Γ′-space M′, or equivalently, that a type in M′ over F determines a unique type in M over F. Assume therefore that the tuples c_{1} and c_{2} have the same type in M′ over F′. Choosing nice sets D′_{i} in M′, for i = 1, 2 containing F′, c_{i}, there is an elementary map f′ : D′_{1} → D′_{2} in M′, which maps c_{1} to c_{2} and is the identity on F′. The sets D_{i} = D′_{i} ∪ (F \ M′) are clearly nice in A, and hence in M. The map f′ extends to an elementary map between D_{1} and D_{2}, which is the identity on F. Thus the tuples c_{1} and c_{2} have the same type over F in M, as desired. □

Recall (Definition 5.1) that a letter s is an end of the word u if u ≈ v · s. The final segment of u, denoted by ũ, is the commuting subword consisting of all ends of u. When a word w is commuting, we will identify it with its support |w|.

Lemma 8.5. ([2, Lemma 8.2 and Proposition 8.3]) Consider nice sets A and B and a flag F such that F | ⌣_{B} A and acl(AB) ∩ acl(AF) = acl(A). Let u = u_{B} (resp. u_{A}) be the minimal word connecting F to a flag G_{B} in B (resp. G_{A} in A). Consider the reduced word v which connects G_{B} to G_{A} and the associated symmetric decomposition

u = u_{1} · u′ · w  w · v′ · v_{1} = v,

as in Proposition 5.9. Then the word w · v_{1} is commuting. Furthermore, if

F |̸ ⌣_{A∩B} A,

then

|v′| ⊈ ũ ⊊ ũ_{A},

where ũ and ũ_{A} are the final segments of u and u_{A}, respectively.

Proof. By transitivity of non-forking, we have that F | ⌣_{G_{B}} G_{A}, so

u_{A} = [u · v] = u_{1} · w · v_{1}.

We will first show that w · v_{1} is commuting. Considering its final segment, write w · v_{1} ≈ a · b where b is a commuting word. In order to show that a is trivial, we need only show that b and a commute.

Now, the word u′ · w is left absorbed by w · v_{1}, so write u′ · w ≈ u_{a} · u_{b}, by Lemma 5.14, where u_{a} is left-absorbed by a and u_{b} commutes with a in order to be left-absorbed by b. Choose a flag path P : G_{B} ⟶^{v′·a} H ⟶^{b} G_{A}, for some flag H.

Choosing P independent from F over G_{B}, G_{A}, we may assume that F | ⌣_{G_{B}} P, so G_{B} is a base-point of F over the nice set determined by P. Therefore

w(F, H) = [u · v′ · a] = u_{1} · u′ · w · v′ · a = u_{1} · u_{b} · u_{a} · v′ · a = u_{1} · a · u_{b}.

Choose now a flag K with F ⟶^{u_{1}·a} K ⟶^{u_{b}} H. Observe that w(K, G_{A}) ⪯ [u_{b} · b] = b. On the other hand, the word w(F, G_{A}) = [u · v] = u_{1} · w · v_{1} ≈ u_{1} · a · b, so w(K, G_{A}) = b.

G_{B} F H K G_{A} v′ · a bu u_{1} · a bu_{b}

Set C(a) to be the set of colours commuting with a. Clearly C(a) ∩ S_{R}(a) = ∅ and both Wob(v′ · a, b) and Wob(u_{1} · a, b) are subsets of S = S_{R}(a) ∪ C(a). Lemma 6.19 implies that H/S lies in acl(AB) and K/S in acl(AF). Since u_{b} commutes with a and K ⟶^{u_{b}} H, we have that

K/S = H/S ∈ acl(AB) ∩ acl(AF) = acl(A).

Lemma 6.20 implies that b ⊂ S. However, no letter of b is contained in S_{R}(a), since a · b is reduced and b is commuting, so b and a commute, as desired.

Let us now show that ũ ⊂ ũ_{A}. Since a = 1 and b = w · v_{1}, the previous diagram yields the following picture:

G_{B} F H K G_{A} u_{1} u′ · w u_{1} w · v_{1} v′ v′ w · v_{1} u′ · w

The final segment ũ = û_{1} · ũ′ · w for some commuting final subword û_{1} of u_{1}, which commutes with u′ · w. Since v′ is (properly) right-absorbed by u_{1}, we have S_{R}(v′) ⊂ S_{R}(u_{1}) ⊂ T = û_{1} ∪ C(û_{1}), so

Wob(v′, w · v_{1}) ⊂ Wob(u_{1}, w · v_{1}) ⊂ T.

Note that |u′·w| ⊂ T and as above, the flag K/T lies in acl(A). Lemma 6.20 implies that |w · v_{1}| ⊂ T. Since the word û_{1} · w · v_{1} is reduced, no letter of the commuting word w · v_{1} is contained in û_{1}. Therefore w · v_{1} and û_{1} commute, so

ũ = û_{1} · w · ũ′ ⊂ û_{1} · w · v_{1} = ũ_{A}.

To conclude, notice that if |v′| ⊂ S_{R}(u_{A}), then G_{A}/S_{R}(u_{A}) = G_{B}/S_{R}(u_{A}), which would imply F | ⌣_{A∩B} A by Corollary 6.8. Therefore, if F |̸ ⌣_{A∩B} A, then neither ũ = ũ_{A} nor |v′| ⊂ ũ: for the first case, if ũ = ũ_{A}, then ũ′ = v_{1} and hence u′ = v_{1} = 1, since ũ′ is properly absorbed by v_{1}. For the latter, if |v′| ⊂ ũ, then |v′| ⊂ ũ_{A} ⊂ S_{R}(u_{A}). □

If the graph Γ has no edges, the theory PS_{Γ} is the theory of an infinite set M partitioned into |Γ| many infinite sets A_{γ}. This is a trivial theory of Morley rank 1 (and degree |Γ|) which is easily seen not to be 1-ample.

For a graph with at least one edge, we define its minimal valency as the minimum of the valencies of non-isolated vertices. In particular, it is at least 1.

Theorem 8.6. Let Γ be a graph with at least one edge. Let r be its minimal valency and n in ℕ be maximal such that the graph [0, n]:

\begin{matrix}0 \\ 1 \\ 2 \\ n − 1 \\ n \end{matrix}

embeds as a full subgraph of Γ. Then the theory PS_{Γ} is n-ample but not (|Γ|−r+1)- ample.

If Γ contains a full subgraph isomorphic to [0, n], for some n ∈ ℕ, then n ≤ |Γ| and r ≤ |Γ| − n, since the graph [0, n] has minimal valency 1. Thus |Γ| − r + 1 is always bigger than n, as expected. For the graph [0, n], the theorem says that its associated theory is n-ample but not (n + 1)-ample (cf. [15, Theorem 3.3], [2, Theorem 8.4]), hence the bounds are best possible, similarly as for the graph consisting 0, …, n + 1 arranged in a circular way;

\begin{matrix}2 \\ 1 \\ 0 \\ n + 1 \\ n \end{matrix}

which has valency 2, so its theory is n-ample yet not (n + 1)-ample.

In particular, the theory of Γ is not 1-based if and only if Γ contains at least one edge. The complete graph 𝕂_{n} has minimal valency n − 1 and the theory PS_{𝕂_{n}} is CM-trivial for every n.

Proof. Suppose that [0, n] embeds as a full subgraph in Γ. Fix some flag F and consider the collection of flags [0, n]-equivalent to F. Corollary 8.4 and [2, Theorem 8.4] imply that PS_{Γ} is n-ample.

Suppose now that PS_{Γ} is N-ample for some natural number N, and let a_{0}, …, a_{N} be enumerations of small models as in Lemma 8.2. Total triviality of PS_{Γ} implies that we may replace a_{N} by a flag F. For 0 ≤ i ≤ N − 1, let u^{i} be the reduced word connecting F to a base-point G_{i} in the nice set a_{i}. Lemma 8.5 applied to each triangle (F, a_{i}, a_{i+1}) implies that the final segment ũ^{i+1} of u^{i+1} is properly contained in the final segment ũ^{i} of u^{i}. In particular |ũ^{1}| ≥ N − 1.

Let v be the reduced word connecting G_{1} to G_{0}. Lemma 8.5 implies the existence of a word v′ which is properly right-absorbed by u^{1} and such that |v′| is not contained in ũ^{1}. Let γ be in |v′| \ ũ^{1}. Since v′ is absorbed by u^{1}, so is γ. Thus γ commutes with ũ^{1} and must be properly right-absorbed by u^{1}. Hence γ is not isolated and has the valency at most |Γ| − |ũ^{1}| − 1. So r ≤ |Γ| − N, that is N < |Γ| − r + 1. □

References

[1] A. Baudisch, Kommutationsgleichungen in semifreien Gruppen, Acta Math. Acad. Sci. Hungar., 29, (1977), 235–249.

[2] A. Baudisch, A. Martin-Pizarro, M. Ziegler, Ample Hierarchy, Fund. Math., 224, (2014), 97–153

[3] A. Baudisch, A. Pillay, A free pseudospace, J. Symb. Logic, 65, (2000), 443–460.

[4] D. Evans, Ample dividing, J. Symb. Logic, 68, (2003), 1385–1402.

[5] J. B. Goode, Some trivial considerations, J. Symb. Logic 56, (1991), 624–631.

[6] T. Grundhöfer, Basics on buildings, in Tits buildings and the model theory of groups, London Math. Soc. Lecture Note Ser., 291, (2002), 1–21.

[7] F. Haglund, F. Paulin, Constructions arborescentes d’immeubles, Math. Ann., 325, (2003), 137–164.

[8] E. Hrushovski, On stable non-equational theories, unpublished notes, (1991).

[9] E. Hrushovski, A new strongly minimal set, Annals of Pure and Applied Logic, 62, (1993), 147–166 .

[10] E. Hrushovski, A. Pillay, Weakly normal groups, Stud. Logic Found. Math., 122, 233–244, (1987).

[11] M. Junker, A note on equational theories, J. Symb. Logic, 65, (2000), 1705–1712.

[12] A. Pillay, The geometry of forking and groups of finite Morley rank, J. Symb. Logic, 60, (1995), 1251–1259.

[13] A. Pillay, A note on CM-triviality and the geometry of forking, J. Symb. Logic, 65, (2000), 474–480.

[14] A. Pillay, G. Srour, Closed Sets and Chain Conditions in Stable Theories, J. Symb. Logic, 49, (1984), 1350–1362.

[15] K. Tent, The free pseudospace is N-ample, but not (N +1)-ample, J. Symb. Logic, 79, (2014), 410–428.

[16] K. Tent, M. Ziegler, A Course in Model Theory, ASL Lecture Note Series, Cambridge University Press (2012)

[17] M. Ziegler, Strong Fraïssé limits, preprint, http://home.mathematik.uni-freiburg.de/

ziegler/preprints/starker_fraisse.pdf, (2011).

Institut für Mathematik,Humboldt-Universität zu Berlin, D-10099 Berlin, Germany Université de Lyon, CNRS UMR 5208, Université Lyon 1, Institut Camille Jordan, 43

boulevard du 11 novembre 1918, F–69622 Villeurbanne Cedex, France

Mathematisches Institut, Albert-Ludwigs-Universität Freiburg, D-79104 Freiburg, Germany

E-mail address: baudisch@mathematik.hu-berlin.de
E-mail address: pizarro@math.univ-lyon1.fr
E-mail address: ziegler@uni-freiburg.de