2.1 Permutation group notation

For a set $X$ , we write $\mathrm {Sym}(X)$ for the group of all permutations of $X$ . We say that a group $G$ is a permutation group $G\leq \mathrm {Sym}(X)$ for some set $X$ . Note that in this case the set $X$ is unique, and we call it the domain of $G$ , denoted by $\mathrm {Dom}(G)$ . The cardinality of $\mathrm {Dom}(G)$ is called the degree of $G$ . We say that two permutation groups $G$ and $H$ are isomorphic as permutation groups if there is bijection $e\colon \mathrm {Dom}(X)\rightarrow \mathrm {Dom}(H)$ such that $H=eGe^{-1}=\{e^{-1}ge: g\in G\}$ . All groups appearing in this article will be permutation groups, and when we say that two permutation groups are isomorphic we always mean that they are isomorphic as permutation groups.

Assume that $G\leq \mathrm {Sym}(X)$ is a permutation group, and $Y\subset X$ . We introduce the following notation:

• • $G_{Y}$ denotes the pointwise stabilizer of $Y$ , that is,

  $$ \begin{align*}G_Y=\{g\in G\colon\forall y\in Y(g(y)=y)\}.\end{align*} $$

• • $G_{\{Y\}}$ denotes the setwise stabilizer of $Y$ , that is,

  $$ \begin{align*}G_{\{Y\}}=\{g\in G\colon\forall y\in Y(g(y)\in Y)\}.\end{align*} $$

• • $G|_Y$ denotes the restriction of $G$ to $Y$ , that is,

  $$ \begin{align*}G|_Y=\{h|_Y\colon h\in G\},\end{align*} $$
  provided that $Y$ is invariant under $G$ .

• • $G_{(Y)}:=G_{\{Y\}}|_Y=G_{\{X\setminus Y\}}|_Y$ .

• • $G_{((Y))}:=G_{\mathrm {Dom}(G)\setminus Y}|_Y$ .

If $Y$ is finite, say $Y=\{x_1,\dots ,x_n\}$ , then we simply $G_{x_1,\dots ,x_n}$ for $G_Y$ .

Every permutation group $G\leq \mathrm {Sym}(X)$ is equipped with a topology called the topology of pointwise convergence. This topology is defined to be the subspace topology of the product space $X^X$ where $X$ is equipped with the discrete topology. We say that a permutation group is closed if it is closed in the topology of pointwise convergence. Equivalently, a group $G\leq \mathrm {Sym}(X)$ is closed if the following holds: for all $g\in \mathrm {Sym}(X)$ , if for every finite $F\subset X$ there exists $g'\in G$ such that $g'|_F=g|_F$ then $g\in G$ .

Let us assume that $E$ is an equivalence relation on some set $X$ . Then for an element $x\in X$ we write $[x]_E$ for the unique $E$ class that contains $E$ . Note that in this case $[x]_E=[y]_E$ holds if and only if $(x,y)\in E$ . We denote by $X/E$ the set of $E$ classes on $X$ , i.e., $X/E=\{[x]_E: x\in X\}$ . If $G\leq \mathrm {Sym}(X)$ is a group then we say that $E$ is a congruence of $G$ if $E$ is preserved by every element of $G$ , that is, for all $x,y\in X$ and $g\in G$ we have $(x,y)\in E$ if and only if $(g(x),g(y))\in E$ . If $E$ is a congruence of $G$ then there is a natural homomorphism $G\rightarrow \mathrm {Sym}(X/E)$ defined by $g\mapsto g/E$ where $g/E: [x]_E\mapsto [g(x)]_E$ . We write $G/E$ for the image of this homomorphism, i.e., $G/E=\{g/E: g\in G\}$ .

2.2 Orbit growth functions

Let $G\leq \mathrm {Sym}(X)$ be a permutation group, and let $n\in \omega $ . Then we introduce the following notation:

• • $\mathcal {O}_n(G)$ denotes the set of $n$ -orbits of $G$ , i.e., the set of orbits of the coordinate-wise action of $G$ on $X^n$ ;

