ℵ_{0}-categorical structures with arbitrarily fast growth of algebraic closure

David M. Evans^{∗} and M. E. Pantano

1 Introduction

Over the past 25 years, various results have been proved about the growth rates of certain sequences of integers associated to infinite permutation groups. Most of the results concern the number of orbits of the automorphism group of an ℵ_{0}-categorical structure M on the set of unordered n-subsets or on the set of n-tuples of elements of M. (Recall that by the Ryll-Nardzewski Theorem, if M is countable and ℵ_{0}-categorical, the number of the orbits of the automorphism group Aut(M) on the set of n-tuples is finite and equals the number of complete n-types consistent with the theory of M.) Many of the results known about these sequences are collected in the book [Ca90] by P. J. Cameron. One of the oldest (in the realms of ‘folklore’) is that for any sequence (k_{n})_{n∈N} of natural numbers there is a countable ℵ_{0}-categorical structure M such that the number of orbits of Aut(M) on the set of n-tuples from M is greater than k_{n} for all n.

These investigations suggested the study of the growth rate of another sequence. Let M be an ℵ_{0}-categorical structure and X be a finite subset of M. Let acl(X) be the algebraic closure of X, that is, the union of the finite X-definable subsets of M. Equivalently, this is the union of the finite orbits on M of Aut(M)_{(X)}, the pointwise stabiliser of X in Aut(M). Define

b_{n} = b_{n}(M) = max{|acl(X)| : X ⊆ M, |X| = n}.

In [Ma86, Question 2], H. D. Macpherson posed the following problem:

∗Correspondence to First Author

Problem: Given any sequence {a_{n}}, is it always possible to find a transitive ℵ_{0}-categorical structure M such that b_{n} ≥ a_{n} for every n?

For ‘naturally occuring’ examples of ℵ_{0}-categorical structures b_{n} does not grow faster than doubly exponentially, and in many cases algebraic closure is trivial (i.e. for every finite subset X ⊆ M, acl(X) = X).

Independently, D. M. Evans and H. D. Macpherson gave positive answers to the above question. The structures produced by Evans (see [Ev94], Theorem 4.3) had primitive and not 2-transitive automorphism groups and those of Macpherson had imprimitive automorphism groups. So the question remained as to whether M in Macpherson’s problem could be multiply transitive. We show that it can be (although of course, in a k + 1-transitive structure, the algebraic closure of k points must be those k points, so we insist only that the algebraic closure grows arbitrarily rapidly from some point onwards). Specifically, we prove the following result (in Section 2).

Theorem 1. For every sequence (a_{i})_{i∈N} and every k ∈ N, k ≥ 2, there exists a (k − 1)-transitive, countable, ℵ_{0}-categorical k-uniform hypergraph M such that for each n > k, there exists A_{n} ⊆ M with |A_{n}| = n and |acl(A_{n})| ≥ a_{n}.

A k-uniform hypergraph is a k-ary relational structure, and one of the difficulties in the proof is that we use a finite language. The construction can be greatly simplified if we use an infinite language (see Theorem 2 in Section 3). All the constructions are modifications of E. Hrushovski’s construction of an ℵ_{0}-categorical pseudoplane (see [Hr88], [Wa94], [KL92]).

It would be very interesting to know if similar results can be obtained for stable ℵ_{0}-categorical structures. The Second Author’s Ph.D. thesis [Pa95] contains some partial attempts to do this. In contrast, in [St92], P. Steitz showed (using the structure theory of Cherlin, Harrington and Lachlan from [CHL85]) that if T is an ℵ_{0}-categorical, ℵ_{0}-stable theory and M is its countable model, then both the number s_{n}(T) of complete n-types consistent with T and the maximal size b_{n}(M) of the algebraic closure of a n-set of M are bounded:

s_{n}(T) ≤ 2^{mn^{2}}
b_{n}(M) ≤ q^{n}

where m and q are natural numbers depending only on M.

There is another sense, apart from the finiteness of the language, in which Theorem 1 is a stronger result than Theorem 2. For a structure M and a natural number k define the k-ary algebraic closure acl^{k}(X) of a subset X to be the smallest subset of M containing X which is closed under taking algebraic closure of k-element subsets. It is easy to see that the examples constructed to prove Theorem 1 have arbitrarily fast growth rate of k-ary algebraic closure, whereas those constructed (with much less effort) to prove Theorem 2 do not.

This notion is also relevant to the question of whether the structures in Theorem 1 can be taken to be stable. In [Ev00, Lemma 5.2], it is observed that k-ary algebraic closure in the stable ℵ_{0}-categorical structures in [Hr88] grows linearly.

Almost all of the material in this paper is taken from the Ph. D. Thesis [Pa95] of the Second Author at the University of East Anglia. A preliminary version of the paper has been available since 1995. Since then, the construction of unstable structures in [Hr88] has acquired an additional significance. In [Hr97], Hrushovski pointed out that these constructions give rise to simple, unstable ℵ_{0}-categorical structures which are not modular. To ensure that the structures we produce in

