Extending partial isomorphisms for

the small index property of many ω–categorical structures

BERNHARD HERWIG June 1996, revised June 1997

Abstract

Theorem: Let A be a finite K_{m}–free graph, p_{1}, …, p_{n} partial isomorphisms on A. Then there exists a finite extension B, which is also a K_{m}–free graph, and automorphisms f_{i} of B extending the p_{i}. A paper by Hodges, Hodkinson, Lascar and Shelah shows how this theorem can be used to prove the small index property for the generic countable graph of this class. The same method also works for a certain class of continuum many non–isomorphic ω–categorical countable digraphs and more generally for structures in an arbitrary finite relational language, which are built in a similar fashion.

Hrushovski proved this theorem for the class of all finite graphs [Hr]; the proof presented here stems from his proof.

1. Introduction

We say a class 𝒦 of structures has the extension property for partial isomorphisms, (EP) for short, if for every finite structure A∈𝒦 and p_{1}, …, p_{n} partial isomorphisms on A, there exists a finite structure B∈𝒦 and f_{1}, …, f_{n}∈Aut(B) such that f_{i} extends p_{i}. The main points are: We want to stay in the realm of finite structures, so B has to be finite; we want to stay inside the class 𝒦 ; we want to solve the extension problem simultaneously in one extending structure for finitely many partial isomorphisms.

The question “does the (EP) hold for graphs” arose in work by Hodges, Hodkinson, Lascar and Shelah on the small index property for the random graph [HHLS]. They realized that this question (EP) is important to understand the automorphism group of the random graph as a topological group. More precisely: The extension property for graphs just shows that most of the n– tuples of automorphisms of the random graph (in the sense of Baire Category) are locally finite. See also section 5 for this relationship. We want to extend these results to more classes of structures.

In section 4 of this paper we will consider classes 𝒦 of relational irreflexive structures, which are definable by axioms of a certain type, namely axioms of the type “every structure in 𝒦 weakly avoids T ” (where T is a “packed” S– structure; by a packed structure we mean a structure T such that for every a, b∈T, if a ≠ b then there exists an atomic formula Ra_{1} … a_{r} which holds and in which a and b are appearing) and axioms of the type “if a_{1}, …, a_{m} ∈A∈𝒦 are elements which are linked (i.e. Ra_{1} … a_{m} holds for some R in the language), then the quantifier–free formula φ(a_{1}, …, a_{m}) holds”. We will show, that if a class has such an axiom system, then the (EP) holds for 𝒦 . From this follows with the same proof as in [HHLS], that the automorphism group of the generic countable structure of this class –which exists in this case– has the small index property.

There are two examples of such classes we want to mention:

1. The K_{m}–free graphs, where m∈ω and K_{m} is the complete graph with m edges.

2. Certain classes of digraphs, which are defined in a similar way by omitting a given (possibly infinite) set of tournaments.

This second example is due to Henson, who introduced these digraphs to construct continuum many non–isomorphic countable ω–categorical digraphs ([Hen]). The results in this paper will show that all the automorphism groups of these digraphs have the small index property. In [Hg] we have already treated the K_{3}–free case. Also we introduced the technique of permorphisms, which we are also going to use in the present paper. We will need a general extension lemma for permorphisms, which we prove in Section 2. This lemma is nearly already proved in [Hg], but unfortunately not in the generality which is needed here. Furthermore we need a special feature of this extension, which we did not prove there. It might be a good strategy to start reading section 3 before reading section 2, because there is a more detailed description of the ideas of the proofs; in particular the notion of permorphisms is motivated there.

In section 3 we will prove the extension property for the example 1. In section 4 we will handle the general case. We have chosen to go this way rather then to first prove the general case, because we think that the proof in the general case without an understanding of the simpler case is quite hard to follow. Also section 3 is meant for the reader who is not interested in arbitrary relational structures, but only in graphs, and who might want to skip the proof in section 4. For technical reasons we restrict attention to irreflexive structures in section 4.

In a joint paper with Daniel Lascar [HL] there will be treated a weaker variant of the (EP): a class 𝒦 has the weak extension property for partial isomorphisms (WEP), if whenever for A, p_{1}, …, p_{n} there exists a possibly infinite solution M, g_{1}, …, g_{n}, then there exists also a finite solution B, f_{1}, …, f_{n} (A, B, M structures in 𝒦 ; a solution is a structure in 𝒦 together with an n-tuple of automorphisms extending the given partial isomorphisms). There the (WEP) for several classes will be proved and a connection between this property and results on the free groups in finitely many generators considered as topological groups will be developed. In the cases we consider in this paper the (EP) and the (WEP) are equivalent, because there it is easy to give an infinite solution.

In section 5 we will explain the connection between the (EP) for a class 𝒦 and properties of the automorphism group of the generic countable structure in 𝒦 , considered as a topological group. This relationship has already been explained in [HHLS]; we will only add a few remarks due to the slightly different situation.

In section 6 we are discussing some of the preconditions under which the general theorem was proved in section 4. In particular we extend the theorem to structures which are not irreflexive.

Apart from the two areas already mentioned (the Small Index Property and topological properties of free groups) there are other fields in which various extension results for partial isomorphisms are used. Let me mention infinite combinatorics (see [GGK]), finite model theory (see [Gr]) and cylindric algebras (see [AHN]). Notably in the last field one uses a strong result on extending partial isomorphisms.

I would like to thank Daniel Lascar and Elisabeth Bouscaren, who patiently listened to older and more complicated versions of this proof and who gave helpful suggestions on how to make it easier. I also would like to thank Dugald Macpherson and Ian Hodkinson for helpful remarks.

Notation: By A ⊂ B we denote inclusion (and not proper inclusion). If p is a partial function on a set A, then D(p) will denote the domain of p, and by R(p) the range of p (so D(p) ⊂ A and R(p) ⊂ A). If p and f are functions we write p⊂f for f extends p, i.e. D(p)⊂D(f) and for a∈D(p) : a^{p} = a^{f}. By a partial mapping we will always mean an injective partial function. If ā is a tuple, say ā = a_{1} … a_{r} and D is a set, we write ā∈D for a_{1}∈D and … and a_{r} ∈D, and if ā∈D(p) we denote by ā^{p} the tuple a_{1}^{p}, …, a_{r}^{p}. The cardinality of a set D will be denoted by ^{#}D. Throughout the paper p_{1}, … p_{n} will be partial mappings and D_{i} := D(p_{i}) and D′_{i} := R(p_{i}), so p_{i} maps D_{i} bijectively to D′_{i}.

2. The plain lemma for permorphisms

In this section we are working in the class of all finite S–structures, for a finite relational language S. “Plain lemma” is just meant to mean: no further restrictions on the S–structures; it is the basic step.

Definition: Let S be a relational language. Let χ be a permutation of the symbols in S mapping every symbol to a symbol with the same arity. Let A be an S–structure and p be a partial mapping on A. We call p a χ–permorphism, if for every r ∈ ω and every r–ary relation R in S and every a_{1}, …, a_{r} ∈ D(p): Ra_{1} … a_{r} ⟺ R^{χ}a_{1}^{p} … a_{r}^{p}.

Lemma 1 Let S be a finite relational language, let χ_{1}, …, χ_{n} be permutations of the language mapping every symbol to a symbol of the same arity. Let A be a finite S–structure. Let p_{1}, …, p_{n} be partial mappings on A, such that p_{i} is a χ_{i}–permorphism. Then there exists a finite S–structure B, A ⊂ B, and f_{1}, …, f_{n}∈Sym(B) such that each f_{i} is a χ_{i}–permorphism and such that p_{i} ⊂f_{i}. We can choose B to satisfy in addition:

1. ∀b∈B∃f ∈<f_{1}, …, f_{n} >: b^{f} ∈A,

2. for every R r–ary in S for all b_{1}, …, b_{r} ∈B if Rb_{1} … b_{r} then there exists f ∈<f_{1}, …, f_{n} > such that for 1^{≤} i^{≤} r b_{i}^{f} ∈A,

3. If the maximal arity of S is bigger than 1 then: whenever there is given f ∈ < f_{1}, …, f_{n} > and a, b ∈ A such that a^{f} = b then there exists t ∈ ω p_{i_{1}}, …, p_{i_{t}} ∈ {p_{1}, …, p_{n}} and ϵ_{1}, …, ϵ_{t} ∈ {−1, 1} such that a^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = b and f_{i_{1}}^{ϵ_{1}} … f_{i_{t}}^{ϵ_{t}} = f

< f_{1}, …, f_{n} > is the subgroup of Sym(B) generated by f_{1}, …, f_{n}. Conditions 1 and 2 just mean that B only contains the structure which is necessary. These conditions are easy to achieve even if B would not have them to begin with: One first replaces B by the substructure {a^{f} | a ∈ A, f ∈ < f_{1}, …, f_{n} >} and then one cuts down the interpretation of a relation symbol R to all the tuples of the form ā^{f}, where ā∈A and f ∈<f_{1}, …, f_{n} > and Rā holds (in A). In Condition 3 p_{i_{1}}^{ϵ_{1}} … p_{i_{t}}^{ϵ_{t}} means the concatenation of partial mappings. In the case t = 0 this empty concatenation of partial isomorphisms is defined to be the identity on A. The condition means: a and b in the original structure A are only mapped to each other via f inside B if this is necessary given the information of the p_{i}. We will have this condition automatically at the end. The precondition on the maximal arity in 3 is just included to make the proof easier. We are not interested in the case of just unary relation symbols.

Proof: The proof is by induction on the maximal arity of relation symbols in S. The case of this arity being 1 is easy and is already treated in [Hg].

Let the maximal arity be s, s^{≥} 2. Let S_{s} be the set of relation symbols in S of arity s.

Definition:

1. A Δ–type over A is a collection of formulae of the form Rxā, where R∈S and ā∈A. If C ⊃A and c∈C then by Δ-tp(c/A) we denote the collection of all the formulae of form Rxā which hold for c in C. Note that the meaning of “Δ-tp(c/A)” will be different in the different chapters.

2. if p is a Δ–type over A and A_{0} ⊂A⊂C and c∈C, then p À_{0} := {Rxā∈p | ā∈A_{0}} and Δ-tp(c/A_{0}) := Δ-tp(c/A) À_{0} = {Rxā | ā∈A_{0}, Rcā holds}.

3. If φ is a formula of the form Rxā with ā∈D_{i}, then φ^{p_{i}} := R^{χ_{i}}xā^{p_{i}}; note that φ^{p_{i}} does not only depend on p_{i} but also on χ_{i}.

4. If p is a Δ–type over D_{i} then p^{p_{i}} := {φ^{p_{i}} | φ ∈ p} is a Δ–type over D′_{i}. It is the type p transported by the permorphism p_{i}, (remember D_{i} = D(p_{i}), D′_{i} = R(p_{i})).

Claim: There exists a finite S–structure C, A⊂C such that

a) there exists a constant c_{0} such that for every Δ–type p over A:

#{c∈C | Δ-tp(c/A) = p} = c_{0},

b) there exists bijections h_{1}, …, h_{n}∈Sym(C), h_{i} ⊃p_{i} such that for every ā∈D_{i}, b∈C, R∈S: Rbā ⟺ R^{χ_{i}}b^{h_{i}}ā^{p_{i}}.