• • for $a\in X^n$ we denote by $o_G(a)$ the orbit of the tuple $a$ , i.e., the unique $n$ -orbit of $G$ containing $a$ ;

• • for $a,b\in X^n$ we write $a\approx _G b$ if $o_G(a)=o_G(b)$ ;

• • $o_n(G)$ denotes the number of $n$ -orbits of $G$ , i.e., $o_n(G)=|\mathcal {O}_n(G)|$ ;

• • $\ell _n(G)$ denotes the number of injective $n$ -orbits of $G$ , i.e., the number of those $n$ -orbits of $G$ which contain tuples with pairwise different entries;

• • $u_n(G)$ denotes the number of orbits of $n$ -subsets of $G$ , i.e., the number of orbits of the natural action $G\curvearrowright {X\choose n}=\{Y\subset X\colon |Y|=n \}$ .

A permutation group is called oligomorphic if and only if $o_n(G)$ is finite for all $n\in \omega $ . By Remark 2.1 it follows that the oligomorphicity of a group $G$ is also equivalent to $u_n(G)$ (or $\ell _n(G)$ ) being finite for all $n\in \omega $ . We call the sequence $(\ell _n(G))_{n\in \omega }$ the labelled growth profile of $G$ , and $(u_n(G))_{n\in \omega }$ the unlabelled growth profile of $G$ . The orbit growth functions $\ell _n(\cdot )$ and $u_n(\cdot )$ are introduced and discussed in general in [Reference Cameron31, Reference Cameron32]. Note that at some places in the literature the sequences $o_n,\ell _n$ , and $u_n$ are denoted by $F_n^*,F_n$ , and $f_n$ , respectively. In this article we are mostly concerned with the unlabelled growth profile of permutation groups.

Let $G\leq \mathrm {Sym}(X)$ be a permutation group, and let $S\subset X$ . Then we write $\mathrm {acl}_G(X)$ for the union of finite $G$ -orbits of elements contained in $X$ .Footnote ¹ Note that if $X$ is finite and $G$ is oligomorphic then $\mathrm {acl}_G(X)$ is also finite.

2.3 Automorphisms of structures

In this article we denote structures by Fraktur letters $\mathfrak {A},\mathfrak {B},\mathfrak {C},\dots $ (sometimes with subscripts or other diacritics), and we write $A,B,C,\dots $ for the corresponding domain set. The signature of a structure $\mathfrak {A}$ is denoted by $\Sigma (\mathfrak {A})$ . For a structure $\mathfrak {A}$ , we write $\mathrm {Age}(\mathfrak {A})$ (called the age of $\mathfrak {A}$ ) for the class of all finite structures which embed into $\mathfrak {A}$ . We write $\mathrm {Aut}(\mathfrak {A})$ for the automorphism group of a structure $\mathfrak {A}$ . It is easy to see that the automorphism group of every structure is closed. Conversely, every closed permutation group is the automorphism group of some structure. In this article every structure is assumed to be countable, unless otherwise mentioned. We also assume for convenience that all structures in our discussions have a purely relational signature.Footnote ²

We are considering the following two notions of equivalence on first-order structures.

We say that a countable structure $\mathfrak {A}$ is $\omega $ -categorical if every countable model of the first-order theory of $\mathfrak {A}$ is isomorphic to $\mathfrak {A}$ . By the theorem of Engeler, Ryll-Nardzewski, and Svenonius, we know that a countable structure $\mathfrak {A}$ is $\omega $ -categorical if and only if $\mathrm {Aut}(\mathfrak {A})$ is oligomorphic (see for instance [Reference Hodges36, Theorem 7.3.1]). The connection between $\omega $ -categorical structures and their automorphism groups is summarized in the following theorem.

Theorem 2.4(3) tells us that in order to classify some class $\mathscr {C}$ of $\omega $ -categorical structures which is closed under bidefinability, it is enough to classify the automorphism groups of structures in $\mathscr {C}$ up to isomorphism.