Theorems 1 and 2 are simple we require an extra condition on the function f used in the construction. If f(3t) ≤ f(t) + 1 (for t ≥ k) then the argument in [Hr97] shows that M is supersimple, of SU-rank k in the case of the structures for Theorem 1, and SU-rank 1 for those of Theorem 2 (more detail can be found in [Ev00, Theorem 3.6]). It seems clear that our arguments can be adjusted to accommodate this extra condition.

We conclude the Introduction with some definitions and notation which will be used in the rest of the paper.

If L is a first-order language, then a countable L-structure M is said to be ℵ_{0}-categorical if its theory has, up to isomorphism, a unique countably infinite model.

A permutation group G on an infinite set Ω is said to be oligomorphic if, for every n, it has only a finite number of orbits on Ω^{n}, the set of the n-tuples of elements of Ω.

The Theorem of Ryll-Nardzewski, Svenonius and Engeler states that a countable first-order structure M is ℵ_{0}-categorical if and only if its automorphism group Aut(M) is oligomorphic (see [CK90]).

If M is ℵ_{0}-categorical and A is a finite subset of M, then the algebraic closure acl(A) of A is the union of the finite orbits of the pointwise stabilizer (Aut(M))_{(A)} of A (by Ryll-Nardzewski Theorem, acl(A) is finite).

The age of a structure M is the class of all structures (with the same language as M) which are isomorphic to finite substructures of M.

A structure M is homogeneous if any isomorphism between finite substructures of M can be extended to an automorphism of M.

The Theorem of Fraïssé states that a class C of finite structures over a relational language is the age of some countable homogeneous relational structure if and only if it is closed under isomorphisms and under taking substructures, has only countably many non-isomorphic members and has the amalgamation property. Moreover, two countable homogeneous structures with the same age are isomorphic. Hrushovski’s construction is a modification of Fraïssé’s, working with a restricted notion of amalgamation (self-sufficient amalgamation). More details can be found in [Hr88], [Wa94], [KL92] and [Ev94], but we hope that our account here is self-contained.

A k-uniform hypergraph is a pair (V, H) where V is a set of points called vertices and H is a set of k-subsets of V, called (hyper)edges.

For the rest of the paper, k is fixed (k ≥ 2) and a k-uniform hypergraph will simply be called a graph.

The reader could refer to [Ca90], [Ev94] and [Ho93] for more background information on ℵ_{0}-categorical structures and infinite permutation groups.

2 Proof of Theorem 1

2.1 The Construction

The construction from [Hr88] makes use of a continuous, non-decreasing function f on the non-negative reals. We assume that the graph of f is piecewise linear, interpolated between the points (x, f(x)) for integers x. We define a class of finite (k-uniform hyper)graphs as follows.

Suppose A is a finite graph. Let x(A) be the number of vertices and e(A) be the number of edges of A. Let y(A) = kx(A)−e(A). Let H = {(x, y) : y ≥ f(x)} and let C_{0} be the class of finite graphs A such that (x(A), y(A)) ∈ H and C the class of the graphs A in C_{0} such that for each A′ ⊆ A, A′ ∈ C_{0}.

In our construction, we require that f satisfies the following additional properties. The existence of such functions is shown in the proof of Theorem 1.

F_{1}) For each m < k, f(m) = km; k(k − 1) < f(k) < k^{2};

F_{2}) For each m > k, f(m + 1) − f(m) ≤ \frac{1}{m+1};

F_{3}) The area below f is convex;

F_{4}) The function f is divergent;

F_{5}) The function f is increasing;

F_{6}) For each m ≥ k, m ≥ \frac{1}{k}f(m + 1) + \frac{4}{k^{2}(k−1)}(f(m + 1))^{2}.

So f is a slow-growing convex function which tends to infinity. First, we make a few comments on these properties. From F_{1} and F_{2} it follows that for every m > k we have f(m) ≤ km. F_{6} is a technical property which will be used to prove Lemma 5.

If B ∈ C we say that a subgraph A of B is self-sufficient in B (and write A ≤ B) if, for every finite graph B′ such that A ⊂ B′ ⊆ B, we have y(A) < y(B′). If M is infinite and A ⊆ M is finite, A ≤ M means that A ≤ B for all finite B with A ⊆ B ⊆ M.

We now want to prove that the class C is a self-sufficient amalgamation class. The following are taken directly from [Hr88]: proofs can also be found in [Wa94], for example.

Lemma 1 Suppose C ∈ C.

(i) If A, B ⊆ C then y(A ∪ B) ≤ y(A) + y(B) − y(A ∩ B). (ii) If A ≤ C and X ⊆ C then A ∩ X ≤ X. (iii) If A ≤ B ≤ C then A ≤ C. □

Definition 1 Let B_{1}, B_{2} be graphs and A ⊆ B_{1}, B_{2}. The free amalgam of B_{1} and B_{2} over A is the graph E whose universe is the disjoint union over A of the vertices of B_{1} and B_{2} and whose edges are just those of B_{1} and those of B_{2}.