Proof: a) for a Δ–type p over A we let c_{p} := ^{#}{c ∈ A | Δ-tp(c/A) = p} and c_{0} := max{c_{p} | p Δ–type over A}. Now for every Δ–type p over A we add (c_{0} − c_{p}) many new points c with Δ-tp(c/A) = p. Note that we do not consider instances of the relations between these new points; for a clear picture we can suppose that every new instance of a relation involves exactly one new point (and some old points from A).

b) Fix i (1^{≤} i^{≤} n). Note that the statement of b) just says, that if Δ-tp(b/D_{i}) = p, then Δ-tp(b^{h_{i}}/D′_{i}) = p^{p_{i}}. Let p be a Δ–type over D_{i} and p′ := p^{p_{i}}. The key for the proof of 2. is the following observation: there are as many possibilities to extend the type p to a type over A as there are to extend p′. More precisely, if we denote Q(p) = {q | q Δ–type over A, q D̀_{i} = p} and likewise Q(p′) = {q | q Δ–type over A, q ` D′_{i} = p′} then ^{#}Q(p) = ^{#}Q(p′): For any A_{0} ⊂ A let F (A_{0}) = {Rxā | R ∈ S, ā ∈ A_{0}}. Obviously ^{#}F (D_{i}) = #F (D′_{i}), so^{#}(F (A)−F (D_{i})) = ^{#}(F (A)−F (D′_{i})). The elements of F (A)−F (D_{i}) are the formulae we might add to p without changing the type over D_{i}: Q(p) = {p ∪ r | r ⊂(F (A) − F (D_{i}))}. So ^{#}Q(p) = 2^{#(F (A)−F (D_{i}))} and likewise ^{#}Q(p′) = 2^{#(F (A)−F (D′_{i}))} = ^{#}Q(p). Now we prove the crucial equality

#({c∈C | Δ-tp(c/D_{i}) = p}) = ^{#}({c∈C | Δ-tp(c/D′_{i}) = p^{p_{i}}}) :

#({c∈C | Δ-tp(c/D_{i}) = p}) = ∑_{qϵQ(p)}^{#}({c∈C | Δ-tp(c/A) = q}) = c_{0} ·^{#}Q(p)

and likewise

#({c∈C | Δ-tp(c/D′_{i}) = p′}) = c_{0} ·^{#}Q(p′) = c_{0} ·^{#}Q(p)

Now we can choose h_{i} to map every set {c∈C | Δ-tp(c/D_{i}) = p} bijectively to {c∈C | Δ-tp(c/D′_{i}) = p^{p_{i}}}; furthermore we can choose h_{i} to extend p_{i} because if a∈D_{i} and a∈{c∈C | Δ-tp(c/D_{i}) = p}, then a^{p_{i}} ∈{c∈C | Δ-tp(c/D′_{i}) = p^{p_{i}}}.

We introduce the language S′ := (S − S_{s}) ∪ {R_{c} | c∈C, R∈S_{s}}, where the R_{c} are new (s−1)–ary relation symbol. We consider A as an S′–structure (and call it A′), by defining

A′ ⊧ R_{c}ā ⟺ C ⊧ Rcā.

The maximal arity in S′ is (s−1). If we define χ′_{i} on {R_{c} | c ∈ C, R ∈ S_{s}} by R_{c}^{χ′_{i}} := (R^{χ_{i}})_{c^{h_{i}}} (and for R ∈ S − S_{s} by R^{χ′_{i}} := R^{χ_{i}}), then p_{i} is a χ′_{i}– permorphism on A′. So we get by induction a finite S′–structure F, A′ ⊂F and φ_{1}, …, φ_{n}∈Sym(F), φ_{i} ⊃p_{i}, φ_{i} a χ′_{i}–permorphism. We will not need the extra properties for F mentioned in the lemma.

Now we let Γ⊂Sym(S) × Sym(F) × Sym(C) be the subgroup generated by the elements γ_{i} := (χ_{i}, φ_{i}, h_{i}). As a convention the components of an element γ ∈ Γ will always be called χ, φ and h, i.e. γ = (χ, φ, h). Γ operates on S (by R^{γ} := R^{χ}), on F (by d^{γ} := d^{φ}), on C (by c^{γ} := c^{h}), and on S′ (by (R_{c})^{γ} := (R^{χ})_{c^{h}}). But we have to be careful with this notation, because for a ∈ A a^{γ} might mean a^{h} or a^{φ}, which might be different; we will only apply the notation to relation symbols. For γ = (χ, φ, h) ∈ Γ we have that φ is a γ–permorphism on F (of course only with respect to relation symbols in S′). This is true for the generators of Γ and it extends to the whole group.

On A×Γ we define the equivalence relation ≡ to be the symmetric, reflexive and transitive closure of

E = {((a^{p_{i}}, γ), (a, γ_{i}γ)) | 1^{≤} i^{≤} n, a∈D_{i}, γ ∈Γ}.

We note some basic facts:

(1) If (a, (χ, φ, h))≡ (a^{∗}, (χ^{∗}, φ^{∗}, h^{∗})) then a^{φ} = (a^{∗})^{φ^{∗}} and a^{h} = (a^{∗})^{h^{∗}},

(2) If R ∈ S ∪ S′ is r–ary and (a_{1}, γ)≡ (a_{1}^{∗}, γ^{∗}) and … and (a_{r}, γ)≡ (a_{r}^{∗}, γ^{∗}) then R^{γ^{−1}}a_{1} … a_{r} ⟺ R^{(γ^{∗})^{−1}}a_{1}^{∗} … a_{r}^{∗}.

Proof:

(1) It suffices to prove (1) in the cases ((a, (χ, φ, h)), (a^{∗}, (χ^{∗}, φ^{∗}, h^{∗}))) ∈ E, (a^{∗})^{p_{i}} = a and (χ^{∗}, φ^{∗}, h^{∗}) = (χ_{i}, φ_{i}, h_{i}) · (χ, φ, h). But then a^{φ} = (a^{∗})^{p_{i}φ} = (a^{∗})^{φ_{i}φ} = (a^{∗})^{φ^{∗}} and a^{h} = (a^{∗})^{p_{i}h} = (a^{∗})^{h^{∗}}.

(2) Let γ = (χ, φ, h) and γ^{∗} = (χ^{∗}, φ^{∗}, h^{∗}), so φ is a γ–permorphism and φ^{∗} is a γ^{∗}–permorphism (on the S′–structure F). Case S′: We consider A′. We have for R ∈ S′: R^{γ^{−1}}a_{1} … a_{r} ⟺ Ra_{1}^{φ} … a_{r}^{φ} ⟺ R(a_{1}^{∗})^{φ^{∗}} … (a_{r}^{∗})^{φ^{∗}} ⟺ R^{(γ^{∗})^{−1}}a_{1}^{∗} … a_{r}^{∗}. For the middle equivalence we used (1). Case S: Let R∈S_{s} (otherwise it follows from the previous case). R^{χ^{−1}}a_{1} … a_{s} ⟺ (R^{χ^{−1}})_{a_{1}}a_{2} … a_{s} ⟺ R_{a_{1}^{h}}a_{2}^{φ} … a_{s}^{φ} ⟺ ⟺ R_{(a_{1}^{∗})^{h^{∗}}} (a_{2}^{∗})^{φ^{∗}} … (a_{s}^{∗})^{φ^{∗}} ⟺ R^{(χ^{∗})^{−1}}a_{1}^{∗} … a_{s}^{∗}. Here we are using

that φ is a γ–permorphism for S′ and that ((R^{χ^{−1}})_{a_{1}})^{γ} = R_{a_{1}^{h}} and similarly with the ∗.

Now we are ready to define an S–structure on A × Γ/≡: For e_{1}, …, e_{r} ∈A × Γ/≡ and R∈S we define: Re_{1} … e_{r} ⟺ ∃γ ∈Γ ∃a_{1}, …, a_{r} ∈A (e_{i} = (a_{i}, γ)/≡ and R^{γ^{−1}}a_{1} … a_{r}). We note that

(3) R^{γ}(a_{1}, γ)/≡ … (a_{r}, γ)/≡ ⟺ Ra_{1} … a_{r}.

(4) if (a, γ_{1})≡ (b, γ_{2}), then there exists t ∈ ω, p_{i_{1}}, …, p_{i_{t}} ∈ {p_{1}, …, p_{n}} and ϵ_{1}, …, ϵ_{t}∈{−1, 1} such that b^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = a and γ_{2} = γ_{i_{1}}^{ϵ_{1}} … γ_{i_{t}}^{ϵ_{t}}γ_{1}.

(3) follows directly from (2) and it suffices to prove (4) in the case (a, γ_{1})E(b, γ_{2}) and a = b^{p_{i}}, γ_{2} = γ_{i}γ_{1}, where it is obvious. In fact in (4) also the reverse implication holds, so (4) just gives a description of the reflexive, symmetric and transitive closure of E.

We define a map i : A → A × Γ/≡ by i(a) := (a, 1)/≡ (where 1 is the unit element in the group). i is injective: if (a, 1)≡ (b, 1) then by (1) a = b. By (3) i is an embedding of A into A × Γ/≡ as S–structures. By identifying we suppose A⊂A × Γ/≡ and we set B = A × Γ/≡.

We define the permorphism f_{i} (for 1^{≤} i^{≤} n) by ((a, γ)/≡)^{f_{i}} := (a, γγ_{i})/≡. f_{i} is well defined; f_{i} is an χ_{i}–permorphism, because of fact (3); for 1^{≤} i^{≤} n we have p_{i} ⊂f_{i}, because if a^{p_{i}} = b then ((a, 1)/≡)^{f_{i}} = (a, γ_{i})/≡ = (a^{p_{i}}, 1)/≡ = (b, 1)/≡.

Properties 1 and 2 are easy; for the additional property 3 suppose ((a, 1)/≡)^{f} = (b, 1)/≡, where f ∈ < f_{1}, …, f_{n} >. Take γ ∈ Γ such that for all d ∈ A and γ′ ∈Γ ((d, γ′)/≡)^{f} = (d, γ′γ)/≡. Then (b, 1)≡ (a, γ) and by fact (4) there exists p_{i_{1}}, …, p_{i_{t}} ∈ {p_{1}, …, p_{n}} and ϵ_{1}, …, ϵ_{t} ∈ {−1, 1} such that a^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = b and γ = γ_{i_{1}}^{ϵ_{1}} … γ_{i_{t}}^{ϵ_{t}}. So f = f_{i_{1}}^{ϵ_{1}} … f_{i_{t}}^{ϵ_{t}} as desired.

The size of the structure B constructed in this proof is very large in terms of the given data. Therefore we did not try hard to be a little more economical in our construction of the structure B. But nevertheless we want to give an upper bound for the size of B. This bound is an iterated exponential function. We denote by itexp(r, ·) the r times iterated exponential function on natural numbers, which has the following inductive definition: itexp(0, s) := s; itexp(r + 1, s) := 2^{itexp(r,s)}. Let us suppose the maximal arity of relation symbols in S is r^{≥} 2 and that S contains l_{j} many symbols of arity j (for 1^{≤} j^{≤} r). Let p(x) = l_{1} + l_{2}x + … + l_{r−1}x^{r−2} + 2l_{r}x^{r−1}.

Claim: If we suppose the structure A is of cardinality c, then for the structure B constructed in the proof of Lemma 1 we have ^{#}B ≤itexp(2r − 1, p(c)).

The proof of this claim is fairly routine but a little bit tedious. We will only sketch the proof. To start one has to compute that in the unary case one can find a structure B of size c · 2^{l_{1}}. Then the proof is by induction on r. We assume r ^{≥} 3 (the case r = 2 being similar). The number of Δ–types over A equals t = 2^{p(c)−l_{r}c^{(r−1)}}. The cardinality of C constructed at the beginning of the proof can be bounded by ct. The number of new (r − 1)-ary predicates in the new language S′ is bounded by l_{r} · c · t. By induction we find a structure F of size bounded by itexp(2r − 3, l_{1} + … + l_{r−2}c^{r−3} + 2l_{r−1}c^{r−2} + 2l_{r}c^{r−1}t). For Sym(F) we are using the bound 2^{log_{2}#F ·#F}. We obtain a bound for A × Γ by multiplying c and a bound for the number of arity preserving permutations of S and a bound for Sym(C) and for Sym(F). As the other numbers are fairly small compared to Sym(F), you can easily obtain the bound itexp(2r − 1, p(c)) for this number (the additional term l_{r}c^{r−1} is just meant to swallow all these smaller numbers). As B = A × Γ/≡ the above bound also holds for B.

3. The case of the graphs

Definition: In this paper graphs are undirected and loop free and R denotes the edge relation.

A graph A is called K_{m}–free (for m∈ω), if K_{m}, which is the complete graph with m vertices, is not embeddable into A, i.e. there do not exist a_{1}, …, a_{m}∈A such that a_{k}Ra_{l} (for 1^{≤} k < l^{≤} m).

Theorem 2 Let m, n ^{≥} 1, let A be a finite K_{m}–free graph. Let p_{1}, …, p_{n} be partial isomorphisms on A. There exists a finite K_{m}–free graph B, B ⊃A, and f_{1}, …, f_{n}∈Aut(B), such that f_{i} ⊃p_{i}.

Before going through the formal proof, which looks a little bit technical, let us describe the main ideas of the proof: The proof in the general case will be by induction on m. Let us introduce for every a ∈ A a new colour (i.e. a unary predicate) U_{a} such that if b ∈ A then b is of colour U_{a} iff bRa. Now A is K_{m}–free if and only if you can not embed K_{m−1} “uni–coloured” into A; the latter means there does not exist a colour U_{a} and elements a_{1}, …, a_{m−1} in A such that a_{k}Ra_{l} (1 ^{≤} k < l ^{≤} m) and all the a_{i} are of colour U_{a}. Thus one can reduce K_{m}–freeness conditions to certain K_{m−1}–freeness conditions, if one works with coloured graphs. Here are the main problems which one has to overcome doing this reduction.

1. With respect to the colours, p_{i} is not longer a partial isomorphism, but it is a permorphism, i.e. it respects the colours only up to a permutation χ_{i} of the colours ((U_{a})^{χ_{i}} = U_{a^{p_{i}}}).

2. χ_{i} is not yet really a permutation of the set of colours {U_{a} | a ∈ A}, but it is only a partial function. As in [Hg] one overcomes this problem by doing a type–realizing step to get a nice graph C ⊃ A; afterwards one looks at the colours {U_{d} | d∈C} and extends the partially already defined functions χ_{i} to permutations of this set.

3. If one extends the graph A considered as a (uni–coloured K_{m−1})–free graph to a (uni–coloured K_{m−1})–free graph B and the p_{i} to f_{i}, how can one ensure that B is K_{m}–free? Take into account that B is {U_{d} | d ∈ C}–coloured, so we don’t have for every b ∈ B a colour U_{b} such that all neighbours of b have colour U_{b}. This problem disappears by miracle: The resulting graph B looks locally like A. In particular, for every a ∈ A the neighbours of a in B will still all have colour U_{a}. Now any orbit of the automorphism group of B (as graph) will have an element inside A. So to check K_{m}–freeness of B, one has only to look for copies of K_{m} having one element a inside A, but such a copy would lead to a copy of K_{m−1} of colour U_{a}.

4. To get a proper induction, one has to prove the theorem for coloured graphs and permorphisms. Starting with a coloured graph, we have to introduce a new set of colours {U_{d} | d ∈ C}. But (uni–coloured K_{m})– freeness does not exactly mean (uni–coloured K_{m−1})–freeness with respect to the new colours. It means precisely: there do not exist an old colour U, some a of colour U, a new colour U_{a} and a U_{a}–coloured copy of K_{m−1} which is at the same time U–coloured. We will call such a combination (U, U_{a}) a critical colouring, and we have to avoid copies of K_{m−1} which are critical coloured. This last problem and the notational complication arising from the fact that we are dealing with permorphisms rather than isomorphisms will make the proof look rather technical.

The definitions which follow, and the version of the theorem (i.e. Lemma 3), which will be provable by induction, should now be sufficiently motivated.

Definition: Let 𝒰^{1}, …, 𝒰^{r} be a family of disjoint finite sets of unary predicates (called colours). Let 𝒰 := ⋃_{1 ^{≤} j ^{≤} r} 𝒰^{j}. If A is an {R}∪𝒰 –structure and a∈A, V ∈ 𝒰 , then we write a ∈ V or Va to indicate that the unary predicate V (or rather its interpretation in A) is true for a; we also write “a is of colour V ”.

1. A 𝒰 –graph is an {R} ∪ 𝒰 –structure A such that A considered as an {R}– structure is a graph.

For a∈A we define 𝒰 (a) := {V ∈𝒰 | a∈V }.

2. Let 𝒰_{c} ⊂𝒰^{1} × … × 𝒰^{r}. We will call 𝒰_{c} the set of critical colourings. We say that A is 𝒰_{c}-K_{m}–free (for m ∈ ω), if there do not exist a colouring (V_{1}, …, V_{r})∈𝒰_{c} and elements a_{1}, …, a_{m}∈A, such that a_{k}Ra_{l} (for 1^{≤} k < l^{≤} m) and a_{k} ∈V_{j} (for 1^{≤} k^{≤} m, 1^{≤} j ^{≤} r).

The next lemma is the permorphism version of Theorem 2. This is the version we are able to prove by induction on m.

Lemma 3 Let m^{≥} 1. Let 𝒰^{1}, …, 𝒰^{r} be disjoint sets of colours (where r^{≥} 0). Let 𝒰 := ⋃_{1 ^{≤} j ^{≤} r} 𝒰^{j}. Let χ_{i}^{j} ∈Sym(𝒰^{j}) (for 1^{≤} i^{≤} n, 1^{≤} j^{≤} r), S := 𝒰 ∪{R} χ_{i} := ⋃_{0 ^{≤} j ^{≤} r} χ_{i}^{j} ∈Sym(S), where χ_{i}^{0} is the identity on {R}. Furthermore let

𝒰_{c} ⊂𝒰^{1}×…×𝒰^{r} be a set called critical colourings. Suppose 𝒰_{c} is χ_{i}–invariant (for 1^{≤} i^{≤} n).

Let A be a finite 𝒰_{c}-K_{m}–free 𝒰 –graph and suppose p_{1}, …, p_{n} are partial mappings on A such that p_{i} is a χ_{i}–permorphism.

Then there exist a finite 𝒰 –graph B, B ⊃ A, B 𝒰_{c}-K_{m}–free, f_{1}, …, f_{n} ∈ Sym(B), f_{i} ⊃p_{i}, f_{i} a χ_{i}–permorphism (for 1^{≤} i^{≤} n).

B can be chosen to satisfy in addition:

1. ∀b∈B∃f ∈<f_{1}, …, f_{n} >: b^{f} ∈A,

2. for all a, b∈B if aRb then there exists f ∈<f_{1}, …, f_{n} > with a^{f}, b^{f} ∈A,

3. whenever there exists f ∈<f_{1}, …, f_{n} > and a, b∈A such that a^{f} = b then there exists t ∈ ω p_{i_{1}}, …, p_{i_{t}} ∈ {p_{1}, …, p_{n}} and ϵ_{1}, …, ϵ_{t} ∈ {−1, 1} such that a^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = b and f_{i_{1}}^{ϵ_{1}} … f_{i_{t}}^{ϵ_{t}} = f

From the lemma follows the theorem: Let r = 0 which means we just talk about (uncoloured) graphs. 𝒰_{1} × … × 𝒰_{r} just contains the empty tuple λ and we let 𝒰_{c} = {λ}; then 𝒰_{c}-K_{m}–freeness just means K_{m}–freeness. Now χ_{i} is the identity on {R} and χ_{i}–permorphism just means isomorphism of graphs.

Proof of the lemma: The proof goes by induction on m. Let us first treat the case m = 1. By Lemma 1 there exists B ⊃A, B a 𝒰 –graph, and f_{1}, …, f_{n}∈Aut(B), p_{i} ⊂f_{i}, f_{i} a χ_{i}–permorphism, having all the extra properties we want for B (use property 2 to check that B is really a graph, i.e. R is irreflexive and symmetric). We have to check that B is 𝒰_{c}-K_{1}–free. Suppose there exists b∈B and (V_{1}, …, V_{r})∈𝒰_{c}, such that b ∈ V_{j} (1 ^{≤} j ^{≤} r). Choose f ∈ < f_{1}, …, f_{n} > such that b^{f} ∈ A and choose χ ∈ < χ_{1}, …, χ_{n} > such that f is a χ–permorphism. It follows that b^{f} ∈A, (V_{1}^{χ}, …, V_{r}^{χ})∈𝒰_{c}, b^{f} ∈V_{j}^{χ}. This contradicts the 𝒰_{c}-K_{1}–freeness of A.

Now we do the step of induction m → m + 1 (m^{≥} 1): We have the set of colours 𝒰^{1}, …, 𝒰^{r} and we suppose A to be 𝒰_{c}-K_{m+1}–free. By a type–realizing step and by introducing new colours we want to consider A as satisfying a certain K_{m}–freeness condition and then we want to apply the lemma for m.

A subset A_{0} ⊂ A and a colouring 𝒰_{0} ⊂ 𝒰 determine a type over A in this context, namely the type {xRa | a ∈ A_{0}} ∪ {V x | V ∈ 𝒰_{0}} (see the following definition). But not all of the types are realizable in 𝒰_{c}-K_{m+1}–free graphs.

Definition: Let A ⊂ C be 𝒰 -graphs. p will denote a Δ–type over A, c an element of C.

1. A Δ–type over A is a collection of formulae of the form Vx (where V ∈𝒰 ) and of the form xRa (where a ∈ A). We let Δ-tp(c/A) := {Vx | C ⊧ Vc} ∪ {xRa | a ∈ A, C ⊧ cRa} and Par(p) := {a ∈ A | xRa ∈ p}, the parameters of p and 𝒰 (p) := {V ∈𝒰 | Vx∈p}, the colours of p.

2. We say c ⊧ p, if for every formula φ(x)∈p we have φ(c). Note the difference between Δ-tp(c/A) = p and c ⊧ p: c ⊧ p iff Δ-tp(c/A)⊃p.

3. We call a Δ–type p over A realizable, if there do not exist (V_{1}, …, V_{r}) ∈ 𝒰_{c}∩(𝒰 (p))^{r} and elements a_{1}, …, a_{m}∈Par(p) such that a_{k}Ra_{l} (for 1^{≤} k < l^{≤} m) and a_{k} ∈V_{j} (for 1^{≤} k^{≤} m, 1^{≤} j ^{≤} r). The intended meaning is: p is realizable if one can realize it in a 𝒰_{c}-K_{m+1}–free graph.

Here are facts about realizability:

(1) If p⊂q and q is realizable, then so is p.

(2) If C ⊃A (C a 𝒰 –graph) is 𝒰_{c}-K_{m+1}–free, then for every c∈C Δ-tp(c/A) is realizable. In particular for every a∈A Δ-tp(a/A) is realizable.

(3) If p is a Δ–type over A and Par(p)⊂D_{i} for some i with 1^{≤} i^{≤} n then we can define p^{p_{i}} := {V^{χ_{i}}x | V x∈p} ∪ {xRa^{p_{i}} | xRa∈p} and we have:

p is realizable ⟺ p^{p_{i}} is realizable

All these facts follow directly from the definition of realizability. For (3) one has to use in addition, that 𝒰_{c} is χ_{i}–invariant.

Now we do the type–realizing step:

Claim:

a) There exists a 𝒰_{c}-K_{m+1}–free 𝒰 –graph C ⊃A and for every t (0^{≤} t^{≤} ^{#}A) a constant c_{t} such that for every Δ–type p over A:

#\{c∈C | c ⊧ p, 𝒰 (c) = 𝒰 (p)\} = \{ \begin{matrix}c_{#Par(p)} & if p is realizable \\ 0 & otherwise \end{matrix}

b) There exist bijections h_{1}, …, h_{n}∈Sym(C), h_{i} ⊃p_{i} such that for every V ∈𝒰 , for every b∈C, for every i (1^{≤} i^{≤} n): b∈V ⟺ b^{h_{i}} ∈V^{χ_{i}} and for every a∈D_{i}, b∈C : aRb ⟺ a^{p_{i}}Rb^{h_{i}}.

Proof of a): Let T = ^{#}A. We construct graphs A = C_{T} ⊂C_{T −1} ⊂…⊂C_{0} = C and constants c_{T} , … c_{0} such that for every t (T ^{≥} t^{≥} 0) and for every Δ–type p over A with #Par(p)^{≥} t:

#{c∈C_{t} | c ⊧ p, 𝒰 (c) = 𝒰 (p)} = c_{#Par(p)} if p is realizable

and such that C_{t} is 𝒰_{c}-K_{m+1}–free. We let c_{T} = 0.

If c_{r}, C_{r} are already constructed (for T ^{≥} r ^{≥} t) and t ^{≥} 1 then we will construct C_{t−1} by adding points which have exactly t − 1 neighbours, all of them in A: For p a realizable Δ–type over A with ^{#}Par(p) = t−1 we define c_{p} = ^{#}{c∈C_{t} | c ⊧ p, 𝒰 (c) = 𝒰 (p)} and we define c_{t−1} to be the maximum of all these c_{p}. Now to get C_{t−1} we add for every realizable p (with^{#}Par(p) = t−1) c_{t−1} −c_{p} many points having exactly type p (by this we mean points c such that Δ-tp(c/A) = p; note that all the neighbours of c are in A). Now C_{t−1} is a 𝒰 – graph and 𝒰_{c}-K_{m+1}–free and for every Δ–type p over A (with t − 1^{≤} ^{#}Par(p)): #{c ∈ C_{t−1} | c ⊧ p, 𝒰 (c) = 𝒰 (p)} = c_{#Par(p)} if p is realizable. This is true, because if Par(p)^{≥} t we did not change the set in question (by going from C_{t} to C_{t−1}) and if ^{#}Par(p) = t − 1 then ^{#}{c∈C_{t−1} | c ⊧ p, 𝒰 (c) = 𝒰 (p)} = ^{#}{c∈ C_{t} | c ⊧ p, 𝒰 (c) = 𝒰 (p)} + (c_{t−1} − c_{p}) = c_{p} + c_{t−1} − c_{p} = c_{t−1}.

The proof of b) is similar as the proof of b) in Lemma 1. Here again it is crucial to check that for every Δ–type p over D_{i}:

#{c∈C | Δ-tp(c/D_{i}) = p} = ^{#}{c∈C | Δ-tp(c/D′_{i}) = p^{p_{i}}}

This is done by downwards induction on the size of Par(p). We do the induction step in the case p is realizable. Otherwise both sets are empty; here we are using fact (3): p is realizable ⟺ p^{p_{i}} is realizable.

#{c∈C | Δ-tp(c/D_{i}) = p}
= ^{#}{c∈C | Δ-tp(c/D_{i})⊃p, 𝒰 (c) = 𝒰 (p)} − ∑_{qϵExt(p)}^{#}{c∈C | Δ-tp(c/D_{i}) = q}
= c_{#Par(p)} − ∑_{qϵExt(p)}^{#}{c∈C | Δ-tp(c/D′_{i}) = q^{p_{i}}}
= ^{#}{c∈C | Δ-tp(c/D′_{i})⊃p^{p_{i}}, 𝒰 (c)=𝒰 (p^{p_{i}})} − ∑_{q′ϵExt(p^{p_{i}})}^{#}{c∈C | Δ-tp(c/D′_{i}) = q′}
= ^{#}{c∈C | Δ-tp(c/D′_{i}) = p^{p_{i}}}

Here Ext(p) := {q | q Δ–type over D_{i}, p⊊q, 𝒰 (q) = 𝒰 (p)} and similar Ext(p^{p_{i}}).

Now we introduce a new set of colours: 𝒰^{r+1} = {U_{d}^{r+1} | d∈C}, where U_{d}^{r+1} is a new unary predicate for every d ∈ C. We define χ_{i}^{r+1} ∈ Sym(𝒰^{r+1}) (for 1^{≤} i^{≤} n) by (U_{d}^{r+1})^{χ_{i}^{r+1}} := U_{d^{h_{i}}}^{r+1}. We let 𝒰′ := 𝒰 ∪𝒰^{r+1} and χ′_{i} := χ_{i} ∪ χ_{i}^{r+1}∈ Sym(𝒰′ ∪ {R}). We define 𝒰 ′_{c} ⊂𝒰^{1} × … × 𝒰^{r+1} by (V_{1}, …, V_{r}, U_{d}^{r+1})∈𝒰 ′_{c} ⟺ (V_{1}, …, V_{r})∈𝒰_{c} and d∈V_{j} (1^{≤} j ^{≤} r) (in C). 𝒰 ′_{c} is χ′_{i}–invariant, because 𝒰_{c} is χ_{i}–invariant, because of the definition of χ_{i}^{r+1} and because of the property of h_{i} in claim b) (b∈V ⟺ b^{h_{i}} ∈V^{χ_{i}}).

The colours in 𝒰^{r+1} are in a natural way interpreted in A: for a ∈ A and d∈C we define a∈U_{d}^{r+1} ⟺ dRa (in C). Now A is a 𝒰′–graph.

A is 𝒰 ′_{c}-K_{m}–free. Otherwise there would exist a_{1}, … a_{m}∈A and (V_{1}, …, V_{r}, U_{d}^{r+1}) ∈ 𝒰 ′_{c} such that a_{k}Ra_{l} (for 1 ^{≤} k < l ^{≤} m) and a_{k} ∈ V_{j} (for 1^{≤} k ^{≤} m, 1^{≤} j ^{≤} r) and a_{k} ∈ U_{d}^{r+1}. But then (V_{1}, …, V_{r}) ∈𝒰_{c}, d ∈ V_{j}, a_{k}Rd. This means a_{1}, …, a_{m}, d contradicts the 𝒰_{c}-K_{m+1}–freeness of C.

For 1^{≤} i^{≤} n p_{i} is a χ′_{i}–permorphism. By the lemma for m we find a finite 𝒰′–graph B, B ⊃ A, B 𝒰 ′_{c}-K_{m}–free and f_{1}, …, f_{n} ∈ Sym(B), f_{i} ⊃ p_{i}, f_{i} a χ′_{i}–permorphism having the indicated properties.

Now we consider B just as a 𝒰 –graph. The only thing we still have to check, is that B is 𝒰_{c}-K_{m+1}–free.

Claim:

(1) If a∈A and b∈B then aRb ⇒ b∈U_{a}^{r+1}.

(2) B is 𝒰_{c}-K_{m+1}–free.

Proof: (1) Because of the extra property 2 of the lemma and as aRb we can choose f ∈ < f_{1}, …, f_{n} > such that a_{0} := a^{f} ∈ A and b_{0} := b^{f} ∈ A. As a_{0}Rb_{0} we have b_{0} ∈ U_{a_{0}}^{r+1}. Let f = f_{i_{1}}^{ϵ_{1}} … f_{i_{t}}^{ϵ_{t}} and a^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = a_{0}; here we are using the extra property 3. Now f is a χ_{i_{1}}^{ϵ_{1}} … χ_{i_{t}}^{ϵ_{t}}–permorphism and we also know

a^{h_{i_{1}}^{ϵ_{1}} ...h_{i_{t}}^{ϵ_{t}}} = a_{0} so (U_{a}^{r+1})^{χ_{i_{1}}^{ϵ_{1}} ...χ_{i_{t}}^{ϵ_{t}}} = U_{a_{0}}^{r+1}. Thus because b^{f} = b_{0} ∈ U_{a_{0}}^{r+1} it follows: b∈U_{a}^{r+1}.

(2) Suppose there exist (V_{1}, …, V_{r}) ∈ 𝒰_{c} and elements a_{0}, …, a_{m} ∈ B such that a_{k}Ra_{l} and a_{k} ∈ V_{j}. W.l.o.g we suppose a := a_{0} ∈ A: Otherwise choose f ∈ < f_{1}, …, f_{n} >, such that a_{0}^{f} ∈ A and choose χ′ ∈ Sym(S′) such that f is a χ′–permorphism and let χ = χ′ |_{S}; now still (V_{1}^{χ}, …, V_{r}^{χ})∈𝒰_{c} and a_{k}^{f}Ra_{l}^{f} and a_{k}^{f} ∈ V_{j}^{χ}. We have (V_{1}, …, V_{r}, U_{a}^{r+1}) ∈ 𝒰 ′_{c} and by (1): a_{k} ∈ U_{a}^{r+1} (1^{≤} k ^{≤} m). Thus we get a contradiction to the 𝒰 ′_{c}-K_{m}–freeness of B.

The graphs we constructed to prove Theorem 2 are all of the form A × Γ/≡ where Γ is a big enough finite group generated by n distinguished elements γ_{1}, …, γ_{n}. In fact to proof (EP) for the K_{m}–free graphs it is equivalent –given A, p_{1}, …, p_{n} – to find a finite extending K_{m}–free graph B and automorphisms f_{1}, …, f_{n} extending the p_{i} and to find such a group Γ such that B = A × Γ/≡ is K_{m}–free, a ↦ (a, 1)/≡ gives an embedding and for each i the action of γ_{i} extends p_{i}. To see this take an arbitrary solution B, f_{1}, …, f_{n}, then define Γ = < f_{1}, …, f_{n} > ⊂ Aut(B). The mapping ρ : A × Γ/≡ → B defined by (a, f)/≡ ↦ a^{f} is well defined and an embedding i : K_{m} → A × Γ/≡ would lead to an embedding iρ : K_{m} → B. Thus also A × Γ/≡ is K_{m}–free and solves the extension problem. Note that ρ is a weak homomorphism in the sense below.

4. A more general case

In this section we are handling a more general case. The theorem we are going to prove will imply the theorem 2 which we just proved. But we hope that it will be much easier to understand this general case, after having understood the case of the graphs. We will start with some definitions we will need for the statement of the theorem. We will restrict attention here to irreflexive structures, even if this is not essential, as the final chapter will show.

Definition: Let S be a relational language.

1. A structure A is called irreflexive, if for every k ∈ ω, every k–ary R in S and every a_{1}, …, a_{k} in A, if Ra_{1} … a_{k} holds, then a_{1}, …, a_{k} are pairwise distinct.

2. By S_{k} (k∈ω) we denote the set of k–ary relation symbols in S.

3. Let L be an S–structure. L is called a link structure, if there exists a_{1}, …, a_{k} ∈ L and R ∈ S such that {a_{1}, …, a_{k}} = L and Ra_{1} … a_{k} holds in L or if L has just one element.

4. Let ℒ be a set of link structures, A be an S–structure. A has link type ℒ if for every substructure L ⊂ A: if L is a link structure, then there exist L′∈ℒ such that L ≅ L′.

5. Let T, A be S–structures, let ρ :T → A be a function. ρ is called a weak homomorphism (notation: ρ : T →w A) if for every k ∈ ω, R ∈ S_{k} and s_{1}, …, s_{k} ∈T: if Rs_{1} … s_{k} (in T) then Rs_{1}^{ρ} … s_{k}^{ρ} (in A).

6. Let ℱ be a set of finite S–structures. Let A be an S–structure. We say A is ℱ–free or A weakly avoids ℱ, if there does not exist T ∈ℱ and ρ :T →w A.

7. Suppose ℒ is a set of link structures and ℱ be a set of finite S–structures, then 𝒦 ℒℱ will be the class of all finite S–structures A, which are ℱ–free and of link type ℒ and 𝒦 ℱ will denote all irreflexive S–structures, which are ℱ–free.

8. T is a packed structure, if for every t_{1}, t_{2} ∈T there exists a link–structure L⊂T with t_{1}, t_{2}∈L.

Examples: 1. If ℒ contains for every irreflexive link structure an isomorphic copy, then for every S–structure B: B is irreflexive iff B has link type ℒ .

2. Let R be binary, S = {R}. If we let ℒ_{1} = {K_{1}, K_{2}}, where K_{1} is just one point and K_{2} is the graph with two points and an edge between them, then B is a graph iff B has link type ℒ_{1}.

3. Now we let T_{2} be the structure consisting of two points a, b and xRy holds in T_{2} iff x = a and y = b. B is a directed graph iff B is of link type ℒ_{2} = {K_{1}, T_{2}}.

Proposition 4 If T is packed and A is irreflexive and ρ : T →w A, then ρ is injective. If ℱ is a family of packed structures then 𝒦 ℱ (and also 𝒦 ℒℱ ) has the free amalgamation property (fAP). By this we mean: If A, B, C ∈𝒦 ℱ ∪ {∅}, A⊂B, A⊂C then B ∗_{A} C ∈𝒦 ℱ ∪ {∅}.

Here B ∗_{A} C is the free amalgam of B and C over A. To define it, first suppose that C ∩ B = A (by changing C to an isomorphic copy). Now the underlying domain of B ∗_{A} C is just B ∪ C and a relation Rd̄ holds in B ∗_{A} C iff it holds in B (and d̄∈B) or in C. Note that we allow the common part to be empty. The proof of the proposition is easy.

Theorem 5 Let S be a finite relational language. Let ℱ be a set of finite irreflexive packed S–structures. Let ℒ be a set of irreflexive link structures. Then 𝒦 ℒℱ has (EP), the extension property for partial isomorphisms.

Definition: Let χ be an arity-preserving permutation of S. For any S–structure T we define T^{χ} to be the S–structure with the same underlying domain as T, but for R ∈ S (R k–ary) we define: Ra_{1} … a_{k} holds in T^{χ} iff R^{χ^{−1}}a_{1} … a_{k} holds in T. We say that a family ℱ of S–structures is invariant under χ, if T ∈ℱ ⟺ T^{χ}∈ℱ.

Now we formulate the permorphism version of theorem 5

Lemma 6 Let S be a finite relational language and let χ_{1}, …, χ_{n} be arity preserving permutations of S. let ℱ be a finite family of finite irreflexive packed S–structures invariant under χ_{i} (for 1 ^{≤} i ^{≤} n). Let A ∈ 𝒦 ℱ be finite. Let p_{1}, …, p_{n} be partial mappings on A, p_{i} a χ_{i}–permorphism.

There exist a finite S–structure B∈𝒦 ℱ, A⊂B and f_{1}, …, f_{n} bijections on B, f_{i} ⊃ p_{i}, such that f_{i} is a χ_{i}–permorphism. B has the additional properties mentioned in Lemma 1.

From the lemma follows the theorem: Let A∈𝒦 ℒℱ and p_{1}, …, p_{n} be given.

1. Suppose first that ℱ is finite. Let each χ_{i} be the identity and apply the lemma in this situation. We only have to check that the resulting structure B is automatically of link type ℒ . This follows from the additional property 1 and 2.

In fact suppose L ⊂ B is a link structure. There exists f ∈ < f_{1}, …, f_{n} > such that L^{f} ⊂ A. Because A has link type ℒ there exists L′ ∈ ℒ such that L ≅ L^{f} ≅ L′.

2. Suppose now that for every T ∈ℱ and every substructure T′ ⊂T T′ is packed. Let m be the size of A. Let ℱ_{m+1} be a finite set containing for every packed S–structure of size m + 1 exactly one isomorphic copy. Suppose further that ℱ contains only finitely many structures of size less than m + 1 (by throwing away isomorphic copies). Let ℱ′ := {T ∈ℱ | ^{#}T ^{≤} m} ∪ ℱ_{m+1}. Then A∈𝒦 ℒℱ ′ and we can apply the first case to get B∈𝒦 ℒℱ ′ solving the extension problem. But B is automatically ℱ–free. It does not contain any packed substructure of size m + 1 so it does not (weakly) contain any structure T ∈ℱ with ^{#}T > m.

3. We do the general case by a trick. Let R be a new binary predicate and define S^{∗} := S ∪ {R}. For an S–structure C we define C^{∗} to be the expansion of C where for b, c∈C: bRc ⟺ b ≠ c. Let ℱ^{∗} = {T^{∗} | T ∈ℱ} and ℒ^{∗} := {L⊂A^{∗} | L a link structure}. By case 2 we find B ∈𝒦 ℒ^{∗}ℱ^{∗}, A^{∗} ⊂ B, and we only have to show that B S̀ ∈𝒦 ℒℱ .

If L⊂B such that L S̀ is a link structure then L ≅ L′∈ℒ^{∗}, so L ≅ L′ ⊂A^{∗}. Thus L S̀ ≅ L′ S̀ ⊂A. But A has link type ℒ so L S̀ ≅ L′ S̀ ≅ L′′∈ℒ .

Suppose now there exists T ∈ℱ and ρ : T →w B S̀ (note id : B S̀ →w B). As B is irreflexive ρ is injective. We want to prove that ρ is a map T^{∗} →w B, to get a contradiction. For this suppose t_{1}, t_{2}∈T^{∗} and Rt_{1}t_{2}. We have to show Rt_{1}^{ρ}t_{2}^{ρ}. Because T is packed there is P ∈S and t̄∈T, t_{1}, t_{2} appear in t̄, such that P t̄ holds. Thus P t̄^{ρ} holds in B. Consider the substructure {t̄^{ρ}} of B. It is a link structure. So it is isomorphic to a substructure of A^{∗}. Thus for any two distinct elements t, t′ of {t̄} Rtt′ holds. In particular, as ρ is injective, Rt_{1}^{ρ}t_{2}^{ρ} holds.

Proof of the lemma:

The proof will be similar to the proof for the graphs in section 3. We only point out the main differences. It goes by induction on the maximal size of structures in ℱ. The case that this size is one is as easy as the corresponding case for the graphs. So let us suppose that the maximal size of the structures in ℱ is m + 1 > 1. We need to change the notion of Δ–type slightly:

Definition:

1. A Δ–type over A is a collection of formulae of the form Ra_{1} … a_{k′−1}xa_{k′} … a_{k−1}, where k ^{≥} 1 and R ∈ S_{k} and a_{1}, … a_{k−1} are pairwise distinct elements of A. The notions about Δ–types in section 2 like Δ-tp(c/A) and p D̀_{i} and p^{p_{i}} extend naturally to this notion of Δ– type. If p is a Δ–type over A we define Par(p) := {a ∈ A | there exists a formula φ∈p in which a appears}.

2. Let p be a Δ–type over A and let A_{0} :=Par(p). Suppose A_{0} ⊂ B. We denote by B + p the structure which we get by adding just one point c_{p} to B having exactly type p. So B + p = B ∪ {c_{p}}, c_{p}∉B, Δ-tp(c_{p}/B) = p. Note that B + p is irreflexive.

3. Let p be a Δ–type, and A_{0} =Par(p). p is called realizable iff A_{0} + p∈𝒦 ℱ.

The facts about realizability in this context:

(0) If p is realizable and A_{0} ⊂B and B∈𝒦 ℱ then B + p∈𝒦 ℱ.

(1) If p⊂q and q is realizable, then so is p.

(2) If A ⊂ C ∈𝒦 ℱ, then for every c∈C Δ-tp(c/A) is realizable. In particular for every a∈A Δ-tp(a/A) is realizable.

(3) If p is a type over A and Par(p)⊂D_{i} (for some i with 1^{≤} i^{≤} n) then

p is realizable ⟺ p^{p_{i}} is realizable

It is here (in Fact (0), which says that realizable types are indeed realizable) where we use that the structures in ℱ are packed.

Proof:

(0) It is A_{0} + p∈𝒦 ℱ and B∈𝒦 ℱ so by (fAP) B + p ≅ (A_{0} + p) ∗_{A_{0}} B∈𝒦 ℱ.

(1) Note that if p⊂q then Par(p) + p →w Par(q) + q.

(2) Use that for p = Δ-tp(c/A): A + p →w C.

(3) Observe that (Par(p) + p)^{χ_{i}} ≅Par(p^{p_{i}}) + p^{p_{i}} and use that ℱ is χ_{i}–invariant.

Now the crucial claim in this proof reads as follows:

Claim: a) There exists an ℱ–free S–structure C, A ⊂ C, and for every t a constant c_{t} ∈ω such that for every E ⊂A and every Δ–type p over A such that Par(p) = E:

#\{c∈C | Δ-tp(c/E) = p\} = \{ \begin{matrix}c_{#E} & if p is realizable \\ 0 & otherwise \end{matrix}

b) There exist bijections h_{1}, …, h_{n} ∈ Sym(C), h_{i} ⊃ p_{i} such that for every i (1^{≤} i^{≤} n) and every b∈C: Δ-tp(b^{h_{i}}/D′_{i}) = (Δ-tp(b/D_{i}))^{p_{i}}.

The proof of a) is as in the case of the graphs. It works because adding a new point of exactly type p (where Par(p) = E) does not change the number of points d with Δ-tp(d/E′) = p′ for any type p′ with Par(p′) = E′, provided #E′ ^{≥} ^{#}E and p′ ≠ p. So as in section 3 we can work our way downwards. Here we use also fact 0; the fact insures that the constructed structure is still ℱ–free.

Also the proof of b) goes exactly along the lines of section 3. If p is a Δ–type over D_{i} and Par(p) = E, then {c | Δ-tp(c/D_{i}) = p} = {c | Δ-tp(c/E) = p} − ⋃_{qϵExt(p)}{c | Δ-tp(c/D_{i}) = q}, where Ext(p) = {q Δ–type over D_{i} | q È = p, p ⊂ q, p ≠ q}. It follows that #{c | Δ-tp(c/D_{i}) = p} = ^{#}{c | Δ-tp(c/D′_{i}) = p^{p_{i}}}

With the help of this claim we now change the class of structures we want to avoid and then use induction.

Definition:

• Let R ∈ S_{k} (k > 1) and C be the S–structure of the claim. Suppose 1 ^{≤} k′ ^{≤} k and c ∈ C, then R_{c}^{k′} will be a (k − 1)–ary relation symbol, and the natural interpretation on A will be R_{c}^{k′}b_{1} … b_{k−1} holds iff Rb_{1} … b_{k′−1}cb_{k′} … b_{k−1} holds in C.

• Let S′ := S ∪ {R_{c}^{k′} | k∈ω, k > 1, R∈S_{k}, 1^{≤} k′ ^{≤} k, c∈C}. Define χ′_{i} on S′ by χ′_{i} S̀ = χ_{i} and (R_{c}^{k′})^{χ′_{i}} := (R^{χ_{i}})_{c^{h_{i}}}^{k′}. We can consider A in a natural way as an S′–structure.

• For T ∈ℱ, ^{#}T ^{≥} 2, t∈T and c∈C we expand the S–structure T − {t} to an S′–structure called T_{t}^{c} according to the clause:

T_{t}^{c} ⊧ R_{d}^{k′}t_{1} … t_{k−1} ⟺ d = c and T ⊧ Rt_{1} … t_{k′−1}tt_{k′} … t_{k−1}

• We let ℱ′ := {T ∈ ℱ | ^{#}T = 1} ∪ {T_{t}^{c} | T ∈ ℱ, ^{#}T ^{≥} 2, t ∈ T, c ∈ C, for every R ∈ S_{1}: T ⊧ Rt ⇒ C ⊧ Rc}; note that ℱ′ contains only packed structures.

Claim:

(1) p_{i} is a χ′_{i}–permorphism (1^{≤} i^{≤} n),

(2) ℱ′ is χ′_{i}–invariant (1^{≤} i^{≤} n).

(3) A is ℱ′–free.

Proof:

(1) follows directly from the properties of the h_{i} (see b) of previous claim).

(2) If T_{t}^{c} ∈ ℱ′ then also (T_{t}^{c})^{χ′_{i}} = (T^{χ_{i}})_{t}^{c^{h_{i}}} ∈ ℱ′. For this suppose R ∈ S_{1} and T^{χ_{i}} ⊧ Rt. Now T_{t}^{c} ∈ ℱ′ and T ⊧ R^{χ_{i}^{−1}}t ⇒ C ⊧ R^{χ_{i}^{−1}}c ⇒ R^{χ_{i}^{−1}}x ∈ Δ-tp(c/D_{i}) ⇒ Rx∈Δ-tp(c^{h_{i}}/D′_{i}) ⇒ C ⊧ Rc^{h_{i}}.

(3) Suppose T_{t}^{c} ∈ ℱ′ and i : T_{t}^{c} →w A. This leads to a weak homomorphism i′ : T →w C, where i′ T̀ − {t} = i and i′(t) = c. Here we are using that T is irreflexive. This contradicts C ∈𝒦 ℱ.

By induction we can apply the lemma in this situation and get an ℱ′–free S′–structure B, B ⊃A, f_{1}, …, f_{n} ∈Sym(B), such that f_{i} is a χ′_{i}–permorphism.

B satisfies the additional properties mentioned in Lemma 1 for the language S′, thus a fortiori for the language S.

So the only thing that still needs checking is that B is ℱ–free. Again we need that in a certain sense B looks locally like A:

Claim:

(1) If k > 1, R∈S_{k}, 1^{≤} k′ ^{≤} k, a∈A and b_{1}, …, b_{k−1}∈B then

Rb_{1} … b_{k′−1}ab_{k′} … b_{k−1} ⇒ R_{a}^{k′}b_{1} … b_{k−1}.

(2) B is ℱ–free.

Proof: (1) By the extra property 2 there exists f ∈ < f_{1}, …, f_{n} > such that a^{f} ∈ A and b_{i}^{f} ∈ A for all i. Using the extra property 3 let f = f_{i_{1}}^{ϵ_{1}} … f_{i_{t}}^{ϵ_{t}} and

a^{p_{i_{1}}^{ϵ_{1}} ...p_{i_{t}}^{ϵ_{t}}} = a^{f} so also a^{h_{i_{1}}^{ϵ_{1}} ...h_{i_{t}}^{ϵ_{t}}} = a^{f}. f is a χ′ = (χ′_{i_{1}})^{ϵ_{1}} … (χ′_{i_{t}})^{ϵ_{t}}–permorphism and (R_{a}^{k′})^{χ′} = (R^{χ})_{a^{f}}^{k′}, where χ = χ′ S̀. Thus Rb_{1} … b_{k′−1}ab_{k′} … b_{k−1} ⇒ R^{χ}b_{1}^{f} … b_{k′−1}^{f}a^{f}b_{k′}^{f} … b_{k−1}^{f} ⇒ (R^{χ})_{a^{f}}^{k′} b_{1}^{f} … b_{k−1}^{f} ⇒ (R_{a}^{k′})^{χ′}b_{1}^{f} … b_{k−1}^{f} ⇒ R_{a}^{k′}b_{1} … b_{k−1}.

(2) We suppose there exist T ∈ℱ and ρ : T →w B. Because of the ℱ′–freeness of B we have ^{#}T ^{≥} 2. Pick t∈T. We can suppose that t^{ρ}∈A: Otherwise choose f ∈<f_{1}, …, f_{n} > such that (t^{ρ})^{f} ∈A and choose χ∈<χ_{1}, …, χ_{n} > such that f is a χ–permorphism. Now ρ · f induces a weak homomorphism T^{χ} →w B with t^{ρf} ∈A and we still have T^{χ}∈ℱ.

Let t^{ρ} = a∈A. We have T_{t}^{a}∈ℱ′. Consider ρ′ = ρ T̀ − {t}. We want to show that ρ′ : T_{t}^{a} →w B to get a contradiction to the ℱ′–freeness of B. ρ′ clearly preserves S–relations so let R ∈ S_{k}, k > 1, 1^{≤} k′ ^{≤} k, c ∈ C and t_{1}, …, t_{k−1} ∈ T − {t} such that T_{t}^{a} ⊧ R_{c}^{k′}t_{1} … t_{k−1}. So a = c and Rt_{1} … t_{k′−1}tt_{k′} … t_{k−1}. Because ρ is a weak homomorphism Rt_{1}^{ρ′} … t_{k′−1}^{ρ′}at_{k′}^{ρ′} … t_{k−1}^{ρ′}. By (1) and a = c: (R_{c}^{k′})t_{1}^{ρ′} … t_{k−1}^{ρ′}.

One open question is, if (EP) also holds for classes of structures which avoid a given family of packed structures in a stronger sense:

Definition: Let A be an S–structure and ℱ a family of packed S–structures. We say A avoids ℱ (as substructures) iff there does not exists T ∈ ℱ and an embedding ρ : T ↪ A.

If ℱ is any family of finite packed structures, does (EP) hold for the class of structures avoiding ℱ?

The only point in the proof where we used weak homomorphism as opposed to embeddings, was the very last claim we proved. If we would be able to find extending structures B which in a stronger sense would locally look like A (i.e. also the reverse of the implication in part (1) of the claim holds), then we would be able to replace weak homomorphisms by embeddings.

Let us give a bound for the structure B satisfying the conclusion in Lemma 6 (or Theorem 5). As in section 2 it is an iterated exponential function. For this we assume ℱ to be finite and we let c := ^{#}A and t :=sup{^{#}T | T ∈ ℱ} ^{≥} 2 (if ℱ is infinite we would need t := (c + 1)). We suppose the maximal arity of symbols in S is r ^{≥} 2 and that S contains l_{j} many j–ary symbols. We let p_{2}(x) = l_{1}x + 2l_{2}x^{2} + … rl_{r}x^{r}. Claim: We can find B with^{#}B^{≤} itexp(2r+t−3, 2p_{2}(c)) satisfying the conclusion in Lemma 6. We do not give the straight forward but tedious proof here. We only indicate the reason for the different form of the polynomial compared to the formula in section 2. The notion of Δ–types is different compared to section 2 and the number of Δ–types over A equals 2^{l_{1}+2l_{2}c+...+rl_{r}c^{r−1}}. In the construction of the structure C we have to iterate a certain type realizing step c times. We can bound C by c · (2^{l_{1}+...l_{r}c^{r−1}})^{c} = c2^{p_{2}(c)}. The proof of the claim is by induction on t. Note that for t = 2 the structure B is automatically ℱ–free as long as the extra conditions are satisfied. This is because every packed structure of size at most 2 is a link structure.

5. The small index property

In [HHLS] Hodges, Hodkinson, Lascar, Shelah showed how the (EP) for the class of graphs can be used to prove the small index property for the random graph. This proof readily extends to our cases. We do not want to repeat the complete proof here, but for the convenience of the reader we want to indicate how a property like (EP) is useful to understand the automorphism group of the “generic countable structure” of this class. Most of the material up to Theorem 11 is (partly implicitly) contained in [HHLS]. Here we are only looking at the special case of homogeneous ω-categorical structures. Throughout this section S is a finite language.

The idea to look at a generic automorphism can be found in [L] and [T]. The underlying idea of this presentation is based on the introduction in [Hr].

Definition: Let 𝒦 ℒℱ be a class like in theorem 5. 𝒦 ℒℱ has the amalgamation property (AP). (The (AP) here includes the case –sometimes known as joint embedding property– where the common part is empty). There exists uniquely up to isomorphism a countable structure M called the generic structure for 𝒦 ℒℱ having the following properties:

• every finitely generated substructure of M belongs to 𝒦 ℒℱ .

• For A⊂B finite structures in 𝒦 ℒℱ and i : A ↪ M there exists j : B ↪ M j extending i. Here again we allow A = ∅.

Such a structure exists for a class 𝒦 , if 𝒦 is a class of finite S–structures having the (AP), and which is closed under isomorphisms and substructures. Furthermore M is always homogeneous. See [C] section 2.6 or [Fr], also for the definition of the amalgamation property.

In this paper we always want to assume that the classes we consider are closed under isomorphisms and substructures and we exclude the uninteresting case that there are only finitely many structures up to isomorphism in 𝒦 .

If M is a countable structure we equip G =Aut(M) with the topology of pointwise convergence. G is a polish group, as is G^{n} equipped with the product topology. So we can talk about comeager sets. See the introduction in [KM] for an introduction to these topological groups.

(g_{1}, …, g_{n})∈G^{n} is called locally finite, if for every a∈M the orbit of a under < g_{1}, …, g_{n} > is finite. With respect to the automorphism group (EP) says exactly that a generic n–tuple of automorphisms is locally finite (this proposition was probably known to Hrushovski, see the introduction of [Hr]):

Proposition 7 Let 𝒦 be a class of finite S–structures having (AP). Let M be the generic structure for 𝒦 . Then 𝒦 has (EP) iff {(g_{1}, …, g_{n}) ∈ Aut(M)^{n} | (g_{1}, …, g_{n}) locally finite} is comeager in Aut(M)^{n}.

Proof: “⇐”: Suppose that {(g_{1}, …, g_{n})∈Aut(M)^{n} | (g_{1}, …, g_{n}) locally finite} is comeager, thus dense in G^{n}. Take A∈𝒦 and p_{1}, …, p_{n} partial isomorphisms on A. Embedding A into M we can suppose A⊂M. The set {(g_{1}, …, g_{n}) | p_{i} ⊂ g_{i} (1^{≤} i^{≤} n)} is by definition of the topology an open set of G^{n}. It is not empty because of the homogeneity of M. So we find (g_{1}, …, g_{n}), p_{i} ⊂ g_{i}, such that (g_{1}, …, g_{n}) is locally finite. Take B to be the union of all the orbits of elements of A under < g_{1}, …, g_{n} >. Then B solves the extension problem; (EP) holds for 𝒦 . “⇒”: We prove that for every a ∈ M the set {(g_{1}, …, g_{n}) | a^{<g_{1},...,g_{n}>} finite} is open and dense. So take a ∈ M and a non empty open subset O of G^{n}. By definition of the topology we find p_{1}, …, p_{n} finite partial isomorphisms on M such that O ⊃ {(g_{1}, …, g_{n}) | p_{i} ⊂ g_{i} (1 ^{≤} i ^{≤} n)} ≠ ∅. Let A be a finite substructure of M containing a and the ranges and domains of the p_{i}. By applying (EP) we find a finite structure B ∈𝒦 , A⊂B and f_{1}, …, f_{n} ∈Aut(B), p_{i} ⊂f_{i}. By the defining property of M we can suppose B ⊂M. By homogeneity of M we can extend the f_{i} to automorphisms g_{i} of M. This shows the denseness. For the openness, observe that given (g_{1}, …, g_{n}) such that B = a^{<g_{1},...,g_{n}>} is finite, all n–tuples of automorphism which look on B like (g_{1}, …, g_{n}) are also in {(g_{1}, …, g_{n}) | a^{<g_{1},...,g_{n}>} finite}.

In the sequel we want to describe more precisely, what in our cases a generic tuple of automorphisms looks like.

Definition: 1. Let 𝒦 be a class of S–structures. By S^{+n} denote S∪{h_{1}, …, h_{n}}, where h_{1}, …, h_{n} are new unary function symbols. By 𝒦 ^{+n} we denote the following class of S^{+n}–structures:

{(A, f_{1}, …, f_{n}) | A∈𝒦 , f_{i}∈Aut(A), A finite}

2. If 𝒦 ^{+n} has the (AP) then we define M^{+n} to be the generic countable model of 𝒦 ^{+n}. M^{+n} = (M, g_{1}, …, g_{n}), where g_{i} is the interpretation of h_{i} in M^{+n}. By definition of the generic model (g_{1}, …, g_{n}) is locally finite.

Proposition 8 If 𝒦 has the free amalgamation property then so has 𝒦 ^{+n}.

Proposition 9 a) Suppose 𝒦 has the free amalgamation property. Denote by M the generic countable structure of this class and by M^{+n} the generic structure of 𝒦 ^{+n}. Then M^{+n} S̀ ≅ M.

b) Suppose 𝒦 has (AP) and (EP) and 𝒦 ^{+n} has (AP). Then M^{+n} S̀ ≅ M.

a) This proposition is not as obvious as it might look at first glance. We have to show, that for A⊂M^{+n} S̀ and A⊂B∈𝒦 there exists an embedding i : B ↪ M, i À = id À. We can suppose A to be closed under < g_{1}, …, g_{n} >. Let g′_{i} := g_{i} À for every i. We take C := B×<g′_{1}, …, g′_{n} > /≡, where (b, g)≡ (b^{∗}, g^{∗}) iff b, b^{∗} ∈ A and b^{g} = (b^{∗})^{g^{∗}} and embed B into C via b ↦ (b, 1)/≡. For R ∈ S r-ary and c_{1}, …, c_{r} ∈ C we define Rc_{1} … c_{r} iff there exists g ∈ < g′_{1}, …, g′_{n} > and a_{1}, …, a_{r} ∈A such that Ra_{1} … a_{r} and c_{1} = (a_{1}, g) and … and c_{r} = (a_{r}, g). We define f_{i} on C by ((b, g)/≡)^{f_{i}} := (b, gg_{i})/≡. Now (C, f_{1}, …, f_{n}) is in 𝒦 ^{+n}. For this note that C is nothing else but a free amalgam of (twisted) copies of B over A. Thus there is j′ : (C, f_{1}, …, f_{n}) ↪ M^{+n} with j′ À = id À and j = j′ B̀ : B ↪ M^{+n} S̀ with j À = id À. Note the similarity of this relatively easy construction of C and constructions of the form A×Γ/≡ in earlier chapters.

b) has the same proof. Just take for (C, f_{1}, …, f_{n}) the structure you get by applying (EP) to B and g_{1} À, …, g_{n} À.

Side remark: It is a nice and not so easy exercise to prove that this proposition also holds for the class 𝒦 of all finite tournaments. (Use that the automorphism group of a tournament is odd, and that a directed graph, with a group of odd order acting on it, can be completed to a tournament such that the group still acts as automorphisms on this tournament.)

Definition: Let 𝒦 be a class of finite S–structures such that 𝒦 and 𝒦 ^{+n} have (AP). Let M be the generic countable model of 𝒦 . Let (g_{1}, …, g_{n}) be a tuple of automorphisms. (g_{1}, …, g_{n}) is called Fraïssé–generic if (M, g_{1}, …, g_{n}) is isomorphic to the generic model of 𝒦 ^{+n}.

Note that {(g_{1}, …, g_{n}) | (g_{1}, …, g_{n}) is Fraïssé–generic} is an orbit in (AutM)^{n} (under the action of AutM on (AutM)^{n} by conjugation). The next proposition shows that under certain circumstances it is a comeager orbit (and therefore the only comeager orbit).

Proposition 10 ([HHLS]) Let 𝒦 be a class of finite S–structures having (AP) and (EP). Suppose further that 𝒦 ^{+n} has (AP). Then {(g_{1}, …, g_{n}) | (g_{1}, …, g_{n}) is Fraïssé–generic} is comeager in Aut(M)^{n}.

Thus in our cases a generic (in the sense of Baire Category) tuple of automorphisms is Fraïssé–generic.

The proof of the proposition is fairly routine. Transform “(g_{1}, …, g_{n}) is Fraïssé–generic” into countably many open dense conditions corresponding to the countably many conditions by which the generic structure M^{+n} is defined.

You find this proposition in different notation and context in [HHLS] (Theorem 2.9). In their terminology the proposition implies that M has “ample generic automorphisms”.

Theorem 11 ([HHLS]) Let 𝒦 be a class of finite S–structures having (AP) and (EP). Suppose further that 𝒦 ^{+n} has (AP) for all n with 1^{≤} n < ω. Let M be the generic structure of 𝒦 . Then M has the small index property.

Here we say a countable structure M has the small index property (SIP), if for every subgroup H of G = Aut(M), if [G : H] < 2^{ω} then H is open. See [HHLS] and [KM] for more information about the small index property and section 4 and 5 of [HHLS] for a proof of the statement “if M has ample generic automorphisms then it has the (SIP)”.

Theorem 11 is only implicitly contained in [HHLS], but one can find it more explicitly in a preliminary version of that paper.

Corollary 12 (1) Let ℱ be any set of finite packed irreflexive S–structures, and ℒ be a set of irreflexive link–structures. Then Mℒℱ the generic model of 𝒦 ℒℱ has the (SIP).

(2) Let m > 1. The generic countable K_{m}–free graph has the (SIP).

Proof: By Theorem 5 the classes in question have (EP) and by Proposition 4 they have the free amalgamation property, and by Proposition 8 also the corresponding classes 𝒦 ^{+n} have (AP). Thus Theorem 11 can be applied.

Here we are especially interested in certain classes of digraphs, which have been introduced by Henson, to prove that there are 2^{ω} many different ω– categorical theories of directed graphs ([Hen]). Also Peretyat’kin defined 2^{ω} many different ω–categorical theories in the language consisting of just one binary predicate ([P]), but we are not able to prove the (SIP) for these structures.

Let S = {R}. We will look at directed graphs so instead of writing aRb we will also write a → b; directed graphs are S–structures having link type ℒ_{2} = {·, · → ·}. A tournament is a packed directed graph, i.e. an irreflexive S–structure A, such that for a, b∈A (a ≠ b) exactly one of aRb and bRa holds. The directed graphs Henson introduced are the generic graphs M_{ℒ_{2}ℱ} of classes 𝒦 _{ℒ_{2}ℱ}, where ℱ is an infinite family of tournaments. Henson proved that there are 2^{ω} many non–isomorphic graphs of the form M_{ℒ_{2}ℱ}.

Corollary 13

(1) Let ℱ be a possibly infinite family of tournaments. Then 𝒦 _{ℒ_{2}ℱ} has (EP).

(2) The generic structure M_{ℒ_{2}ℱ} of the above class has the (SIP).

(3) There are 2^{ω} many non–isomorphic ω–categorical directed graphs having the (SIP).

(4) There are 2^{ω} many non–isomorphic automorphism groups of ω–categorical directed graphs having the (SIP).

Proof:

(1) and (2) are direct consequences of Theorem 5 and Corollary 12 respectively.

(3) follows directly from (2) and the fact that there are 2^{ω} many non–isomorphic directed graphs of type 𝒦 _{ℒ_{2}ℱ}, which is proved in [Hen].

(4) follows from (3) if you take into account that two ω–categorical structures have isomorphic automorphism group as topological groups iff they are bi– interpretable in each other (see [AZ]). Use further that in one particular directed graph, there are only countably many different directed graphs interpretable. So the equivalence classes under the equivalence relation “bi–interpretability” on non–isomorphic directed graphs are countable.

Furthermore observe that for structures M, M′ having the (SIP) AutM is isomorphic to AutM′ as a topological group iff they are isomorphic as groups. This is because then the topology can completely be defined from the pure group (not using the operation on M): A subset is open iff it is the union of cosets of subgroups of G having at most countable index.

6. Final remarks

One can hardly expect (EP) to hold for a class 𝒦 , if (AP) does not hold for 𝒦 . In fact, if you extend a partial isomorphism p : D → D′, D, D′ ⊂ A∈𝒦 , to an automorphism f ∈Aut(B), with B∈𝒦 , A⊂B, then you solve the amalgamation problem id : D ↪ A, p : D ↪ A (via f À : A ↪ B, id : A ↪ B).

Also the joint embedding property together with (EP) implies (AP): Let D, B, C ∈ 𝒦 , D ⊂ B, D ⊂ C. By the joint embedding property there exists A∈𝒦 , B ⊂ A, j : C ↪ A. Now j D̀ is a partial isomorphism on A. By (EP) there exists E ∈𝒦 , A ⊂ E and f ∈Aut(B) extending j D̀. Now jf^{−1} : C ↪ E and jf^{−1} D̀ = id D̀. This solves the amalgamation problem.

Having this remark in mind the restriction in Theorem 4 on the family ℱ to consist of packed structures looks quite natural. It is the restriction needed to ensure that (AP) holds for the class. In fact we have the following:

Lemma 14 Let S be a finite relational language. Let ℱ be a set of finite structures. 𝒦 ℱ satisfies (AP) iff there exists a set of packed structures ℱ′ such that 𝒦 ℱ = 𝒦 ℱ′.

Proof: Let us first remark that 𝒦 ℱ has (AP) iff 𝒦 ℱ has (fAP). For suppose 𝒦 ℱ has (AP). Let A, B, C ∈ 𝒦 ℱ ∪ {∅} A ⊂ B, A ⊂ C. By (AP) there exists D ∈ 𝒦 ℱ and embeddings i_{1} : B ↪ D, i_{2} : C ↪ D with i_{1} À = i_{2} À. But this leads in a natural way to a weak homomorphism which we like to call i_{1}∗_{A}i_{2} : B∗_{A}C →w D. [In fact if you like to think in terms of the category of Sstructures, with weak homomorphisms as morphisms, then B ∗_{A} C is the fibered co–product (of A ↪ B and A ↪ C) in that category, and is therefore uniquely determined up to isomorphism by this property.] But from B ∗_{A} C →w D and D ℱ–free follows B ∗_{A} C ℱ–free.

We say ℱ is good, if for every T ∈ ℱ and every finite S–structure T′, if T →w T′ (by this we mean more formally: if there exists a weak homomorphism h : T →w T′) then T′∈ℱ.

Claim: If ℱ is good and 𝒦 ℱ satisfies (AP) then for every T ∈ℱ there exists a packed T′∈ℱ such that T′ →w T. Proof of the claim: Let T ∈ ℱ be a counterexample minimal in size. As there does not exist a packed T′ ∈ ℱ such that T′ →w T, T is not packed. T being not packed means exactly that we can write T ≅ T_{1} ∗_{T_{0}} T_{2} with ^{#}T_{1} < ^{#}T and #T_{2} < ^{#}T. As T ∉ 𝒦 ℱ and as 𝒦 ℱ has the (AP) T_{i} ∉ 𝒦 ℱ for i = 1 or i = 2. This means there exists T′ ∈ℱ and ρ : T′ →w T_{i}. As ℱ is good T_{i} ∈ℱ. But as T_{i} →w T there can not be a packed structure T′ ∈ ℱ such that T′ →w T_{i}. T_{i} contradicts the minimality assumption on T.

From the claim follows the Lemma: Let ℱ be a family of structures such that 𝒦 ℱ has the (AP). Let ℱ′ be the family (well, formally it is a class) of finite structures T′ such that there exists T ∈ℱ with T →w T′. We have 𝒦 ℱ = 𝒦 ℱ′. If we let ℱ′′ be the family of elements of ℱ′ which are packed, then we have 𝒦 ℱ′ = 𝒦 ℱ′′ by the claim.

There is also a variant of (EP) available in classes of structures, which fail to have the amalgamation property:

Definition: 𝒦 has the weak extension property (WEP), if for every finite A∈𝒦 and partial isomorphisms p_{1}, …, p_{n} on A, if there exists a possibly infinite structure M ∈𝒦 , A ⊂ M and g_{1}, …, g_{n} ∈Aut(M) such that p_{i} ⊂ g_{i}, then there exists a finite structure B∈𝒦 , A⊂B and f_{1}, …, f_{n}∈Aut(B) such that p_{i} ⊂f_{i}.

There is a joint paper with Daniel Lascar in preparation, where we are going to prove the (WEP) for several classes 𝒦 . These properties will be strongly connected to properties of the free groups in finitely many generators. In fact the results in that paper will be stronger than Theorem 5. The methods used there will be quite different from the methods in this paper, and the proof of the stronger theorem will be much longer and more complicated.

Remark: Let us point out that in the context of this paper the weak extension property is not weaker than the extension property:

Let 𝒦 be a class of structures having the amalgamation property. Also suppose that 𝒦 contains the generic countable structure, the “Fraïssé–limit” of its finite structures. Then 𝒦 has the (WEP) iff 𝒦 has the (EP).

Proof: Let A ∈ 𝒦 be finite, let p_{1}, …, p_{n} be partial isomorphisms on A. We have to show that there exists M ∈𝒦 , A⊂M, g_{1}, …, g_{n}∈Aut(M), g_{i} ⊃p_{i}. Take M to be the generic countable structure and embed A into M. Now p_{i} extends to g_{i}∈Aut(M) because of the homogeneity of M.

In [HL] we prove that for a finite family ℱ of structures the class 𝒦 ℱ has the (WEP). The condition on the elements of ℱ being packed is not longer necessary. In that context it is obvious that working with weak homomorphisms as opposed to embeddings is essential:

Examples:

• The class of total orderings is the class of {R}–structures of link type ℒ_{2} = {·, · → ·} (see the example at the beginning of section 4) which avoids (as substructures) the structures A_{2} and C_{3}, where A_{2} consists of 2 points with no edge, and C_{3} consists of 3 points a, b, c where R^{C_{3}} = {(a, b), (b, c), (c, a)}. As finite orderings allow nontrivial partial isomorphisms but do not allow nontrivial automorphisms and as they are embeddable into the homogeneous ordering of the rationals, this class does not even satisfy (WEP).

• The class of tournaments is the class of {R}–structures of link type ℒ_{2} which avoid A_{2}. It is an open question, iff the class of tournaments satisfies (WEP). For this class (as it satisfies (AP)) (WEP) is equivalent to (EP).

The restriction to irreflexive structures in section 4 and section 5 is not essential. The theorems also hold without this restriction.

Theorem 15 Let ℱ be a set of finite packed S–structures. Let ℒ be a set of link structures.

(1) 𝒦 ℒℱ has (EP).

(2) The generic structure Mℒℱ of the class has the (SIP).

Proof: It suffices to prove (1), as (2) follows from (1) and section 5. We use a natural method to code arbitrary structures by irreflexive ones: Let R be an r–ary relation symbol and let x_{1}, …, x_{r} be pairwise distinct variables. For every r′ ^{≤} r and every formula Rx_{i_{1}} … x_{i_{r}} where {i_{1}, …, i_{r}} = {1, …, r′} we introduce a new r′–ary relation symbol R^{(i_{1},...,i_{r})} with the intended meaning: R^{(i_{1},...,i_{r})}x_{1} … x_{r′} iff x_{1}, …, x_{r′} are pairwise distinct and Rx_{i_{1}} … x_{i_{r}}. Let S^{∗} be the set of relation symbols obtained in this way. We regard every S– structure A as an irreflexive S^{∗}–structure, which we denote by A^{∗} by defining: R^{(i_{1},...,i_{r})}a_{1} … a_{r′} holds in A^{∗} iff a_{1}, …, a_{r′} are pairwise distinct and Ra_{i_{1}} … a_{i_{r}} holds.

If A has link type ℒ then A^{∗} hast link type ℒ^{∗} = {L^{∗} | L∈ℒ }. Conversely if B is of link type ℒ^{∗} then there exists a unique S–structure A, such that A^{∗} = B.

We will suppose that ℱ is closed under homomorphic images. By this we mean: If T ∈ℱ and h : T → T′ is a surjective weak homomorphism, then there exists T′′ ∈ ℱ with T′′ ≅ T′. It is no problem to assume ℱ to be closed under homomorphic images, as homomorphic images of packed structures are packed, and as for h : T →w T′: If A is T –free, then it is also T′–free.

We let ℱ^{∗} := {T^{∗} | T ∈ℱ}.

Claim: If A is an S-structure, then A is ℱ–free iff A^{∗} is ℱ^{∗}–free. The difficult direction is “⇐”: Suppose A^{∗} is ℱ^{∗}–free, but there exist T ∈ℱ and h : T →w A. As ℱ is closed by homomorphic images we can assume h to be an embedding (we can replace T by the substructure T^{h} of A). We now can consider h as a mapping between S^{∗}–structures, and we see that h : T^{∗} ↪ A^{∗}. This is a contradiction.

Now we finish the proof of the theorem. We let A ∈ 𝒦 ℒℱ and p_{1}, …, p_{n} be partial isomorphisms of A. Then A^{∗} ∈ 𝒦 ℒ^{∗}ℱ^{∗} and p_{1}, …, p_{n} are partial isomorphisms of A^{∗}. By Theorem 5 there exists C ∈ 𝒦 ℒ^{∗}ℱ^{∗} A^{∗} ⊂ C and f_{1}, …, f_{n} ∈ Aut(C) with p_{i} ⊂ f_{i} for every i. Now C is of the form B^{∗}, where B∈𝒦 ℒℱ and A⊂B.

There is a description of the classes 𝒦 ℒℱ in terms of axioms: Let S be a finite relational language. The classes 𝒦 ℒℱ (where ℒ is a family of link structures and ℱ is a family of finite packed structures) are the classes which are axiomatizable by axioms of the following forms:

• ∀xφ(x), where φ(x) is a quantifier free formula (in one variable).

• ∀x̄(Rx̄ → φ(x̄)), where r ∈ ω, x̄ = x_{1} … x_{r}, R is r–ary and φ(x̄) is a quantifier free formula • ¬∃ȳ⋀_{i=1}^{t} φ_{i}(ȳ), where k, t ∈ ω, ȳ = y_{1} … y_{k}, each φ_{i}(ȳ) is an atomic

formula, for every j, j′ with 1^{≤} j < j′ ^{≤} k there exists i (1^{≤} i^{≤} t) such that y_{j} and y_{j′} both appear in φ_{i}(ȳ).

It is also no problem to allow finitely many constants in the language as long as one insists that all the domains of the partial isomorphisms in question contain all the constant. For simplicity we will not speak about structures of a given link type.

Corollary 16 Let S be a finite relational language with constants. Let ℱ be a family of finite packed structures each in a sublanguage of S. Let 𝒦 ℱ be the class of ℱ–free S–structures. 𝒦 ℱ has the (EP). Hereby a partial isomorphism p on A is an isomorphism between two S–substructures of A.

The condition on the partial isomorphisms just means that for all the constants c in the language and every of the partial isomorphisms p, c (or rather the interpretation c^{A} of c in A) is in D(p) and c^{p} = c. Proof: We replace in the language S every constant c by a unary predicate U_{c}, which is intended to hold only for the interpretation of c. We denote this new relational language by S^{∗}. Every structure A in a sublanguage of S can be considered in a natural way as an S^{∗}–structure, which we denote by A^{∗}. Hereby we interpret relation symbols from S which have not been in the language of A by the empty set, and the same for symbols U_{c}, where c has not been in the language of A. We let ℱ^{∗} = {T^{∗} | T ∈ℱ}.

Now let A∈𝒦 ℱ be finite and p_{1}, …, p_{n} be partial isomorphisms on A. We have A^{∗} ∈𝒦 ℱ^{∗}. By Theorem 15 there exists a finite E ∈𝒦 ℱ^{∗} and f_{1}, …, f_{n} ∈ Aut(E), such that A^{∗} ⊂ E and p_{i} ⊂ f_{i} for each i. We only have to check that U_{c}^{E} = U_{c}^{A^{∗}} = {c} to conclude that E = B^{∗} for some B ∈𝒦 ℱ and to finish the proof.

But we can easily suppose that for every element d∈E there exists f ∈ < f_{1}, …, f_{n} > such that d^{f} ∈ A^{∗}. Now if we take d ∈ U_{c}^{E} and suppose that d^{f} ∈ A then d^{f} ∈ U_{c}^{A} and therefore d^{f} = c. But for every f′ ∈ < f_{1}, …, f_{n} > c^{f′} = c as c is fixed by every f_{i}. In particular d = c^{f^{−1}} = c.

References

[AHN] Andréka, Hodkinson, Németi: The Finite Base Property for some Cylindric–Relativized Algebras, preprint, 1996

[AZ] Ahlbrandt, Ziegler: Quasi Finitely Axiomatizable Totally Categorical Theories, Annals of Pure and Applied Logic 30(1986), 63-82,

[C] P. Cameron: Oligomorphic Permutation Groups, LMSLNS 152, Cambridge University Press, 1990, [Fr] R. Fraïssé: Sur l’extension aux rélations de quelques propriété des ordres,

Ann. Sci. l’École Norm. Sup. 71(1954) 361-388,

[Gr] M. Grohe: Arity Hierarchies, Annals of Pure and Applied Logic 82(1996), 103-163,

[GGK] Goldstern, Grossberg, Kojman: Infinite Homogeneous Bipartite Graphs with Unequal Sides, Discrete Mathematics 149(1996), 69-82

[Hen] W. Henson: Countable Homogeneous Relational Structures and ℵ_{0}-categorical Theories, The Journal of Symbolic Logic 37(1972) 494-500,

[Hg] B. Herwig: Extending Partial Isomorphisms, Combinatorica, 15(1995), 365-371,

[HL] Herwig, Lascar: Extending Partial Isomorphisms and the Profinite Topology on the Free Groups, in preparation, 1997,

[Hr] E. Hrushovski: Extending Partial Isomorphisms of Graphs, Combinatorica 12(1992), 411-416,

[HHLS] Hodges, Hodkinson, Lascar, Shelah: The Small Index Property for ω–stable, ω–categorical Structures and for the Random Graph, Journal of the LMS 48(1993), 204-218,

[KM] Kaye, Macpherson: Automorphisms of First–Order Structures, Clarendon Press, Oxford, 1994,

[L] D. Lascar: Autour de la propriété du petit indice, Proc. London Math. Soc. 62(1991), 25-53,

[P] M.G. Peretyat’kin: On Countable Theories With a Finite Number of Denumerable Models, Algebra i Logika 12(1973), 570-576 (310-326 in the english translation),

[T] J.K. Truss: Generic Automorphisms of Homogeneous Structures, Proc. London Math. Soc. 65(3)(1992), 121-141.