In this article we use the following notational conventions: we use mathcal letters ( $\mathcal {H},\mathcal {S},\mathcal {F}$ ) for classes of permutations groups, and mathscr letters ( $\mathscr {H},\mathscr {S},\mathscr {F}$ ) for the corresponding structures, (for instance we write $\mathscr {C}$ for the class of all structures with automorphism groups in $\mathcal {C}$ ). If all groups in $\mathcal {C}$ are closed and then we have $\mathcal {C}=\{\mathrm {Aut}(\mathfrak {A}): \mathfrak {A}\in \mathscr {C}\}$ .

2.4 Direct products and disjoint unions

Let $\{X_i\colon i\in I\}$ be a family of pairwise disjoint sets, and for each $i\in I$ let $G_i\leq \mathrm {Sym}(X_i)$ be a permutation group. Then we define the direct product of the permutation groups $G_i$ , denoted by $\prod _{i\in I}G_i$ , to be the set of all permutations of $X:=\bigcup \{X_i\colon i\in I\}$ which can be written as $\bigcup \{f(i)\colon i\in I\}$ , for some $f\colon I\to \prod _{i\in I}G_i$ that satisfies $f(i)\in G_i$ for all $i\in I$ . In this case $\prod _{i\in I}G_i$ as a group is also the usual direct product of the groups $G_i\colon i\in I$ . It is clear from the definition that direct products of closed groups are closed.

Direct products of groups correspond to disjoint unions of structures in the following sense.

It is easy to see that if $(\mathfrak {A}_i)_{i\in I}$ are as above then $\mathrm {Aut}(\biguplus _{i=1}^n\mathfrak {A}_i)=\prod _{i\in I}\mathrm {Aut}(\mathfrak {A}_i)$ . It is also clear that finite unions of $\omega $ -categorical structures are $\omega $ -categorical which in turn implies that oligomorphic groups are closed under taking finite direct products.

2.5 Wreath products

If $G\leq \mathrm {Sym}(X)$ is a permutation group, and $S$ is a set then we define the power $G^S$ to be $\prod _{s\in S}G_s$ where $G_s:=\{(g,s)\colon g\in G\}$ and $(g,s)(g',s)=(gg',s)$ . This makes sense since the sets $\mathrm {Dom}(G_i)=X\times \{i\}$ are pairwise disjoint. Then $\mathrm {Dom}(G^S)=X\times S$ , and since all $G_i$ are isomorphic to $G$ it follows that $G^S$ is isomorphic to the power $G^{|S|}$ in the usual group theoretical sense.