Then x(E) = x(B_{1}) + x(B_{2}) − x(A) and e(E) = e(B_{1}) + e(B_{2}) − e(A), so y(E) = y(B_{1}) + y(B_{2}) − y(A).

Lemma 2 (Amalgamation) Let A, B_{1}, B_{2} ∈ C with A ≤ B_{1} and A ≤ B_{2}. Let E be the free amalgam, as above. Then E ∈ C and B_{1}, B_{2} ≤ E.

Proof. Let x_{0} = x(A), e_{0} = e(A), y_{0} = y(A) = kx(A) − e(A), a = (x_{0}, y_{0}) and x_{i} = x(B_{i}), e_{i} = e(B_{i}), y_{i} = y(B_{i}) = kx(B_{i}) − e(B_{i}), b_{i} = (x_{i}, y_{i}), with i = 1, 2.

To prove that E ∈ C, we want to prove that b_{1} + b_{2} − a lies above the graph of the function f and that every subgraph of E lies in C_{0}. However it is enough to prove the first part; in fact, if E′ ⊆ E, then E′ is the free amalgam over A ∩ E′ of B_{1} ∩ E′ and B_{2} ∩ E′ and, by Lemma 1 A ∩ E′ ≤ B_{i} ∩ E′ (i = 1, 2).

If x_{1} = x_{0} or x_{2} = x_{0}, we have A = B_{1} or A = B_{2} and the lemma is trivial. So we can assume x_{1} − x_{0} > 0, x_{2} − x_{0} > 0. From now on, we assume that x_{1}, x_{2} ≥ k (the other cases can be handled easily by F_{1}). Assume, without loss of generality, that

\frac{y_{2} − y_{0}}{x_{2} − x_{0}} ≥ \frac{y_{1} − y_{0}}{x_{1} − x_{0}} .

The slope of the line from a to b_{2} is (y_{2} − y_{0})/(x_{2} − x_{0}) and

\frac{y_{2} − y_{0}}{x_{2} − x_{0}} ≥ \frac{y_{1} − y_{0}}{x_{1} − x_{0}} ≥ \frac{1}{x_{1} − x_{0}} ≥ \frac{1}{x_{1}} ≥ f(x_{1}) − f(x_{1} − 1) ≥ f(x_{1} + 1) − f(x_{1}),

where the last two inequalitiea follow from properties F_{2} and F_{3}.

So the slope of to line from a to b_{2} is greater or equal to the slope of the (right) tangent line to the graph of f at the point (x_{1}, f(x_{1})) and, by F_{3}, b_{1} + (b_{2} − a) lies above the graph of f. Therefore E ∈ C.

To prove that B_{1} ≤ E, consider B′ such that B_{1} ⊂ B′ ⊆ E. Then B′ is the free amalgam over A of B_{1} and B′_{2} = B_{2}∩B′. So y(B′) = y(B_{1})+y(B′_{2})−y(A). As A ≤ B_{2} we have y(A) < y(B′_{2}), thus y(B′) > y(B_{1}). □

Lemma 3 There is a countable graph M with the following properties: 1. The class of the finite self-sufficient substructures of M is C.

2. If A ≤ M, A finite, B ∈ C and α : A → B is a self-sufficient embedding (i.e. αA ≤ B), then there exists a self-sufficient embedding γ : B → M with γα(a) = a for each a ∈ A.

Moreover,

(i) If X ⊆ M there is Y ≤ M with X ⊆ Y and |Y | ≤ f^{−1}(y(X)). (ii) M is unique up to isomorphism, and any isomorphism between selfsufficient subgraphs of M extends to an automorphism of M. (iii) M is ℵ_{0}-categorical.

Proof. The construction is standard using Lemmas 1 and 2 and (ii) follows from a back-and-forth argument once we have (i). To obtain (iii) note that properties (1) and (2) are first-order expressible (by (i)); alternatively one can use (i), (ii) to show that the number of n-types over ∅ is finite, and use the Ryll-Nardzewski theorem.

To see (i), note that if X ⊆ B and y(X) ≥ y(B) then x(B) ≤ f^{−1}(y(X)), by definition of C. Take Y ⊇ X with y(Y) ≤ y(X) and Y as large as possible. Then Y ≤ M. □

Remark 1 If M is the above structure, and A is a finite subset of M, then acl(A) is the smallest B such that A ⊆ B and B ≤ M.

2.2 Some graphs in C

Suppose we have a function f with properties F_{1} − F_{6} and a structure M as in Lemma 3. Then for every n > k and m with n ≤ m ≤ f^{−1}(kn), we construct a graph A_{n} ⊆ M of size n such that |acl(A_{n})| = m.

Let A_{n} be the graph with n vertices and no edges. Then x(A_{n}) = n and y(A_{n}) = kn. Let t be a natural number. We construct a graph A containing A_{n} in the following way. The vertices of A are v_{i,j}, where 1 ≤ i ≤ t − 1 and 0 ≤ j ≤ n − 1 and v_{t,0}, …, v_{t,s} where s ≤ n − 1. The set S_{i} of vertices with first index i will be referred to as the i-th layer of A. So A has t layers and all apart from the final one have n vertices. We now define the edges of A (remember that these are k-element sets of vertices). For 1 ≤ i ≤ t − 1 and 0 ≤ j ≤ n − 1 let B_{i,j} = {v_{i,j}, v_{i,j+1}, …, v_{i,j+k−1}}, where the second index here is read modulo n. So this is a set of k ‘consecutive’ points in the i-th layer. We refer to such a subset as a block. Each block contains k subsets of size k − 1, and for a vertex v_{i+1,j} we have an edge {v_{i+1,j}} ∪ S for each such subset S ⊆ B_{i,j}.

We identify S_{1} with A_{n}. To compute y(A) consider building A by adding points one at a time in successive layers, starting with S_{1}. Each time we add a point v_{i,j}, we add k new edges, associated to the block B_{i−1,j}. Thus adding a new point in this way does not change the y-value of the graph, so y(A) = y(S_{1}) = kn. Let m_{0} be the largest integer with m_{0} ≤ f^{−1}(kn). Clearly if A is to be in C we must have x(A) ≤ m_{0}. We show that the converse is true. The difficulty is, of course, that we must check that y(H) ≥ f(x(H)) for all subgraphs H of A.

Lemma 4 If H is a subgraph of A and |S_{i} ∩ H| = n for some 1 ≤ i ≤ t, then y(H) ≥ kn.

Proof. We refer to H ∩ S_{j} as a layer of H and say that this is full if it has n vertices. Without loss of generality, we can assume that the last non-empty layer of H is a full layer. In fact, if it is not, we can consider the subgraph H′ of H in which the full layer is the last one and note that y(H′) ≤ y(H) (as in the computation of y(A)). As t has not yet been fixed, we may simplify the notation and assume that the last layer of H is the t-th and that this is full.

As H is a subgraph of A, we can obtain H from A by deleting some of its vertices. We want to calculate the number of edges which are lost when we delete those vertices. So let u_{ℓ} be the number of vertices we delete in the layer S_{ℓ}, with ℓ = 1, …, t. As u_{t} = 0 we have:

x(H) = x(A) − ∑_{ℓ=1}^{t−1} u_{ℓ}.

For 1 ≤ ℓ ≤ t − 1 let r_{ℓ} be the minimum number of edges between S_{ℓ} and S_{ℓ+1} that we lose when we delete u_{ℓ} points in S_{ℓ}. Then e(H) ≤ e(A)−∑_{ℓ=1}^{t−1} r_{ℓ}, and so

y(H) ≥ y(A) − k ∑_{ℓ=1}^{t−1} u_{ℓ} + ∑_{ℓ=1}^{t−1} r_{ℓ} = kn − k ∑_{ℓ=1}^{t−1} u_{ℓ} + ∑_{ℓ=1}^{t−1} r_{ℓ}.

Then we want to show that

∑_{ℓ=1}^{t−1} r_{ℓ} ≥ k ∑_{ℓ=1}^{t−1} u_{ℓ}.  (1)

Claim: Let u be the number of vertices deleted in S_{ℓ}. Then if r is the minimum number of edges lost between this layer and S_{ℓ+1}, we have the following table:

\begin{matrix}(i) & u = 0 & r = 0; \\ (ii) & u = 1 & r = k(k − 1); \\ (iii) & 2 ≤ u ≤ n − k & r ≥ uk; \\ (iv) & u = n − (k − 1) & r = kn − 2; \\ (v) & n − (k − 2) ≤ u ≤ n & r = kn. \end{matrix}

Proof of the claim:

(i) Trivial. (ii) The point we delete belongs to k blocks and to (k − 1) of the k edges of each block. (iv) If we have only (k − 1) vertices left in the layer, we can have at most 2 edges left.

(v) If we have less than (k − 1) vertices left in the layer, we cannot form any edge. (iii) We split this case into two parts.

(a) Suppose that, after deleting the u vertices, there is at least one whole block of points left. We can assume this block to be B_{ℓ,n−k}. We will prove the statement by induction on u. Suppose u = 2. By (ii), if we delete the vertex v_{ℓ,j}, we lose k(k − 1) edges. If we now delete v_{ℓ,j+1}, we lose 1 (new) edge for each of the (k − 1) blocks B_{ℓ,j−k+2}, … B_{ℓ,j} and (k − 1) edges of the block B_{ℓ,j+1}. In total, we lose (k − 1) · 1 + 1 · (k − 1) = 2(k − 1) edges. If, instead of v_{ℓ,j+1}, we delete v_{ℓ,j+2}, we have only (k − 2) blocks in common with v_{ℓ,j} and so the number of edges we lose is (k − 2) · 1 + 2 · (k − 1); in general, if, after v_{ℓ,j}, we delete the point v_{ℓ,j+q}, we lose (k − q) · 1 + q · (k − 1) new edges, when 1 ≤ q ≤ k and k(k − 1) if q ≥ k. So the minimum value of r is 2(k − 1), reached for q = 1. Then, for u = 2

r = k(k − 1) + 2(k − 1) = (2 + k)(k − 1) = 2k + (k^{2} − k − 2) ≥ 2k = uk.