Now let $H\leq \mathrm {Sym}(Y)$ be another permutation group. Then we define wreath product of the groups $G$ and $H$ , denoted by $G\wr H$ , as follows. The domain set of $G\wr H$ is $X\times Y$ and a permutation $\sigma \in \mathrm {Sym}(X\times Y)$ is contained in $G\wr H$ if and only if there exist $\beta \in H$ and $\alpha _y\in G$ such that $\sigma (x,y)=(\alpha _y(x),\beta (y))$ . Note that in this case we have a natural surjective homomorphism $\phi $ from $G\wr H$ to $H$ by mapping every $\sigma $ to its action of the second coordinates. The kernel of this homomorphism is exactly the power $G^Y$ , as defined above. Moreover, the map $\iota \colon \beta \mapsto ((x,y)\mapsto (x,\beta (y))$ splits the homomorphism $\phi $ , that is, $\phi \circ \iota =\mathrm {id}(Y)$ . This implies that $G\wr H$ can be written as a semidirect product $G^Y\rtimes e(H)$ .

We can also define wreath products of structures as follows.

The correspondence between wreath products of groups and wreath products of structures is as follows. Let $\mathfrak {A}$ and $\mathfrak {B}$ be a structure as in Definition 2.6. Then we have $\mathrm {Aut}(\mathfrak {A}\wr \mathfrak {B})=\mathrm {Aut}(\mathfrak {A})\wr \mathrm {Aut}(\mathfrak {B})$ . This implies immediately that if $G$ and $H$ are closed then so is $G\wr H$ . Moreover, if $\mathfrak {A}$ and $\mathfrak {B}$ are $\omega $ -categorical then so is $\mathfrak {A}\wr \mathfrak {B}$ which implies that if $G$ and $H$ are oligomorphic groups then $G\wr H$ is also oligomorphic.

2.6 Covers of permutation groups

In this section we introduce the notion of covers of permutation groups which plays a crucial role in this article. This construction will allow us to decompose certain oligomorphic permutation groups into simpler parts from which the original group can be recovered. Our definition of covers is largely based on the ones introduced in [Reference Bodirsky and Bodor8, Reference Evans, Ivanov and Macpherson33, Reference Ivanov38, Reference Pastori48]. In some cases covers are considered for structures and in some other cases it is only considered for closed permutation groups (these are called permutation structures in [Reference Evans, Ivanov and Macpherson33, Reference Pastori48]). One important difference in our definition compared to the earlier ones is that we also define everything for general permutation groups without any closedness assumption. Although all permutation groups showing up during our constructions will be closed, this will sometimes not follow immediately from the definition, so we prefer this more general treatment.

To ease the notation in our later discussions we always consider covers satisfying conditions (a)–(c) above. This way every cover of some group $G^*$ is already specified by the group $G$ . Also, in this case we can (and we will) identify the fiber groups, binding groups, and pointwise binding groups with their action of the first coordinates. By condition (c) these groups are the same, not just isomorphic, at elements coming from the same orbit. From this point on when we say $G$ is a cover of $G^*$ we always automatically assume that the triple $(G,G^*,\pi _2)$ satisfies conditions (a)–(c).

It follows from the discussion in [Reference Bodor24, Section 2.9] that if $G^*$ is transitive then every strongly split cover of $G^*$ is isomorphic to one given in Example 2.13.

Let us assume that $(G,G^*,\pi )$ is a cover with kernel $K$ , and let us assume that $\phi $ is some injective map from $G^*\rightarrow G$ such that $\mu _{\pi }\circ \phi =\mathrm {id}$ . Then $G$ can be written as $G=\ker (\mu )\phi (G^*)$ . Note that $\Phi $ is split if and only if $\phi $ can be chosen to be a group homomorphism. If $G$ is as in Example 2.13 then $\phi $ can be chosen such that $\phi (\sigma )=\hat {\sigma }$ where $\hat {\sigma }$ is defined to be the permutation which maps the $(f,a)$ to $(\sigma (f),a)$ for $(f,a)\in F\times \mathrm {Dom}(G^*)$ .

Now we introduce some further notation which will be useful in the discussion of the kernels of strongly split covers. Let $X$ and $F$ be sets, and let $G:= \mathrm {Sym}(F)\wr \mathrm {Sym}(X)$ . Then for all $a\in X:=\mathrm {Dom}(G)$ and $g\in G$ we define $\delta _a(g)\colon f\mapsto \pi _1(g(f,a))$ . Then clearly $g(f,a)=(\delta _a(f),\mu _{\pi _2}(a))$ . Let $H\triangleleft L\leq \mathrm {Sym}(F)$ . Then we define

$$ \begin{align*}\mathcal{K}^{L}_{H}=\{g\in G\cap \ker(\mu_{\pi_2})\colon \forall a,b\in X(\delta_a(g)\in L\wedge \delta_a(g)H=\delta_b(g)H)\}.\end{align*} $$

Then $\mathcal {K}^{L}_{H}$ always forms a subgroup of $G$ . Moreover, if $H$ and $L$ are closed (in particular if $F$ is finite) then so is $\mathcal {K}^{L}_{H}$ .

Notation 2.14. Let $S\subset \mathrm {Dom}(G^*)$ and $\sigma \in \mathrm {Sym}(F)$ . Then we denote by $\kappa (\sigma ,S)$ the unique permutation $\gamma \in G\cap \ker (\mu _{\pi _2})$ such that

$$\begin{align*}\delta_a(\kappa)= \begin{cases} \sigma &\text{if } a\in S\\ \mathrm{id}(F) &\text{otherwise.} \end{cases} \end{align*}$$

We also write $\kappa (\sigma ,a)$ for $\kappa (\sigma ,\{a\})$ .

2.7 Hereditarily cellular groups and structures

In this section we briefly recall the classification of hereditarily cellular structures mostly taken from [Reference Bodor24].

We first need to introduce a couple of notations.

Note that the definition of the group $\mathcal {G}(H;N_0,\dots ,N_k)$ differs from the one given in [Reference Bodor24], however the equivalence of the two definitions follows from the discussion in Section 3 in the aforementioned paper.

It is clear from the definition that

$$ \begin{align*}\mathcal{G}(N;N_0,\dots,N_k)=(N_0\wr (\mathrm{id}(\{0\}))\times \prod_{i=1}^k(N_i\wr \mathrm{Sym}(\omega)).\end{align*} $$

Now we are ready to give the definition of hereditarily cellular groups/structures.

Note that in [Reference Bodor24] the classes $\mathcal {H}_n$ is defined via $\omega $ -partitions, a notation introduced in [Reference Lachlan41], but again these definitions are known to be equivalent. We recall this equivalence below.

Next we recall a few important facts about hereditarily cellular groups that we will need in this article.

Theorem 2.21 can also be formulated in terms of structures. We say that a reduct $\mathfrak {B}$ of $\mathfrak {A}$ is of finite index if $|\mathrm {Aut}(\mathfrak {B}):\mathrm {Aut}(\mathfrak {A})|$ is finite.

By the results of [Reference Lachlan41] we know that a structure is hereditarily cellular if and only if it is $\omega $ -categorical and monadically stable.

The class of hereditarily cellular structures can also be described by their unlabelled growth profile. We say that a function $f\colon \omega \rightarrow \mathbb {R}$ is slower (faster) than exponential if for all $c>1$ we have $f(n)<c^n$ ( $f(n)>c^n$ ) if $n$ is large enough. Using these notions we have the following dichotomy result for the unlabelled growth profile of $\omega $ -categorical stable structures.

Next we recall a description of cellular structures using their unlabelled growth profile.

The following two theorems follow from the results of [Reference Braunfeld26, Reference Falque34].

For further discussion on the unlabelled growth profile of hereditarily cellular structures we refer the reader to [Reference Braunfeld26].

2.8 Homogeneous and finitely bounded structures

Next we recall some definitions and basic results concerning homogeneity and finite boundedness of structures.

An easy calculation on types shows that every homogeneous structure with a finite relational signature is $\omega $ -categorical; in fact if $\mathfrak {A}$ is homogeneous in a finite relational signature and the maximal arity of relations of $\mathfrak {A}$ is $m$ then $o_n(\mathfrak {A})\leq 2^{cn^{\max (2,m)}}$ for some $c>0$ .

It turns out that $m$ -homogenizable and in turn finitely homogenizable structures can also be characterized in a natural way in terms of their automorphism groups.

Lemma 2.35 can also be formulated for structures.

In the study of homogeneous structures we are particularly interested in the ones which are finitely bounded, i.e., whose age can be described by finitely many forbidden substructures. The precise definition is as follows.

We close this section by recalling some results about finite-index reducts of homogeneous structures.

As usual, Lemma 2.38 can also be formulated in terms of structures.

We know in fact that the second statement of Corollary 2.39 also holds for the class $\mathscr {B}$ .

Note that Lemma 2.40 together with 2.21 immediately implies that $\mathscr {H}\subset \mathscr {B}$ . In this article we will generalize this result to the class $\mathscr {S}$ by following a similar argument.

2.9 Highly set-transitive groups

We say that a permutation group $G$ is highly set-transitive if $u_n(G)=1$ , that is, $G$ acts transitively on the set of $n$ -subsets of $A$ for all $n\in \omega $ . In [Reference Cameron29] Cameron classified all closed highly set-transitive groups.

Theorem 2.41 immediately implies that the structure $(\mathbb {Q};<)$ has exactly five reducts up to interdefinability.

Next we recall how the automorphism groups of the structures $(\mathbb {Q};R)\colon R\in \{\mathrm {Betw},\mathrm {Cyc},\mathrm {Sep}\}$ can be generated over $\mathrm {Aut}(\mathbb {Q};<)$ .

The following statements are easy to check and well-known in the literature.

We will need the following two observations in our later discussion.

Proof. By Theorem 2.41 we can assume that $G=\mathrm {Aut}(\mathbb {Q};R)$ where $R\in \{<, \mathrm {Betw},\mathrm {Cyc},\mathrm {Sep},=\}$ . We can also assume without loss of generality that $s<t$ . Note that $\leftrightarrow $ cannot be contained in $G_{s,t}$ . This implies that $G_{s,t}=\mathrm {Aut}(\mathbb {Q};<)_{s,t}$ or $G_{s,t}=\mathrm {Aut}(\mathbb {Q};\mathrm {Cyc})_{s,t}$ .

In the first case it is clear that

$$ \begin{align*} G_{s,t}&=\mathrm{Aut}(\mathbb{Q};<)_{s,t}\\ &=((-\infty,s);<)\times ((s,t);<)\times ((t,\infty);<)\times \mathrm{id}(\{s,t\}) \\ &\simeq \mathrm{Aut}(\mathbb{Q};<)^3\times \mathrm{id}(\{0,1\}). \end{align*} $$

Now let us assume that $G_{s,t}=\mathrm {Aut}(\mathbb {Q};\mathrm {Cyc})_{s,t}$ . Note that $(s,t)=\{a: (s,a,t)\in \mathrm {Cyc}\}$ , thus this interval is preserved by $\mathrm {Aut}(\mathbb {Q};\mathrm {Cyc})$ . Moreover, for $a,b\in (s,t)$ we have $a<b$ if and only if $(s,a,b)\in \mathrm {Cyc}$ holds. Therefore, $(\mathrm {Aut}(\mathbb {Q};\mathrm {Cyc})_{s,t})|_{(s,t)}\subset \mathrm {Aut}((s,t);<)\simeq \mathrm {Aut}(\mathbb {Q};<)$ . On the other hand, we have

$$ \begin{align*}\mathrm{Aut}((s,t);<)\subset (\mathrm{Aut}(\mathbb{Q};<)_{\mathbb{Q}\setminus (s,t)})|_{(s,t)}\subset (\mathrm{Aut}(\mathbb{Q};<)_{s,t})|_{(s,t)}\subset (\mathrm{Aut}(\mathbb{Q};\mathrm{Cyc})_{s,t})|_{(s,t)},\end{align*} $$

therefore all of these groups are equal. This implies that

$$ \begin{align*}\mathrm{Aut}(\mathbb{Q};\mathrm{Cyc})_{s,t}=\mathrm{Aut}((s,t))\times \mathrm{id}(\{s,t\})\times (\mathrm{Aut}(\mathbb{Q};\mathrm{Cyc})_{s,t})|_{\mathbb{Q}\setminus (s,t)}.\end{align*} $$

Let $\sigma $ be an automorphism of $(\mathbb {Q};\mathrm {Cyc})$ that maps $s$ to $t$ and $t$ to $s$ . Then $\sigma ((s,t))=\mathbb {Q}\setminus (s,t)$ . This implies that the restrictions of $\mathrm {Aut}(\mathbb {Q};\mathrm {Cyc})_{s,t}$ to $(s,t)$ and $\mathbb {Q}\setminus (s,t)$ are isomorphic. Therefore, we have

$$ \begin{align*} G_{s,t}&=\mathrm{Aut}(\mathbb{Q};\mathrm{Cyc})_{s,t}\\&=\mathrm{Aut}((s,t);<)\times \mathrm{id}(\{s,t\})\times (\mathrm{Aut}(\mathbb{Q};\mathrm{Cyc})_{s,t})|_{\mathbb{Q}\setminus (s,t)}\\&\simeq \mathrm{Aut}(\mathbb{Q};<)^2\times \mathrm{id}(\{0,1\}).\\[-34pt] \end{align*} $$