Now consider what happens when we delete u + 1 vertices of S_{ℓ}. Do this in increasing order of the second index. By inductive hypothesis, the number r_{u} of edges lost when we have deleted the first u points is ≥ uk. Let v_{ℓ,j} be the vertex with maximal j amongst the u points. Now delete the vertex v_{ℓ,j+p} (note that 0 < p < n − k − j). In this case, if p ≤ k − 1, we lose (k − 1) edges of B_{ℓ,j+p} and at least one further edge of B_{ℓ,j}; if p ≥ k, we lose k − 1 edges of each of the k blocks B_{ℓ,j+p}, …, B_{ℓ,j+p−(k−1)}. Then

r ≥ uk + k − 1 + 1 = k(u + 1).

This proves case (iii)(a).

(b) Suppose now that every block of S_{ℓ} has lost at least one point. Every remaining point v_{ℓ,i} in S_{ℓ} is joined at most to k points of S_{ℓ+1} (the vertices v_{ℓ+1,i−k+1}, … v_{ℓ+1,i}). Moreover, as every remaining block of S_{ℓ} has at most (k − 1) points, there is at most one edge to which both v_{ℓ,i} and v_{ℓ+1,i−s} (s = 0, … k − 1) belong. So the number kn − r of edges left is at most k(n − u). Then kn − r ≤ k(n − u), i.e. r ≥ ku.

This concludes the proof of the claim.

As in each case of the claim r ≥ uk, Equation (1) holds and the lemma is proved. □

Corollary 1 Suppose x(A) ≤ m_{0}. If H is a subgraph of A and H has a full layer, then H ∈ C_{0}.

Proof. f(x(H)) ≤ f(x(A)) ≤ kn ≤ y(H). □

Lemma 5 If x(A) ≤ m_{0} then A ∈ C.

Definition 2 A graph B ∈ C_{0} is tight if f(x(B) + 1) > y(B).

Proof of Lemma 5: Suppose A is not in the class C. Then there are subgraphs of A which are not in C_{0}. Let H′ be minimal with respect to this property. Let x be a vertex in the last layer of H′ and consider the graph H = H′ \ {x}. By minimality of H′, H and all its subgraphs are in C_{0} and so in C. Claim: H is tight. Proof of the claim: First, we note that x(H) = x(H′)−1 and e(H) = e(H′)−ε where:

ε = k, if all the block corresponding to x (i.e. the block of the previous layer to which x is joined) is in H′;

ε = 1, if (k − 1) points of the block corresponding to x are in H′; ε = 0, if less than (k − 1) points of the block corresponding to x are in

H′.

So y(H) = k(x(H′) − 1) − (e(H′) − ε) = y(H′) − k + ε. If we can prove that k = ε, then y(H′) = y(H) and so f(x(H)) ≤ y(H) and f(x(H) + 1) = f(x(H′)) > y(H′) = y(H), which proves that H is tight. Now f(x(H′)) − f(x(H)) = f(x(H) + 1) − f(x(H)), y(H) ≥ f(x(H)) and y(H′) < f(x(H′)). By F_{2},

1 ≥ \frac{1}{x(H) + 1} ≥ f(x(H) + 1) − f(x(H)) > y(H′) − y(H)

and y(H′) − y(H) = k − ε. Then k − ε < 1 and so k = ε. This concludes the proof of the claim.

Also y(H) < kn, because

kn = y(A) ≥ f(x(A)) ≥ f(x(H) + 1) > y(H′) = y(H).

Let h_{i} = |H ∩S_{i}|; n_{2} the number of points v_{i+1,j} of H with the corresponding block B_{i,j} contained in H; n_{1} the number of points of H having all but 1 point of the corresponding block contained in H; n_{0} the number of points of H having less than k − 1 points of the corresponding block contained in H. Let s_{i} be the number of points of H in the i-th layer not having a complete block in the (i − 1)-th layer and ℓ = max(i : h_{i} ≠ 0). Note that in counting n_{0}, n_{1}, n_{2} and s_{i} we do not consider the points in the first layer.

First, we show that, if 2 ≤ i ≤ ℓ, then h_{i} > 0, i.e. H has no empty layer apart, possibly, from the first.

Suppose this is not true. By definition h_{ℓ} > 0 so H can be written as the free amalgam over the empty set of two non-empty subgraphs H_{1} and H_{2}, with H_{1}, H_{2} ∈ C. Then x(H) = x(H_{1}) + x(H_{2}) and y(H) = y(H_{1}) + y(H_{2}). Suppose x(H_{2}) ≥ x(H_{1}) ≥ k. By F_{2}:

f(x(H) + 1) − f(x(H)) ≤ \frac{1}{x(H)+1} = \frac{1}{x(H)−(−1)}
f(x(H)) − f(x(H) − 1) ≤ \frac{1}{x(H)} = \frac{1}{x(H)−0}
⋮
f(x(H_{2}) + 1) − f(x(H_{2})) ≤ \frac{1}{x(H_{2})+1} = \frac{1}{x(H)−[x(H_{1})−1]}

If we sum these inequalities, we obtain:

f(x(H)+1)−f(x(H_{2})) ≤ ∑_{i=−1}^{x(H_{1})−1} \frac{1}{(x(H) − i)} < ∑_{i=−1}^{x(H_{1})−1} \frac{1}{x(H) − [x(H_{1}) − 1]} =

[x(H_{1}) + 1]\frac{1}{x(H) − x(H_{1}) + 1} = \frac{x(H_{1}) + 1}{x(H_{2}) + 1} ≤ 1.

Then f(x(H)+1) < f(x(H_{2}))+1 ≤ y(H_{2})+1 ≤ y(H_{2})+y(H_{1}) = y(H) and, as H is tight, this is a contradiction. If x(H_{1}) < k then one easily obtains a contradiction to tightness.

Note that by Lemma 4, H has no full layer. Moreover, by construction of A we may clearly assume that h_{1} ≠ 0. Then for each i with 1 ≤ i ≤ ℓ, we have 0 < h_{i} < n. Note that ∑_{i=2}^{ℓ} s_{i} = n_{0} + n_{1}. For i = 1, …, ℓ − 1, the number of points of H in the (i + 1)-th layer which have a complete block in the previous layer is h_{i+1} − s_{i+1}. Thus as the i-th layer is not full, h_{i} ≥ (h_{i+1} − s_{i+1}) + k − 1, with equality occurring when the h_{i+1} points with complete block are consecutive (mod n). Rearranging we have:

h_{i+1} − h_{i} ≤ s_{i+1} − (k − 1) for each i = 1, …, ℓ − 1.

We can sum and obtain, for 1 ≤ j ≤ ℓ − 1,

h_{j+1} − h_{1} ≤ ∑_{i=2}^{j+1} s_{i} − j(k − 1),  (2)

i.e.

h_{j+1} ≤ h_{1} + ∑_{i=2}^{j+1} s_{i} − j(k − 1) ≤ h_{1} + n_{0} + n_{1} − j(k − 1).

So

∑_{j=1}^{ℓ−1} h_{j+1} ≤ (ℓ − 1)(h_{1} + n_{0} + n_{1}) − \frac{ℓ(ℓ − 1)}{2}(k − 1),

and therefore

x(H) ≤ h_{1} + (ℓ − 1)(h_{1} + n_{0} + n_{1}) − \frac{ℓ(ℓ − 1)}{2}(k − 1).

Now

y(H) = k(h_{1} + n_{0} + n_{1} + n_{2}) − kn_{2} − n_{1} = kh_{1} + kn_{0} + (k − 1)n_{1} (3)

and as k − 1 ≥ k/2, we have y(H) ≥ (k/2)(h_{1} + n_{0} + n_{1}). So

x(H) ≤ h_{1} + \frac{2y(H)}{k}(ℓ − 1) − \frac{ℓ(ℓ − 1)}{2}(k − 1).  (4)

We want an inequality independent of ℓ. By (2) with j = ℓ − 1,

h_{ℓ} − h_{1} ≤ ∑_{i=2}^{ℓ} s_{i} − (ℓ − 1)(k − 1) = n_{0} + n_{1} − (ℓ − 1)(k − 1)

thus

(ℓ − 1) ≤ \frac{1}{k − 1}(n_{0} + n_{1} − h_{ℓ} + h_{1}) ≤ \frac{1}{(k − 1)}(n_{0} + n_{1} + h_{1}) ≤ \frac{1}{(k − 1)} \frac{2y(H)}{k}.

(5)

By (4) and (5)

x(H) ≤ h_{1} + \frac{2y(H)}{k} \frac{2y(H)}{k(k − 1)} − \frac{ℓ(ℓ − 1)}{2}(k − 1) ≤ h_{1} + \frac{4(y(H))^{2}}{k^{2}(k − 1)}.

Also, by (3), y(H) ≥ kh_{1} and therefore

x(H) ≤ \frac{y(H)}{k} + \frac{4(y(H))^{2}}{k^{2}(k − 1)}.

But by F_{6} and tightness of H we have

x(H) ≥ \frac{f(x(H) + 1)}{k} + \frac{4}{k^{2}(k − 1)}(f(x(H)+1))^{2} > \frac{y(H)}{k} + \frac{4}{k^{2}(k − 1)}(y(H))^{2}

and we have a contradiction. □ For the rest of this subsection, M is as in Lemma 3.

Lemma 6 Suppose A ≤ M is isomorphic to the graph just constructed. Then A is the algebraic closure of A_{n}.

Proof. We know that Y = acl(A_{n}) ≤ A as A ≤ M. On the other hand by Lemma 4, y(Y) ≥ kn = y(A). So Y = A. □

Corollary 2 For each n > k, there exists A_{n} ⊂ M such that |A_{n}| = n and |acl(A_{n})| = m where m is the integer part of f^{−1}(kn). □

Lemma 7 The group Aut(M) is (k − 1)-transitive.

Proof. By Lemma 3(ii) it suffices to observe that any set of k − 1 points in M is self-sufficient. This follows from F_{1}. □

2.3 Proof of Theorem 1

Theorem 1 For every sequence (a′_{i})_{i∈N}, there exists a (k − 1)-transitive countable ℵ_{0}-categorical k-uniform hypergraph M such that for each n > k, there exists A_{n} ⊆ M with |A_{n}| = n and |acl(A_{n})| ≥ a′_{n}.

Proof. By Corollary 2 it is now enough to construct a function f satisfying F_{1}-F_{6} and such that f^{−1}(kn) ≥ a′_{n}, for n > k.

We define by induction a sequence (a_{i})_{i∈N} with a_{i} ≥ a′_{i} for each i > k and a function (defined on the integers) such that f(a_{i}) = ki, for each i > k.

Let a_{i} = i, f(i) = ik for i < k, f(k) = k^{2} − 1. Suppose j ≥ k + 1 and that we have constructed a_{1}, …, a_{j−1} and f(m) for m ≤ a_{j−1}. Let r be an integer parameter and define a space P (r) ⊆ R^{r} by (p_{1}, …, p_{r}) ∈ P (r) iff

P_{1}) p_{i} > 0;

P_{2}) p_{i} > p_{i+1};

P_{3}) p_{i} < 1/(a_{j−1} + i);

P_{4}) p_{1} < f(a_{j−1}) − f(a_{j−1} − 1).

Each of the sets defined by a condition P_{1}, P_{2}, P_{3} and P_{4} is convex, thus so is P (r). In particular, P (r) is connected. Define a function γ : P → R by

γ(p_{1}, … p_{r}) = ∑_{i=1}^{r} p_{i}.

The function γ is continuous and 0 is a limit point of Imγ. Moreover, as

∑_{i=1}^{∞} min (\frac{1}{a_{j−1} + i} , f(a_{j−1}) − f(a_{j−1} − 1))

is divergent, there exists \overline{r} such that, for each r ≥ \overline{r}, we have ∑_{i=1}^{r} p_{i} > k for some (p_{1}, …, p_{r}) ∈ P (r). For such an r, by the Intermediate Value Theorem, there exists (α_{1}, …, α_{r}) ∈ P (r) such that

∑_{i=1}^{r} α_{i} = k.

Let r_{j−1} be the smallest such r with

a_{j−1} + r ≥ max (a′_{j}, (j + 1) + [4(j + 1)^{2}]/(k − 1)),

and let (α_{1}, …, α_{r_{j−1}}) be chosen as above. Let a_{j} = a_{j−1} + r_{j−1} and, for a_{j−1} + 1 ≤ m ≤ a_{j},

f(m) = f(a_{j−1}) + ∑_{i=1}^{m−a_{j−1}} α_{i}.

Note that

f(a_{j}) = f(a_{j−1}) + ∑_{i=1}^{a_{j}−a_{j−1}} α_{i} = k(j − 1) + ∑_{i=1}^{r_{j−1}} α_{i} = kj

and a_{j} = a_{j−1} + r_{j−1} ≥ a′_{j}.

Let f be the simplest piecewise linear function which joins the points (n, f(n)) (n ≥ k). We now want to show that f satisfies F_{1}, …, F_{6}.

F_{1}. By definition of f.

F_{2}. By construction and P_{3}.

F_{3}. By P_{2} and P_{4}.

F_{4}. As f(a_{j}) = kj for j > k.

F_{5}. By P_{1}.

F_{6}. By definition of r_{i−1}, for each i > k, a_{i} ≥ (i + 1) + [4(i + 1)^{2}]/(k − 1). Let n > k and let j be such that a_{j} ≤ n < n + 1 ≤ a_{j+1}. Then f(n + 1) ≤ f(a_{j+1}) = k(j + 1), so

\frac{f(n + 1)}{k} + \frac{4}{k^{2}(k − 1)}[f(n + 1)]^{2} ≤ \frac{k(j + 1)}{k} + \frac{4k^{2}(j + 1)^{2}}{k^{2}(k − 1)} ≤ a_{j} ≤ n.

□

3 Using an Infinite Language

3.1 The amalgamation class

In the previous section we have used a language with a single k-ary relation symbol. If an infinite language is used, things become a lot simpler. Suppose k_{0} ≥ 1.

Let L be a language with, for every k ≥ k_{0}, a_{k} k-ary relations R_{ik} (i = 1, …, a_{k}). We work with structures in which these relations are symmetric and disjoint. So, if R_{ik}(x_{1}, …, x_{k}) holds, then x_{1}, …, x_{k} are distinct and R_{ik} holds for any permutation of the x_{i}’s and R_{i′k}(x_{1}, …, x_{k}) does not hold for i ≠ i′.

Let X be such a structure with domain a finite set {x_{1}, …, x_{s}} and some of the relations R_{ik} defined on it. Let |X| = x(X) and define:

y(X) = |X| − ∑_{i,k} |R_{ik}[X]|

i.e.

y(X) = s − ∑_{k=k_{0}}^{s} ∑_{i=1}^{a_{k}} |R_{ik}[X]|,

where |R_{ik}[X]| denotes the number of subsets of {x_{1}, …, x_{s}} which satisfy the relation R_{ik}. As before we define a finite structure A to be self-sufficient in a structure B if A ⊆ B and y(A) < y(B′) for every B′ such that A ⊂ B′ ⊆ B.

Let f be a continuous function on the non-negative reals whose graph is the piecewise linear hull of the points (n, f(n)) for integer n and satisfying:

f_{1}) For every n ≥ k_{0}, f(n + 1) − f(n) ≤ 1/n.

f_{2}) The function f is divergent.

f_{3}) The function f is increasing and the sequence f(n + 1) − f(n) is non-increasing.

f_{4}) For every n ≥ k_{0}, f(n + a_{n+1}) ≤ n.

f_{5}) For every 1 ≤ s ≤ k_{0}, f(s) = s − 1.

As before, let C_{0} = {X : y(X) ≥ f(|X|)} and C = {X : X′ ∈ C_{0} for each X′ ⊆ X}. Lemma 1 still holds and we define the free amalgam as before. Then Lemma 2 holds for this class, and we build a structure M with properties as in the previous section. Its automorphism group is (k_{0} − 2)-transitive.

Theorem 2 For any sequence {a_{i}}_{i∈N}, there exists a (k_{0} − 2)-transitive structure M such that for each k > k_{0}, there exists X ⊆ M with |X| = n and |acl(X)| ≥ a′_{n}.

Proof. As with the previous construction, one can find a_{i} ≥ a′_{i} and a function f satisfying the conditions f_{1} - f_{5}. Take M constructed with these as data.

Let X be a set with n points and no relations defined on it. Then y(X) = n. Let Y be a structure with domain X ∪ {x_{1}, …, x_{a_{n+1}}} and such that the only relations are R_{i(n+1)}(X ∪{x_{i}}), for i = 1, …, a_{n+1}. Then |Y | = n+a_{n+1} and

y(Y) = n + a_{n+1} − a_{n+1} = n = y(X).

The structure Y is in C. In fact, if Y′ ⊂ X and Y′ ⊉ X then y(Y′) = |Y′| ≥ f(|Y′|). If Y′ ⊇ X then y(Y′) = n ≥ f(n + a_{n+1}) ≥ f(|Y′|).

By the properties of M, we can find a structure Z, self-sufficient in M and isomorphic to Y. Let X′ be the copy of X inside Z. Exactly as before, one shows that acl(X′) = Z. □

References

[Ca90] P. J. Cameron. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge, 1990.

[CK90] C. C. Chang and H. J. Keisler. Model Theory. North-Holland, Amsterdam, 1990. Third edition.

[CHL85] G. Cherlin, L. Harrington, A. H. Lachlan, ℵ_{0}-categorical, ℵ_{0}-stable structures, Annals Pure Appl. Logic 28 (1985), 103–135.

[Ev94] David M. Evans. Examples of ℵ_{0}-categorical structures, in Automorphisms of First-Order Structures, R.Kaye and D. Macpherson eds. Oxford University Press, Oxford, 1994.

[Fr53] R.Fraïssé. Sur certains relations qui généralisent l’ordre des nombres rationnels. C. R. Acad. Sci. Paris, 237:540-542, 1953.

[Ev00] David M. Evans. ℵ_{0}-categorical structures with a predimension, to appear in Annals of Pure and Applied Logic, Preprint, 2000.

[Fr54] R.Fraïssé. Sur l’extension aux relations de quelques propriétés des ordres. Ann. Sci. École Norm. Sup., 71:363-388, 1954.

[Ho93] W.Hodges. Model Theory. Cambridge University Press, Cambridge, 1993.

[Hr88] Ehud Hrushovski. A stable ℵ_{0}-categorical pseudoplane. Unpublished notes, 1988.

[Hr93] Ehud Hrushovski. A new strongly minimal set. Annals of Pure and Applied Logic., 62:147-166, 1993.

[Hr97] Ehud Hrushovski. Simplicity and the Lascar group, Preprint, 1997.

[KL92] D.W.Kueker and M.C.Laskowski. On generic structures. Notre Dame Journal of Formal Logic. 33:175-183, 1992.

[Ma86] H.D.Macpherson. Groups of automorphisms of ℵ_{0}-categorical structures. Quarterly J. Math. Oxford., 37:449-465, 1986.

[Pa95] M.E.Pantano. Algebraic closure in ℵ_{0}-categorical structures. PhD Thesis, UEA, Norwich, 1995.

[St92] P.W.Steitz. Upper bounds for growth in the Ryll-Nardzewski function of an ω-categorical, ω-stable theory. Isr. J. Math. 77:335-343, 1992.

[Wa94] F.O.Wagner. Relational Structures and Dimensions, in Automorphisms of First-Order Structures, R.Kaye and D. Macpherson eds. Oxford University Press, Oxford, 1994.

Authors’ address: School of Mathematics, UEA, Norwich NR4 7TJ, England

e-mail: d.evans@uea.ac.uk

11 June, 2001.