Ranks based on strong amalgamation Fraïssé classes

Abstract

In this paper, we introduce the notion of ${\textbf{K}}$-rank, where ${\textbf{K}}$ is a strong amalgamation Fraïssé class. Roughly speaking, the ${\textbf{K}}$-rank of a partial type is the number “copies” of ${\textbf{K}}$ that can be “independently coded” inside of the type. We study ${\textbf{K}}$-rank for specific examples of ${\textbf{K}}$, including linear orders, equivalence relations, and graphs. We discuss the relationship of ${\textbf{K}}$-rank to other ranks in model theory, including dp-rank and op-dimension (a notion coined by the first author and C. D. Hill in previous work).

1 Introduction

In model theory, there are many different notions of dimension and rank that are used to measure the complexity of partial types in first-order theories. Some of these notions of rank involve measuring the largest “size” of a certain combinatorial configuration that exists in the type. For example, the dp-rank of a partial type is the largest depth of an ICT-pattern in the type (see Definition 2.1). Ideally, one would like a general framework that simultaneously captures various combinatorial notions of rank together in a single unified notion.

In a modest step towards that goal, we introduce a novel class of ranks we call ${\textbf{K}}$-rank for a strong amalgamation Fraïssé class, ${\textbf{K}}$. The idea is to concretely codify the notion of a “combinatorial configuration” by using ${\textbf{K}}$-configurations (see Definition 4.1). Roughly speaking the ${\textbf{K}}$-rank of a partial type counts the maximum number of “copies” of ${\textbf{K}}$ that can be “independently coded” in the type. More formally, “coding” is captured by the notion of ${\textbf{K}}$-configuration and the number of “copies” is captured by iterative free superpositions (see Definition 3.8), which leads to the notion of ${\textbf{K}}$-rank (see Definition 6.1).

In some instances, ${\textbf{K}}$-rank does generalize known notions of model theoretic rank. For example, if ${\textbf{K}}$ is the class of finite linear orders, then ${\textbf{K}}$-rank (linear order rank) generalizes dp-rank in distal theories (see Example 6.10). This is a consequence of the fact that linear order rank generalizes op-dimension (see Definition 2.2) on theories without the independence property (i.e., NIP theories); see Proposition 6.9. The notion of op-dimension was first introduced by the first author and C. D. Hill in [6] and has since been utilized in other model theoretic studies; e.g., [16]. As another example, if ${\textbf{K}}$ is the class of all finite sets with a single equivalence relation, then ${\textbf{K}}$-rank is bounded by the dp-rank; see Proposition 6.12. Both dp-rank and op-dimension are additive [6, 11] (see Definition 6.3); we examine under what conditions, on both ${\textbf{K}}$ and the target theory, ${\textbf{K}}$-rank is additive. From this analysis on the specific class ${\textbf{K}}$ of all finite linear orders, we derive a result which may be of independent interest: We give a new characterization of NIP for certain theories based on the growth rate of ${\textbf{K}}$-rank; see Theorem 6.29.

The original idea for the “coding” part of this work comes from a paper by the first author and Hill [7], where they study a related notion called positive local combinatorial dividing lines. The requirements on the Fraïssé classes considered in that paper are more stringent; specifically, they are required to be indecomposable (see Section 1 of [7]). In the current paper, we do not make this assumption. The notion of “coding” in this manner is also related to the phenomenon of non-collapsing generalized indiscernibles, studied by the first author, Hill, and L. Scow in [8]; a detailed explanation of this relationship may be found in Section 3 of [7]. When building generalized indiscernibles indexed by a class ${\textbf{K}}$, one needs to assume ${\textbf{K}}$ has the Ramsey property. However, certain useful uniformity aspects of indiscernibility may still exist in the absence of the Ramsey property. First, we develop a “pseudo-indiscerniblity” when the index class is “nice” (see Proposition 4.14 and Proposition 4.15). We then utilize this in type-counting arguments (e.g., Proposition 6.20).

This paper is organized as follows: In Sect. 2, we introduce the notation used in the paper and cover some basic definitions. In Sect. 3, we discuss the relevant concepts surrounding strong amalgamation Fraïssé classes. Primarily, we discuss the notion of free superposition, which formalizes the idea of “independent copies” of a Fraïssé class. In Sect. 4, we study the notion of configurations, which formalizes the idea of “coding” a Fraïssé class into a partial type. In Sect. 5, we connect the work in this paper back to the dividing lines considered in [7]. In particular, we discuss an interesting generalization of a few results from that paper. In Sect. 6, we define and examine ${\textbf{K}}$-ranks for various strong amalgamation Fraïssé classes, ${\textbf{K}}$. In Sect. 6.1, we study ${\textbf{K}}$-rank where ${\textbf{K}}$ is the class of all finite linear orders, in Sect. 6.2, we study ${\textbf{K}}$-rank where ${\textbf{K}}$ is the class of all finite sets with a single equivalence relation, and in Sect. 6.3, we study ${\textbf{K}}$-rank where ${\textbf{K}}$ is the class of all finite graphs. We study each of these ${\textbf{K}}$-ranks for types in the theory of the random graph in Sect. 6.4 and, in Sect. 6.5, we explore the additivity of some ranks in theories without the independence property. Finally, in Sect. 7, we discuss some interesting open problems.

2 Preliminaries

Let L be a first-order language. By the signature of L, denoted $\textrm{sig} (L)$, we mean the set of constant symbols, function symbols, and relation symbols used in L. We say L is finite relational if $\textrm{sig} (L)$ is finite and consists only of relation symbols. For a relation symbol $R \in \textrm{sig} (L)$, we denote the arity of R by $\textrm{arity} (R)$. If M is an L-structure and $A \subseteq M$, we let L(A) denote the language that expands L by adding constant symbols to the signature for each $a \in A$. Abusing notation, also let L(A) also denote the set of L(A)-formulas. For languages L and $L_0$, we say $L_0$ is a reduct of L if $\textrm{sig} (L_0) \subseteq \textrm{sig} (L)$. If M is an L-structure and $L_0$ is a reduct of L, let $M |_{L_0}$ denote the reduct of M to $L_0$. If M and N are L-structures, write $M \cong _L N$ to mean that M and N are isomorphic as L-structures (where we drop the L if it is clear).

In this paper, we will often be working with two first-order theories in different languages simultaneously, the “index” theory and the “target” theory. Typically, the index theory will be the Fraïssé limit of a strong amalgamation Fraïssé class (see Definition 3.1) in a finite relational language and the target theory will be an arbitrary complete first-order theory in an arbitrary language.

On the target side, suppose that T is a complete first-order theory in a language L. We use ${\mathfrak {C}}$ to denote the monster model of T; in this paper, it suffices to take ${\mathfrak {C}}$ to be any model of T that is at least $\aleph _1$-saturated. We will also consider partial types $\pi ({\overline{y}} )$, which are consistent collections of L(A)-formulas with free variables ${\overline{y}}$ for some $A \subseteq {\mathfrak {C}}$. In this paper, we only consider such partial types over a small A (i.e., A is smaller than the saturation of ${\mathfrak {C}}$). For a partial type $\pi$ and M a substructure of ${\mathfrak {C}}$, let $\pi (M)$ denote the set of all realizations of $\pi$ from M. If $\varphi$ is a formula and P is some property, then we write $\varphi ^{\text {iff } P}$ to denote the formula $\varphi$ if P is true and $\lnot \varphi$ if P is false. If $t < 2$, we will write $\varphi ^t$ to denote $\varphi ^{\text {iff } t = 1}$.

For the following two definitions, let T be a complete, first-order theory in a language L, let ${\mathfrak {C}}$ be a monster model of T, and let $\pi ({\overline{y}} )$ be a partial type. We define two notions of rank that we will consider in this paper, dp-rank and op-dimension. For simplicity of presentation, we will only consider $\omega$-valued dp-ranks and op-dimensions (generally, these can be defined to be ordinal-valued).

Definition 2.1

Let $m < \omega$ and $\beta$ be an ordinal. We say that $\pi$ has an ICT-pattern of depth m and length $\beta$ if there exist $L({\mathfrak {C}} )$-formulas $\varphi _i({\overline{y}} , {\overline{z}} _i)$ for $i < m$ and ${\overline{c}} _{i,j} \in {\mathfrak {C}} ^{|{\overline{z}} _i|}$ for $i < m$ and $j < \beta$ such that, for all $g : m \rightarrow \beta$, the partial type

$$\begin{aligned} \pi ({\overline{y}} ) \cup \left\{ \varphi _i({\overline{y}} , {\overline{c}} _{i,j})^{\text {iff } g(i) = j} : i< m, j < \beta \right\} \end{aligned}$$

is consistent. The dp-rank of $\pi$ is the maximum $m < \omega$ such that $\pi$ has an ICT-pattern of depth m and length $\omega$. We denote the dp-rank of $\pi$ by $\textrm{dpRk} (\pi )$.

Definition 2.2

Let $m < \omega$ and $\beta$ be an ordinal. We say that $\pi$ has an IRD-pattern of depth m and length $\beta$ if there exist $L({\mathfrak {C}} )$-formulas $\varphi _i({\overline{y}} , {\overline{z}} _i)$ for $i < m$ and ${\overline{c}} _{i,j} \in {\mathfrak {C}} ^{|{\overline{z}} _i|}$ for $i < m$ and $j < \beta$ such that, for all $g : m \rightarrow \beta$, the partial type

$$\begin{aligned} \pi ({\overline{y}} ) \cup \{ \varphi _i({\overline{y}} , {\overline{c}} _{i,j})^{\text {iff } g(i)< j} : i< m, j < \beta \} \end{aligned}$$

is consistent. The op-dimension of $\pi$ is the maximum $m < \omega$ such that $\pi$ has an IRD-pattern of depth m and length $\omega$. We denote the op-dimension of $\pi$ by $\textrm{opDim} (\pi )$.

In this paper, we attempt to generalize “combinatorial patterns,” like ICT-patterns or IRD-patterns, in order to define a generalized notion of rank. To do this, we view the patterns as coming from an “index” theory.

On the index side, let $L_0$ be a finite relational language and let ${\textbf{K}}$ be a class of finite $L_0$-structures closed under isomorphism.

• We say that ${\textbf{K}}$ has the hereditary property if, for all $B \in {\textbf{K}}$ and $A \subseteq B$, $A \in {\textbf{K}}$.

• We say that ${\textbf{K}}$ has the joint embedding property if, for all $A_0, A_1 \in {\textbf{K}}$, there exist $B \in {\textbf{K}}$ and embeddings $f_t : A_t \rightarrow B$ for each $t < 2$.

• We say that ${\textbf{K}}$ has the amalgamation property if, for all $A, B_0, B_1 \in {\textbf{K}}$ and embeddings $f_t : A \rightarrow B_t$ for each $t < 2$, there exist $C \in {\textbf{K}}$ and embeddings $g_t : B_t \rightarrow C$ such that $g_0 \circ f_0 = g_1 \circ f_1$.

• We say that ${\textbf{K}}$ is a Fraïssé class if it has the hereditary property, the joint embedding property, and the amalgamation property.

The Fraïssé limit of a Fraïssé class ${\textbf{K}}$ is the unique (up to isomorphism) countable $L_0$-structure $\Gamma$ such that $\Gamma$ is ultrahomogeneous and ${\textbf{K}}$ is the class of all finite structures embeddable into $\Gamma$ (see Theorem 6.1.2 of [9]). Since $L_0$ is a finite relational language, the theory of the Fraïssé limit of ${\textbf{K}}$ is $\aleph _0$-categorical and eliminates quantifiers (see Theorem 6.4.1 of [9]). Abusing terminology, we will typically say that ${\textbf{K}}$ has a certain property if its Fraïssé limit does. This allows us to avoid writing the phrase “whose Fraïssé limit satisfies” throughout the paper.

In this paper, we will be interested in “coloring properties” of the limits of Fraïssé classes. The following two definitions can be found in, for example, [5]; here, we have rephrased them to be about colorings of the Fraïssé limit.

Definition 2.3

Let ${\textbf{K}}$ be a Fraïssé class with Fraïssé limit $\Gamma$. We say that ${\textbf{K}}$ is indivisible if, for all $k < \omega$ and $c : \Gamma \rightarrow k$, there exist $\Gamma ' \subseteq \Gamma$ with $\Gamma ' \cong \Gamma$ and $i < k$ such that

$$\begin{aligned} c(\Gamma ') = \{ i \}. \end{aligned}$$

Definition 2.4

Let ${\textbf{K}}$ be a Fraïssé class with Fraïssé limit $\Gamma$. We say that ${\textbf{K}}$ is age indivisible if, for all $k < \omega$, all $c : \Gamma \rightarrow k$, and all $A \in {\textbf{K}}$, there exist an embedding $f : A \rightarrow \Gamma$ and $i < k$ such that $c(f(A)) = \{ i \}$.

It is clear that indivisibility implies age indivisibility.

In the next section, we will study these coloring properties in the context of strong amalgamation Fraïssé classes.

3 Strong Amalgamation Fraïssé classes

In this section, we define the notion of strong amalgamation Fraïssé class. We then explore the free superposition and its relationship to some properties of strong amalgamation Fraïssé classes.

Fix $L_0$ a finite relational language and let ${\textbf{K}}$ be a Fraïssé class in $L_0$. We can strengthen the amalgamation property as follows: We say ${\textbf{K}}$ satisfies the strong amalgamation property if, for all $A, B_0, B_1 \in {\textbf{K}}$ and embeddings $f_t : A \rightarrow B_t$ for each $t < 2$, there exist $C \in {\textbf{K}}$ and embeddings $g_t : B_t \rightarrow C$ such that $g_0 \circ f_0 = g_1 \circ f_1$ and $g_0(B_0) \cap g_1(B_1) = g_0(f_0(A))$. Since the language is relational, we may assume that the empty structure is in ${\textbf{K}}$, so we obtain a “strong” joint embedding property from the strong amalgamation property. Moreover, if $\Gamma$ is the Fraïssé limit of ${\textbf{K}}$, then ${\textbf{K}}$ has the strong amalgamation property if and only if, for all $A \subseteq \Gamma$, $\textrm{acl} (A) = A$; see (2.15) of [3].

Definition 3.1

Let ${\textbf{K}}$ be a Fraïssé class in a finite relational language. We say that ${\textbf{K}}$ is a strong amalgamation Fraïssé class if it satisfies the strong amalgamation property.

For each $t < 2$, let ${\textbf{K}} _t$ be a class of finite $L_t$-structures, where $L_t$ is a finite relational language. Let $L_2$ be the language whose signature is the disjoint union of the signatures of $L_0$ and $L_1$ and define the free superposition of ${\textbf{K}} _0$ and ${\textbf{K}} _1$, denoted ${\textbf{K}} _0 *{\textbf{K}} _1$, as the class of all finite $L_2$-structures A such that $A |_{L_t} \in {\textbf{K}} _t$ for each $t < 2$.

Remark 3.2

Suppose that $A \in {\textbf{K}} _0$, $B \in {\textbf{K}} _1$, and $f : A \rightarrow B$ is a bijection. Then, we can “glue” A and B together via f to make an element of ${\textbf{K}} _0 *{\textbf{K}} _1$. Formally, let C be the $L_2$-structure with universe A such that, for all $R \in \textrm{sig} (L_2)$ and ${\overline{a}} \in A^{\textrm{arity} (R)}$,

• if $R \in \textrm{sig} (L_0)$, then $C \models R({\overline{a}} ) \Longleftrightarrow A \models R({\overline{a}} )$, and

• if $R \in \textrm{sig} (L_1)$, then $C \models R({\overline{a}} ) \Longleftrightarrow B \models R(f({\overline{a}} ))$.

Then, clearly $C \in {\textbf{K}} _0 *{\textbf{K}} _1$. Indeed, $C |_{L_0} = A$ and $C |_{L_1} \cong _{L_1} B$.

Proposition 3.3

(Lemma 3.22 of [2]) If ${\textbf{K}} _0$ and ${\textbf{K}} _1$ are strong amalgamation Fraïssé classes, then ${\textbf{K}} _0 *{\textbf{K}} _1$ is a strong amalgamation Fraïssé class.

Although the result is known, we give a proof here, as it will help in the proof of Proposition 3.16 below.

Proof

We begin by exhibiting the strong amalgamation property. Fix structures $A, B_0, B_1 \in {\textbf{K}} _0 *{\textbf{K}} _1$ and fix $L_2$-embeddings $f_0 : A \rightarrow B_0$ and $f_1 : A \rightarrow B_1$. In particular, $f_0$ and $f_1$ are both $L_s$-embeddings for each $s < 2$. By the strong amalgamation property of ${\textbf{K}} _s$, there exist $C_s \in {\textbf{K}} _s$ and $L_s$-embeddings $g^s_t : B_t \rightarrow C_s$ for $t < 2$ such that $g^s_0 \circ f_0 = g^s_1 \circ f_1$ and $g^s_0(B_0) \cap g^s_1(B_1) = g^s_0(f_0(A))$. By embedding into a larger structure and using the hereditary property, we may assume that $|C_0| = |C_1|$. There exists a bijection $h : C_0 \rightarrow C_1$ such that the following diagram commutes:

As in Remark 3.2, endow $C_0$ with an $L_2$-structure via h and call it $C_2$.

To exhibit the hereditary property, fix $B \in {\textbf{K}} _0 *{\textbf{K}} _1$ and let $A \subseteq B$. In particular, $A |_{L_0}$ is a $L_0$-substructure of $B |_{L_0}$, so $A |_{L_0} \in {\textbf{K}} _0$. Similarly, $A |_{L_1} \in {\textbf{K}} _1$. Thus, $A \in {\textbf{K}} _0 *{\textbf{K}} _1$. $\square$

Example 3.4

Note that the strong amalgamation property is necessary to conclude that the free superposition is even a Fraïssé class. For example, for each $t < 2$, let $L_t$ be the language with one unary predicate, $P_t$, and let ${\textbf{K}} _t$ be the class of all $L_t$-structures where at most one element satisfies $P_t$. This is clearly a Fraïssé class, but does not have strong amalgamation. On the other hand, ${\textbf{K}} _0 *{\textbf{K}} _1$ is not a Fraïssé class, as it fails joint embedding. Let $A_0 = \{ a_0, a_1 \}$ where $P_0(a_0)$ and $P_1(a_1)$ and let $A_1 = \{ a_2 \}$ where $P_0(a_2)$ and $P_1(a_2)$. Then, there exists no $B \in {\textbf{K}} _0 *{\textbf{K}} _1$ which embeds $A_0$ and $A_1$ simultaneously.

Definition 3.5

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in $L_0$, $A \in {\textbf{K}}$, and R a relation of $L_0$ with arity n.

• (1) We say R is symmetric on A if, for all $a \in {}^n A$ and all $\sigma \in S_n$, if $A \models R(a)$, then $A \models R(a \circ \sigma )$.

• (2) We say R is trichotomous on A if, for all $a \in {}^n A$ such that $a(i) \ne a(j)$ for all $i< j < n$, there exists exactly one $\sigma \in S_n$ such that $A \models R(a \circ \sigma )$.

• (3) We say R is reflexive on A if, for all $a \in {}^n A$ such that $a(i) = a(j)$ for all $i< j < n$, $A \models R(a)$.

• (4) We say R is irreflexive on A if, for all $a \in {}^n A$ such that $a(i) = a(j)$ for some $i< j < n$, $A \models \lnot R(a)$.

• (5) If $n = 2$, we say R is transitive if, for all $a, b, c \in A$, if $A \models R(a,b) \wedge R(b,c)$, then $A \models R(a,c)$.

We say A has one of the above properties if, for all $R \in \textrm{sig} (L_0)$, R has that property on A. We say ${\textbf{K}}$ has one of the above properties if, for all $A \in {\textbf{K}}$, A has that property.

Proposition 3.6

Each of the properties in Definition 3.5 is closed under free superposition.

Proof

Any witness to the failure of one of these properties in ${\textbf{K}} _0 *{\textbf{K}} _1$ reducts to a failure of the same property in either ${\textbf{K}} _0$ or ${\textbf{K}} _1$.

$\square$

Definition 3.7

We have a few strong amalgamation Fraïssé classes that we examine in particular in this paper.

• (1) (Sets) Let ${\textbf{S}}$ denote the class of all finite $L_0$-structures where $L_0$ has empty signature.

• (2) (Linear Orders) Let $\textbf{LO}$ denote the class of all finite $L_0$-structures that are trichotomous, irreflexive, and transitive, where $L_0$ is a language with one binary relation symbol.

• (3) (Equivalence Relations) Let ${\textbf{E}}$ denote the class of all finite $L_0$-structures that are symmetric, reflexive, and transitive, where $L_0$ is a language with one binary relation symbol.

• (4) (Graphs) Let ${\textbf{G}}$ denote the class of all finite $L_0$-structures that are symmetric and irreflexive, where $L_0$ is a language with one binary relation symbol.

• (5) (Hypergraphs) For $k \ge 2$, let ${\textbf{H}} _k$ denote the class of all finite $L_0$-structures that are symmetric and irreflexive, where $L_0$ is a language with one k-ary relation symbol. Clearly ${\textbf{G}} = {\textbf{H}} _2$.

• (6) (Tournaments) Let ${\textbf{T}}$ denote the class of all finite $L_0$-structures that are trichotomous and irreflexive, where $L_0$ is a language with one binary relation symbol.

Definition 3.8

Suppose ${\textbf{K}}$ is a strong amalgamation Fraïssé class and fix $n \ge 1$. Then, define ${\textbf{K}} ^{*n}$ recursively as follows:

• (1) ${\textbf{K}} ^{*0} = {\textbf{S}}$,

• (2) ${\textbf{K}} ^{*(n+1)} = {\textbf{K}} ^{*n} *{\textbf{K}}$.

Example 3.9

For any strong amalgamation Fraïssé class ${\textbf{K}}$, notice that

$$\begin{aligned} {\textbf{S}} *{\textbf{K}} = {\textbf{K}} *{\textbf{S}} = {\textbf{K}} . \end{aligned}$$

So, in particular, ${\textbf{K}} ^{*1} = {\textbf{K}}$ and ${\textbf{S}} ^{*n} = {\textbf{S}}$ for all $n \ge 1$.

Example 3.10

For all $n \ge 1$, $\textbf{LO} ^{*n}$ is the class of all finite sets with n linear orders.

Example 3.11

In any finite relational language $L_0$ where all relations are at least binary, the class of $L_0$-hypergraphs, ${\textbf{H}} _{L_0}$, is the set of all finite $L_0$-structures that are symmetric and irreflexive. By Proposition 3.6,

$$\begin{aligned} {\textbf{H}} _{L_0} = {\textbf{H}} _{k_0} *\dots *{\textbf{H}} _{k_{n-1}}, \end{aligned}$$

where $k_0 \le \dots \le k_{n-1}$ list all the arities (with repetition) of the relation symbols in $L_0$. By Proposition 3.3, ${\textbf{H}} _{L_0}$ is a strong amalgamation Fraïssé class.

In the remainder of this section, we will introduce tools that will be used to compute ${\textbf{K}}$-rank for specific strong amalgamation Fraïssé classes ${\textbf{K}}$ in Sect. 6. We use the following proposition to build substructures of Fraïssé limits that are isomorphic to the original limit.

Proposition 3.12

Suppose that $\Gamma$ is the Fraïssé limit of ${\textbf{K}}$ and $\Gamma ' \subseteq \Gamma$. If, for all $A, B \in {\textbf{K}}$ with $A \subseteq B$ and $|B \setminus A| = 1$ and for all embeddings $f : A \rightarrow \Gamma '$, there exists an embedding $g: B \rightarrow \Gamma '$ extending f, then $\Gamma ' \cong \Gamma$.

Proof

This follows from Lemma 6.1.4 of [9]. $\square$

The following definition is made in a general context, but we will mostly be interested in the case where $\Gamma$ is the Fraïssé limit of a strong amalgamation Fraïssé class ${\textbf{K}}$.

Definition 3.13

Let $\Gamma$ be a structure in any language, L. We say $\Gamma$ is (quantifier-free) definably self-similar if, for any finite $A \subseteq \Gamma$ and any complete, non-algebraic (quantifier-free) 1-L-type p over A, $p(\Gamma )$ is isomorphic to $\Gamma$.

Note that, when $\Gamma$ is the Fraïssé limit of a Fraïssé class in a finite relational language, by quantifier elimination, being quantifier-free definably self-similar is equivalent to being definably self-similar.

Lemma 3.14

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$ with Fraïssé limit $\Gamma$. Then, $\Gamma$ is definably self-similar if and only if, for all $B, B', C \in {\textbf{K}}$ such that $B \subseteq B'$ and $|B' \setminus B| = 1$, for all $A \subseteq C$ and p a complete, non-algebraic 1-$L_0$-type over A, for all embeddings $f : B \rightarrow p(C)$, there exist $C' \in {\textbf{K}}$ with $C' \supseteq C$ and an embedding $f' : B' \rightarrow p(C')$ extending f.

Proof

($\Rightarrow$): Assume that $\Gamma$ is definably self-similar. Fix B, $B'$, C, A, p, and f as in the lemma. Since $\Gamma$ is the Fraïssé limit of ${\textbf{K}}$, we may assume that $C \subseteq \Gamma$. Since $\Gamma$ is definably self-similar, $p(\Gamma ) \cong \Gamma$. By assumption, $f(B) \subseteq p(\Gamma )$. Since $p(\Gamma )$ is also the Fraïssé limit of ${\textbf{K}}$, there exists an embedding $f' : B' \rightarrow p(\Gamma )$ extending f. Let $C' = f'(B') \cup C$. This gives the desired extension.

($\Leftarrow$): Fix $A \subseteq \Gamma$ finite and p a complete, non-algebraic 1-$L_0$-type over A. We show that the hypothesis of Proposition 3.12 is satisfied for $p(\Gamma )$. Consider $B, B' \in {\textbf{K}}$ with $B \subseteq B'$ and $|B' \setminus B| = 1$ and suppose that $f : B \rightarrow p(\Gamma )$ is an embedding. Let $C = f(B) \cup A$, so f is an embedding of B into p(C). By assumption, there exists $C' \in {\textbf{K}}$ with $C' \supseteq C$ and an embedding $f' : B' \rightarrow p(C')$ extending f. Since $\Gamma$ is the Fraïssé limit of ${\textbf{K}}$, we may assume $C' \subseteq \Gamma$ and thus $f'$ embeds $B'$ into $p(\Gamma )$. $\square$

The preceding lemma gives us a characterization of when the Fraïssé limit of a Fraïssé class is definably self-similar in terms of the class. Thus, we will say that ${\textbf{K}}$ is definably self-similar if its Fraïssé limit is definably self-similar.

The next lemma is essentially the same as Theorem 2.6 of [14], but we include a proof here for completeness.

Lemma 3.15

Suppose that ${\textbf{K}}$ is a definably self-similar strong amalgamation Fraïssé class. Then, ${\textbf{K}}$ is indivisible.

Proof

Let $\Gamma$ be the Fraïssé limit of ${\textbf{K}}$, let $k < \omega$, and let $c : \Gamma \rightarrow k$. We find $\Gamma ' \subseteq \Gamma$ with $\Gamma ' \cong \Gamma$ and $i < k$ such that $c(\Gamma ') = \{ i \}$. We may assume $k = 2$. Suppose that $c^{-1}( \{ 0 \} ) \not \cong \Gamma$. Then, by the contrapositive of Proposition 3.12, there exist $A, B \in {\textbf{K}}$ with $A \subseteq B$ and $B = \{ b \} \cup A$, and $f: A \rightarrow c^{-1}( \{ 0 \} )$ an embedding that does not extend to an embedding of B into $c^{-1}( \{ 0 \} )$. Then, consider

$$\begin{aligned} \Gamma ' = \left\{ d \in \Gamma : \textrm{tp} _{L_0}(d,f(A)) = \textrm{tp} _{L_0}(b,A) \right\} . \end{aligned}$$

Since $\Gamma$ is definably self-similar, $\Gamma ' \cong \Gamma$. On the other hand, for any $d \in \Gamma '$, the function extending f to a function from B to $\Gamma$ by sending b to d is an embedding. Thus, $c(d) = 1$. In other words, $c(\Gamma ') = \{ 1 \}$. $\square$

In the next proposition, we show that being definably self-similar is closed under free superposition.

Proposition 3.16

Suppose that ${\textbf{K}} _0$ and ${\textbf{K}} _1$ are definably self-similar. Then, ${\textbf{K}} _0 *{\textbf{K}} _1$ is definably self-similar.

Proof

Let $L_0$ be the language of ${\textbf{K}} _0$, let $L_1$ be the language of ${\textbf{K}} _1$, and let $L_2$ be the language whose signature is the disjoint union of the signatures of $L_0$ and $L_1$, which serves as the language for ${\textbf{K}} _2 = {\textbf{K}} _0 *{\textbf{K}} _1$.

We use the characterization in Lemma 3.14. Fix $B, B', C \in {\textbf{K}} _2$ such that $B \subseteq B'$, fix $A \subseteq C$, fix p(x) a complete, non-algebraic 1-$L_2$-type over A, and fix an $L_2$-embedding $f : B \rightarrow p(C)$. In particular, for each $t < 2$, f is an $L_t$-embedding of B into $p |_{L_t}(C)$. For each $t < 2$, since ${\textbf{K}} _t$ is definably self-similar, there exist $C'_t \in {\textbf{K}} _t$ with $C |_{L_t} \subseteq C'_t$ and an $L_t$-embedding $f'_t : B' \rightarrow p |_{L_t}(C'_t)$. Using the hereditary property, we may assume that $|C'_0| = |C'_1|$. Then, as in the proof of Proposition 3.3, there exists a bijection g from $C'_0$ to $C'_1$ such that the following diagram commutes:

As in Remark 3.2, create the structure $C' \in {\textbf{K}} _2$ with universe $C'_0$ endowed with $L_2$-structure given by g. Then, it is not hard to show that $f'_0$ is an $L_2$-embedding of $B'$ into $p(C')$. $\square$

Example 3.17

The classes $\textbf{LO}$, ${\textbf{G}}$, and ${\textbf{T}}$ are definably self-similar. Moreover, for all $k \ge 2$, ${\textbf{H}} _k$ is definably self-similar. By Proposition 3.16, for all $n \ge 1$, $\textbf{LO} ^{*n}$, ${\textbf{G}} ^{*n}$, and ${\textbf{T}} ^{*n}$ are definably self-similar and, for all $k \ge 2$, ${\textbf{H}} _k^{*n}$ is definably self-similar. On the other hand, ${\textbf{E}}$ is not definably self-similar.

Proof

In the theory of dense linear orders, for any complete, non-algebraic 1-type p over a finite subset of ${\mathbb {Q}}$, $p({\mathbb {Q}})$ is an open interval, which is clearly isomorphic to ${\mathbb {Q}}$. Hence, $\textbf{LO}$ is definably self-similar.

Next, consider ${\textbf{H}} _k$ for some $k \ge 2$ in the language $L_0$ with one k-ary relation symbol, E. Fix $B, B', C \in {\textbf{H}} _k$ with $B \subseteq B'$, fix $A \subseteq C$, and fix p a complete, non-algebraic 1-$L_0$-type over A. Suppose that $f : B \rightarrow p(C)$ is an embedding and that $B' = B \cup \{ b' \}$. Create an $L_0$-structure $C'$ where $C' = C \cup \{ c' \}$ by setting, for all ${\overline{b}} \in B^{k-1}$,

$$\begin{aligned} C' \models E(c', f({\overline{b}} )) \Longleftrightarrow B' \models E(b', {\overline{b}} ), \end{aligned}$$

and, for all ${\overline{a}} \in A^{k-1}$,

$$\begin{aligned} C' \models E(c', {\overline{a}} ) \Longleftrightarrow E(x, {\overline{a}} ) \in p(x), \end{aligned}$$

and add no additional edges (except those necessary to create symmetry). Finally, extend f to $f'$ by setting $f'(b') = c'$. It is easy to check that $f'$ is an embedding from $B'$ into $p(C')$. A similar argument works for ${\textbf{T}}$, where the “direction” of each edge is determined by either $B'$ or p.

Finally, consider the class ${\textbf{E}}$ in the language $L_0$ with one binary relation symbol, E, and let $\Gamma$ be the Fraïssé limit of ${\textbf{E}}$. Fix $a \in \Gamma$ and let p(x) be the complete 1-$L_0$-type over $\{ a \}$ extending $x \ne a \wedge E(x,a)$. Clearly $p(\Gamma ) \not \cong \Gamma$. $\square$

The above proof for ${\textbf{H}} _k$ can be modified to show that, if ${\textbf{K}}$ has 3-amalgamation (see [10]), then ${\textbf{K}}$ is definably self-similar. On the other hand, $\textbf{LO}$ witnesses that the converse is false.

Although ${\textbf{E}}$ is not definably self-similar, we can analyze ${\textbf{E}} ^{*m}$ for $m \ge 1$. The following lemma aids in this analysis.

Lemma 3.18

For $m < \omega$, let $L_m$ be the language with m binary relation symbols $E_i$ for $i < m$. For any set I, we can put an $L_m$-structure on $I^{m+1}$ by setting, for all $i < m$ and all ${\overline{a}} , {\overline{b}} \in I^{m+1}$, $E_i({\overline{a}} , {\overline{b}} )$ if $a_i = b_i$. With this $L_m$-structure:

• (1) if I is finite, then $I^{m+1} \in {\textbf{E}} ^{*m}$; and

• (2) if I is countably infinite, then $I^{m+1}$ is isomorphic to the Fraïssé limit of ${\textbf{E}} ^{*m}$.

Proof

Trivial. $\square$

Example 3.19

Although ${\textbf{E}}$ is indivisible, for $m \ge 2$, ${\textbf{E}} ^{*m}$ is not indivisible.

Proof

It follows from the Pigeonhole Principle that ${\textbf{E}}$ is indivisible.

Fix $m \ge 2$ and let $\Gamma$ be the Fraïssé limit of ${\textbf{E}} ^{*m}$. By Lemma 3.18, we can suppose $\Gamma$ has universe $\omega ^{m+1}$. Consider the coloring $c : \Gamma \rightarrow 2$ given by

$$\begin{aligned} c({\overline{a}} ) = {\left\{ \begin{array}{ll} 0 &{} \text { if } a_0 < a_1, \\ 1 &{} \text { if } a_0 \ge a_1 \end{array}\right. }. \end{aligned}$$

Towards a contradiction, suppose there is $\Gamma ' \cong \Gamma$ with $c(\Gamma ') = \{ t \}$. For any ${\overline{a}} \in \Gamma '$, there are only finitely many $E_t$-classes in $\Gamma '$ that have non-empty intersection with the $E_{1-t}$-class of ${\overline{a}}$ in $\Gamma '$, a contradiction.

$\square$

To deal with ${\textbf{E}} ^{*m}$ in Sect. 6, we need a condition that is weaker than being definably self-similar, but which is still strong enough to run counting arguments. It turns out that age indivisibility is a sufficient condition for our purposes. By Lemma 3.15, if ${\textbf{K}}$ is definably self-similar, then ${\textbf{K}}$ is age indivisible.

Example 3.20

For all $m < \omega$, ${\textbf{E}} ^{*m}$ is age indivisible. In particular, age indivisibility is strictly weaker than being definably self-similar.

Proof

Let $\Gamma$ be the Fraïssé limit of ${\textbf{E}} ^{*m}$. By Lemma 3.18, we may assume that $\Gamma$ has universe $\omega ^{m+1}$. Let $c : \Gamma \rightarrow k$ be a coloring and let $A \in {\textbf{E}} ^{*m}$. Let $n = |A|$. By Corollary A.2, there exist $Y_0, \dots , Y_m \in \left( {\begin{array}{c}\omega \\ n\end{array}}\right)$ such that c is constant on $B = \prod _{i \le m} Y_i$. On the other hand, there is clearly an embedding $g : A \rightarrow B$.

Thus, c is constant on g(A). This shows that ${\textbf{E}} ^{*m}$ is age indivisible. $\square$

The property described in the following definition is mild, only requiring that any combination of relation symbols of the same arity that can happen, does happen. However, it provides a lower bound for the number of types in our type-counting arguments in Sect. 6.

Definition 3.21

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class. We say that ${\textbf{K}}$ is fully relational if, for all $n < \omega$, for all functions f from relation symbols in $L_0$ of arity n to 2, there exist $A \in {\textbf{K}}$ and ${\overline{a}} \in A^n$ such that $a_i \ne a_j$ for all $i< j < n$ and, for all relation symbols R in $L_0$ of arity n, $A \models R({\overline{a}} )$ if and only if $f(R) = 1$.

Note that, for a language with a single n-ary relation symbol, being fully relational means that there is one (non-repeating) n-tuple where the relation holds and one where it fails.

Example 3.22

Notice that ${\textbf{S}}$, $\textbf{LO}$, ${\textbf{E}}$, ${\textbf{G}}$, ${\textbf{T}}$, and ${\textbf{H}} _k$ for all $k \ge 2$ are all fully relational.

Proposition 3.23

Suppose that ${\textbf{K}} _0$ and ${\textbf{K}} _1$ are fully relational. Then, ${\textbf{K}} _0 *{\textbf{K}} _1$ is fully relational.

Proof

For each $t < 2$, let ${\textbf{K}} _t$ be a strong amalgamation Fraïssé class in the finite relational language $L_t$ that is fully relational. Let ${\textbf{K}} _2 = {\textbf{K}} _0 *{\textbf{K}} _1$, where ${\textbf{K}} _2$ is in the language $L_2$ whose signature is the disjoint union of the signatures of $L_0$ and $L_1$. Fix $n < \omega$ and, for $t < 3$, let $\textrm{sig} _n(L_t)$ denote the set of all relation symbols of $L_t$ of arity n. Let $f : \textrm{sig} _n(L_2) \rightarrow 2$. For each $t < 2$, since ${\textbf{K}} _t$ is fully relational, there exist $A_t \in {\textbf{K}} _t$ and ${\overline{a}} ^t \in A_t^n$ such that $a_i^t \ne a_j^t$ for all $i< j < n$ and, for all $R \in \textrm{sig} _n(L_t)$, $A_t \models R({\overline{a}} ^t)$ if and only if $f(R) = 1$. By the hereditary property, we may assume that $A_t = \{ a_i^t : i < n \}$. Then, let A be the $L_2$-structure with universe $A_0$ induced by the bijection $a_i^0 \mapsto a_i^1$ as in Remark 3.2. Thus, $A \in {\textbf{K}} _2$ and, for all $R \in \textrm{sig} _n(L_2)$, $A \models R({\overline{a}} _0)$ if and only if $f(R) = 1$. $\square$

4 Configurations

Throughout this section, let L be any language, let T be a complete L-theory, and let ${\mathfrak {C}}$ be a monster model of T.

The following definition will be used to capture what we mean by “coding” the class ${\textbf{K}}$ in the partial type $\pi$.

Definition 4.1

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$ and let $\pi ({\overline{y}} )$ be a partial type in T. A ${\textbf{K}}$-configuration into $\pi$ is a family of functions $(I, f_A)_{A \in {\textbf{K}} }$ such that

• (1) $I : \textrm{sig} (L_0) \rightarrow L({\mathfrak {C}} )$;

• (2) for all $A \in {\textbf{K}}$, $f_A : A \rightarrow \pi ({\mathfrak {C}} )$; and

• (3) for all $R \in \textrm{sig} (L_0)$, for all $A \in {\textbf{K}}$, for all ${\overline{a}} \in A^{\textrm{arity} (R)}$,

  $$\begin{aligned} A \models R({\overline{a}} ) \Longleftrightarrow {\mathfrak {C}} \models I(R)(f_A({\overline{a}} )). \end{aligned}$$

Note that, for each n-ary relation symbol R in $L_0$, the $L({\mathfrak {C}} )$-formula I(R) has free variables consisting of an n-tuple of tuples of variables, each of the same sort as ${\overline{y}}$.

For a small $C \subseteq {\mathfrak {C}}$, we say that a ${\textbf{K}}$-configuration $(I, f_A)_{A \in {\textbf{K}} }$ is over C if the image of I is contained in the set of all L(C)-formulas. We say $(I, f_A)_{A \in {\textbf{K}} }$ is parameter-free if it is over $\emptyset$. We say $(I, f_A)_{A \in {\textbf{K}} }$ is injective if $f_A$ is injective for each $A \in {\textbf{K}}$.

A ${\textbf{K}}$-configuration can be defined in terms of the Fraïssé limit of ${\textbf{K}}$.

Lemma 4.2

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$ with Fraïssé limit $\Gamma$, let $\pi$ be a partial type in T, and let $C \subseteq {\mathfrak {C}}$ be small. There exists a ${\textbf{K}}$-configuration into $\pi$ over C if and only if there exist $I : \textrm{sig} (R_0) \rightarrow L(C)$ and $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ such that, for all $R \in \textrm{sig} (L_0)$ and for all ${\overline{a}} \in \Gamma ^{\textrm{arity} (R)}$,

$$\begin{aligned} \Gamma \models R({\overline{a}} ) \Longleftrightarrow {\mathfrak {C}} \models I(R)(f({\overline{a}} )). \end{aligned}$$

Proof

($\Leftarrow$): Suppose I and f are given. For each $A \in {\textbf{K}}$, let $f_A$ be obtained by composing f with an embedding of A into $\Gamma$. Then, $(I, f_A)_{A \in {\textbf{K}} }$ is a ${\textbf{K}}$-configuration into $\pi$.

($\Rightarrow$): Let $(I, f_A)_{A \in {\textbf{K}} }$ be a ${\textbf{K}}$-configuration into $\pi ({\overline{y}} )$. For each $a \in \Gamma$, let ${\overline{y}} _a$ be a tuple of variables in T of the same sort as ${\overline{y}}$ such that ${\overline{y}} _a$ and ${\overline{y}} _b$ are disjoint for $a \ne b$. Consider the type $\Sigma$ in the free variables $({\overline{y}} _a)_{a \in \Gamma }$ consisting of:

• (1) $\pi ({\overline{y}} _a)$ for all $a \in \Gamma$; and

• (2) $I(R)({\overline{y}} _{a_0}, \dots , {\overline{y}} _{a_{n-1}})^{\text {iff } \Gamma \models R({\overline{a}} )}$ for all n-ary $R \in \textrm{sig} (L_0)$ and ${\overline{a}} \in \Gamma ^n$.

By assumption, $\Sigma$ is finitely satisfiable. By compactness, $\Sigma$ is consistent and, by saturation of ${\mathfrak {C}}$, it has a realization in ${\mathfrak {C}}$, say $( {\overline{c}} _a )_{a \in \Gamma }$. Define $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ by setting $f(a) = {\overline{c}} _a$. Then I and f are the desired functions.

$\square$

In light of the previous lemma, configurations are closely related to a notion called “trace definability,” studied in [17].

Example 4.3

If T is the theory of the random 3-hypergraph and $\pi (x) = (x = x)$, where x is a singleton, then there exists a ${\textbf{G}}$-configuration into $\pi$. Specifically, if R is the ternary relation in L and E is the binary relation in $L_0$, then let $I(E)(x,y) = R(x,y,a)$ for some $a \in {\mathfrak {C}}$; this gives the desired ${\textbf{G}}$-configuration. However, there does not exist a parameter-free ${\textbf{G}}$-configuration into $\pi$; by quantifier elimination, any L-formula must be a Boolean combination of formulas of the form R(x, y, z) and equality.

We will see that any configuration can be made to be parameter-free at the cost of changing the type; see Lemma 4.6. On the other hand, if T has NIP, we will see that there exists no ${\textbf{G}}$-configuration into any partial type in T (see Theorem 5.2 (2)).

In the preceding example, we saw a case where the target theory was the theory of a Fraïssé limit of a Fraïssé class other than the index class ${\textbf{K}}$. In this case, we were unable to find a parameter-free configuration into $x = x$. However, if T is the theory of the Fraïssé limit of ${\textbf{K}}$, we can.

Lemma 4.4

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$, let T be the theory of the Fraïssé limit of ${\textbf{K}}$, and let $\pi (x) = (x = x)$, where x is a singleton. Then, there exists a parameter-free ${\textbf{K}}$-configuration into $\pi$.

Proof

Let I be the inclusion function on $\textrm{sig} (L_0)$ and, for each $A \in {\textbf{K}}$, let $f_A : A \rightarrow {\mathfrak {C}}$ be any embedding. Then, $(I, f_A)_{A \in {\textbf{K}} }$ is a ${\textbf{K}}$-configuration into $\pi$. $\square$

Lemma 4.5

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$. If $\pi _0({\overline{y}} )$ and $\pi _1({\overline{y}} )$ are partial types in T, $\pi _0({\overline{y}} ) \vdash \pi _1({\overline{y}} )$, and there exists a ${\textbf{K}}$-configuration in $\pi _0$, then there exists a ${\textbf{K}}$-configuration into $\pi _1$.

Proof

Since $\pi _0({\mathfrak {C}} ) \subseteq \pi _1({\mathfrak {C}} )$, any ${\textbf{K}}$-configuration into $\pi _0$ is also a ${\textbf{K}}$-configuration into $\pi _1$. $\square$

As an immediate consequence of the previous lemma, if $\pi ({\overline{y}} )$ is a partial type in T and there exists a ${\textbf{K}}$-configuration into $\pi$, then there exists a ${\textbf{K}}$-configuration into the type ${\overline{y}} = {\overline{y}}$.

As previously mentioned, we can convert any configuration into a parameter-free one at the cost of changing the target partial type.

Lemma 4.6

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$ and let $\pi$ be a partial type in T. If there exists a ${\textbf{K}}$-configuration into $\pi$, then there exists a parameter-free ${\textbf{K}}$-configuration into some partial type of T (possibly different from $\pi$).

Proof

Let $\pi ({\overline{y}} )$ be a partial type in T and let $(I, f_A)_{A \in {\textbf{K}} }$ be a ${\textbf{K}}$-configuration into $\pi$. Choose ${\overline{c}} \in {\mathfrak {C}} ^{< \omega }$ such that, for all $R \in \textrm{sig} (L_0)$, we can take ${\overline{c}}$ to be the parameters of I(R) (this can be done as $\textrm{sig} (L_0)$ is finite). Define $\pi ^*$ a partial type of T to be $\pi$ expanded by adding dummy variables ${\overline{z}}$ for ${\overline{c}}$. Then, for each $R \in \textrm{sig} (L_0)$ of arity n, $I(R)({\overline{y}} _0, \dots , {\overline{y}} _{n-1})$ is T-equivalent to $\varphi _R({\overline{y}} _0, \dots , {\overline{y}} _{n-1}, {\overline{c}} )$ for some L-formula $\varphi _R$. Let

$$\begin{aligned} I'(R)({\overline{y}} _0, {\overline{z}} _0, {\overline{y}} _1, {\overline{z}} _1, \dots , {\overline{y}} _{n-1}, {\overline{z}} _{n-1}) = \varphi _R({\overline{y}} _0, \dots , {\overline{y}} _{n-1}, {\overline{z}} _0). \end{aligned}$$

For each $A \in {\textbf{K}}$, define $f'_A : A \rightarrow \pi ^*({\mathfrak {C}} )$ as follows: For $a \in A$,

$$\begin{aligned} f'_A(a) = (f_A(a), {\overline{c}} ). \end{aligned}$$

Then, it is easy to check that $(I', f'_A)_{A \in {\textbf{K}} }$ is a parameter-free ${\textbf{K}}$-configuration into $\pi ^*$.

$\square$

We can also convert any configuration into an injective one at the cost of changing the target partial type (assuming the target theory has infinite models).

Lemma 4.7

Assume T has infinite models. Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$ and let $\pi$ be a partial type in T. If there exists a ${\textbf{K}}$-configuration into some partial type $\pi$ of T, then there exists an injective ${\textbf{K}}$-configuration into some partial type of T (possibly different from $\pi$).

Proof

Let $\pi ({\overline{y}} )$ be a partial type in T and let $(I, f_A)_{A \in {\textbf{K}} }$ be a ${\textbf{K}}$-configuration into $\pi$. Let z be a single variable in T not used in $\pi$ and let $\pi '({\overline{y}} , z) = \pi ({\overline{y}} )$. For each n-ary $R \in \textrm{sig} (L_0)$, let

$$\begin{aligned} I'(R)({\overline{y}} _0, z_0, \dots , {\overline{y}} _{n-1}, z_{n-1}) = I(R)({\overline{y}} _0, \dots , {\overline{y}} _{n-1}). \end{aligned}$$

For each $A \in {\textbf{K}}$, since A is finite and ${\mathfrak {C}}$ is infinite, there exists an injective function $g : A \rightarrow {\mathfrak {C}}$. Let $f'_A : A \rightarrow \pi '({\mathfrak {C}} )$ be given by $f'_A(a) = (f_A(a), g(a))$ for all $a \in A$. By construction, $f'_A$ is injective. Thus, $(I', f'_A)_{A \in {\textbf{K}} }$ is an injective ${\textbf{K}}$-configuration into $\pi '$. $\square$

Definition 4.8

For each $t < 2$, let ${\textbf{K}} _t$ be a strong amalgamation Fraïssé class over a finite relational language $L_t$. We say that ${\textbf{K}} _0$ is a reductive subclass of ${\textbf{K}} _1$ if $\textrm{sig} (L_0) \subseteq \textrm{sig} (L_1)$ and, for each $A \in {\textbf{K}} _0$, there exists $B \in {\textbf{K}} _1$ such that $A \cong _{L_0} B |_{L_0}$.

Example 4.9

Note that $\textbf{LO}$ is a reductive subclass of ${\textbf{T}}$ (it is actually just a subclass). For any ${\textbf{K}} _0$ and ${\textbf{K}} _1$, ${\textbf{K}} _0$ is a reductive subclass of ${\textbf{K}} _0 *{\textbf{K}} _1$ (see Remark 3.2).

Lemma 4.10

For each $t < 2$, let ${\textbf{K}} _t$ be a strong amalgamation Fraïssé class over a finite relational language $L_t$, and let $\pi$ be a partial type in T. If there exists a ${\textbf{K}} _1$-configuration into $\pi$ and ${\textbf{K}} _0$ is a reductive subclass of ${\textbf{K}} _1$, then there exists a ${\textbf{K}} _0$-configuration into $\pi$.

Proof

Fix $(I, f_B)_{B \in {\textbf{K}} _1}$ a ${\textbf{K}} _1$-configuration into $\pi$. Fix $A \in {\textbf{K}} _0$. Choose $B \in {\textbf{K}} _1$ and $g : A \rightarrow B$ such that g is an $L_0$-isomorphism, and let $f'_A = f_B \circ g$. Then, for all $R \in \textrm{sig} (L_0)$ and ${\overline{a}} \in A^{\textrm{arity} (R)}$,

$$\begin{aligned} A \models R({\overline{a}} ) \Longleftrightarrow B \models R(g({\overline{a}} )) \Longleftrightarrow {\mathfrak {C}} \models I(R)(f_B(g({\overline{a}} ))). \end{aligned}$$

Thus, $(I, f'_A)_{A \in {\textbf{K}} _0}$ is a ${\textbf{K}} _0$-configuration into $\pi$. $\square$

If $\pi _0({\overline{y}} _0)$ and $\pi _1({\overline{y}} _1)$ are two partial types in T where ${\overline{y}} _0$ and ${\overline{y}} _1$ are disjoint, define $\pi _0 \times \pi _1$ to be the following type:

$$\begin{aligned} (\pi _0 \times \pi _1)({\overline{y}} _0, {\overline{y}} _1) = \pi _0({\overline{y}} _0) \cup \pi _1({\overline{y}} _1). \end{aligned}$$

If ${\overline{y}} _0$ and ${\overline{y}} _1$ are not disjoint, we can choose different variables to force disjointness. Fix $n \ge 1$ and define $\pi ^{\times n}$ recursively as follows:

• (1) $\pi ^{\times 1} = \pi$,

• (2) $\pi ^{\times (n+1)} = \pi ^{\times n} \times \pi$.

It turns out that free superposition interacts with configurations into these type products in the obvious manner.

Proposition 4.11

For each $t < 2$, let ${\textbf{K}} _t$ be a strong amalgamation Fraïssé class over a finite relational language $L_t$. Suppose $\pi _0$ and $\pi _1$ are two partial types in T. Suppose there exist a ${\textbf{K}} _0$-configuration into $\pi _0$ and a ${\textbf{K}} _1$-configuration into $\pi _1$. Then, there exists a $({\textbf{K}} _0 *{\textbf{K}} _1)$-configuration into $\pi _0 \times \pi _1$.

Proof

For each $t < 2$, let $(I_t, f_{t,A})_{A \in {\textbf{K}} _t}$ be a ${\textbf{K}} _t$-configuration into $\pi _t$. We build $(I, f_A)_{A \in {\textbf{K}} _0 *{\textbf{K}} _1}$ a $({\textbf{K}} _0 *{\textbf{K}} _1)$-configuration into $\pi _0 \times \pi _1$.

For each $t < 2$ and each n-ary relation symbol R in $L_t$, let

$$\begin{aligned} I(R)({\overline{y}} _{0,0}, {\overline{y}} _{0,1}, {\overline{y}} _{1,0}, {\overline{y}} _{1,1}, \dots , {\overline{y}} _{n-1,0}, {\overline{y}} _{n-1,1}) = I_t(R)({\overline{y}} _{0,t}, {\overline{y}} _{1,t}, \dots , {\overline{y}} _{n-1,t}). \end{aligned}$$

(Note that ${\overline{y}} _{i,t}$ is of the same sort as free the variables of $\pi _t$ for all $i < n$ and $t < 2$.) Fix $A \in {\textbf{K}} _0 *{\textbf{K}} _1$. Let $f_A : A \rightarrow (\pi _0 \times \pi _1)({\mathfrak {C}} )$ be given by, for all $a \in A$,

$$\begin{aligned} f_A(a) = (f_{0,A |_{L_0}}(a), f_{1, A|_{L_1}}(a)). \end{aligned}$$

Then, we get that, for all $R \in \textrm{sig} (L_2)$, for all ${\overline{a}} \in A^{\textrm{arity} (R)}$,

$$\begin{aligned} A \models R({\overline{a}} ) \Longleftrightarrow {\mathfrak {C}} \models I(R)(f_A({\overline{a}} )). \end{aligned}$$

Thus, $(I, f_A)_{A \in {\textbf{K}} _0 *{\textbf{K}} _1}$ is a $({\textbf{K}} _0 *{\textbf{K}} _1)$-configuration into $\pi _0 \times \pi _1$. $\square$

Corollary 4.12

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language and let $T_0$ be the theory of the Fraïssé limit of ${\textbf{K}}$. If ${\overline{x}}$ is a tuple of variables with $n = |{\overline{x}} |$ in $T_0$, then there exists a ${\textbf{K}} ^{*n}$-configuration into ${\overline{x}} = {\overline{x}}$.

Proof

Use Lemma 4.4, Proposition 4.11, and induction. $\square$

We can “compose” configurations, as long as the first configuration is parameter-free and the second is injective.

Proposition 4.13

For each $t < 2$, let ${\textbf{K}} _t$ be a strong amalgamation Fraïssé class over a finite relational language $L_t$. Suppose that $\pi ({\overline{z}} )$ is a partial type in T and suppose ${\overline{y}}$ is an n-tuple of variables in the Fraïssé limit of ${\textbf{K}} _1$ for some $n < \omega$. Suppose there exist an injective ${\textbf{K}} _1$-configuration into $\pi$ and a parameter-free ${\textbf{K}} _0$-configuration into ${\overline{y}} = {\overline{y}}$. Then, there exists a ${\textbf{K}} _0$-configuration into $\pi ^{\times n}$.

Proof

Let $(I, f_A)_{A \in {\textbf{K}} _0}$ be a ${\textbf{K}} _0$-configuration into ${\overline{y}} = {\overline{y}}$. Since the theory of the Fraïssé limit of ${\textbf{K}} _1$ has quantifier elimination, we may assume that, for each $R \in \textrm{sig} (L_0)$, I(R) is a quantifier-free $L_1$-formula. Let $(J, g_B)_{B \in {\textbf{K}} _1}$ be a ${\textbf{K}} _1$-configuration into $\pi ({\overline{z}} )$. Extend J to $\textrm{sig} (L_1) \cup \{ = \}$ by setting

$$\begin{aligned} J(=)({\overline{z}} _0, {\overline{z}} _1) = [{\overline{z}} _0 = {\overline{z}} _1]. \end{aligned}$$

Define $H : \textrm{sig} (L_0) \rightarrow L({\mathfrak {C}} )$ by the following method: For each k-ary $R \in \textrm{sig} (L_0)$, consider $I(R)({\overline{y}} _0, \dots , {\overline{y}} _{k-1})$ (so ${\overline{y}} _i = ( y_{i,0}, \dots , y_{i,n-1} )$ for each $i < k$). For each $S(y_{i_0,j_0}, \dots , y_{i_{\ell -1},j_{\ell -1}}) \in \textrm{sig} (L_1) \cup \{ = \}$ used in I(R), replace it with

$$\begin{aligned} J(S)({\overline{z}} _{i_0,j_0}, \dots , {\overline{z}} _{i_{\ell -1},j_{\ell -1}}). \end{aligned}$$

This creates an $L({\mathfrak {C}} )$-formula in the variables $( ( {\overline{z}} _{i,j} )_{j< n} )_{i < k}$; call it H(R). For each $A \in {\textbf{K}} _0$, choose $B \in {\textbf{K}} _1$ so that the image of $f_A$ is contained in $B^n$ (we can do this since $f_A$ maps into n-tuples of the Fraïssé limit of ${\textbf{K}} _1$). Then, define $h_A : A \rightarrow \pi ^{\times n}({\mathfrak {C}} )$ by setting $h_A(a) = g_B(f_A(a))$ for all $a \in A$. It is easy to check that $(H, h_A)_{A \in {\textbf{K}} _0}$ is a ${\textbf{K}} _0$-configuration into $\pi ^{\times n}$.

$\square$

We analyze how the properties of being definably self-similar and being age indivisible translate to configurations. Being age indivisible manifests in a uniformity condition on L-types.

Proposition 4.14

Suppose that ${\textbf{K}}$ is an age indivisible strong amalgamation Fraïssé class in a finite relational language $L_0$ with Fraïssé limit $\Gamma$ and suppose that $\pi ({\overline{y}} )$ is a partial type in T. For all small $C \subseteq {\mathfrak {C}}$, if there exists a ${\textbf{K}}$-configuration into $\pi$ over C, then there exist $I : \textrm{sig} (R_0) \rightarrow L(C)$ and $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ such that

• (1) for all $R \in \textrm{sig} (L_0)$, for all ${\overline{a}} \in \Gamma ^{\textrm{arity} (R)}$, $\Gamma \models R({\overline{a}} )$ if and only if ${\mathfrak {C}} \models I(R)(f({\overline{a}} ))$; and

• (2) for all $a, b \in \Gamma$,

  $$\begin{aligned} \textrm{tp} _L(f(a) / C) = \textrm{tp} _L(f(b) / C). \end{aligned}$$

Proof

Take $I : \textrm{sig} (L_0) \rightarrow L(C)$ and $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ as in Lemma 4.2. Take $\Sigma$ as in the proof of Lemma 4.2, with the additional formulas:

• (3) $\psi ({\overline{y}} _a) \leftrightarrow \psi ({\overline{y}} _b)$ for all $\psi \in L(C)$ and $a, b \in \Gamma$.

Fix $\Sigma _0 \subseteq \Sigma$ finite. Then, there exists a finite set of L(C)-formulas $\Psi ({\overline{y}} )$ and a finite $A \subseteq \Gamma$ so that $\Sigma _0$ mentions only variables ${\overline{y}} _a$ for $a \in A$ and only formulas $\psi ({\overline{y}} _a) \leftrightarrow \psi ({\overline{y}} _b)$ for $\psi \in \Psi$ and $a, b \in A$. Consider the coloring $c : \Gamma \rightarrow {}^{\Psi } 2$ so that, for all $a \in \Gamma$ and $\psi \in \Psi$,

$$\begin{aligned} c(a)(\psi ) = 1 \Longleftrightarrow {\mathfrak {C}} \models \psi (f(a)). \end{aligned}$$

Since ${\textbf{K}}$ is age indivisible, there exists an embedding $g : A \rightarrow \Gamma$ such that c is constant on g(A). Thus, we get. $(f(g(a)))_{a \in A} \models \Sigma _0$.

By compactness and saturation, there exists $({\overline{c}} _a)_{a \in \Gamma } \models \Sigma$. Define $f' : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ by setting $f'(a) = {\overline{c}} _a$. Then, $f'$ is the desired function. $\square$

Note that, if we take C so that $\pi$ is over C, then Proposition 4.14 is saying that we can choose f so that f maps into the realizations of some complete type over C extending $\pi$.

When ${\textbf{K}}$ is definably self-similar, we get a stronger condition on L-types. For all $A \subseteq \Gamma$, let ${\mathcal {S}} (A)$ be the set of all complete, non-algebraic 1-$L_0$-types over A.

Proposition 4.15

Suppose that ${\textbf{K}}$ is a definably self-similar strong amalgamation Fraïssé class in a finite relational language $L_0$ with Fraïssé limit $\Gamma$ and suppose that $\pi ({\overline{y}} )$ is a partial type in T. For all small $C \subseteq {\mathfrak {C}}$, if there exists a ${\textbf{K}}$-configuration into $\pi$ over C, then there exist $I : \textrm{sig} (R_0) \rightarrow L(C)$, $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$, and $J \subseteq |{\overline{y}} |$ such that

• (1) for all $R \in \textrm{sig} (L_0)$, for all ${\overline{a}} \in \Gamma ^{\textrm{arity} (R)}$, $\Gamma \models R({\overline{a}} )$ if and only if ${\mathfrak {C}} \models I(R)(f({\overline{a}} ))$; and

• (2) for all $a, b \in \Gamma$, $\textrm{tp} _L(f(a) / C) = \textrm{tp} _L(f(b) / C)$;

• (3) for all $j \in J$ and all $a, b \in \Gamma$, $f(a)_j = f(b)_j$; and

• (4) for all finite $A \subseteq \Gamma$ and all $p \in {\mathcal {S}} (A)$, there exists $b \models p$ such that, for all $i, j \in |{\overline{y}} | \setminus J$ and all $a \in A$, $f(a)_i \ne f(b)_j$.

Proof

By Proposition 4.14, there exist I and f such that (1) and (2) hold.

For conditions (3) and (4), start with $J = \emptyset$ and construct J recursively as follows: For any J satisfying condition (3), assume that condition (4) fails. So there exist a finite $A \subseteq \Gamma$ and $p \in {\mathcal {S}} (A)$ such that, for all $b \models p$, there exist $i, j \in |{\overline{y}} | \setminus J$ and $a \in A$ such that $f(a)_i = f(b)_j$. Let $\Gamma ' = \{ b \in \Gamma : b \models p \}$. Since ${\textbf{K}}$ is definably self-similar, $\Gamma ' \cong \Gamma$. Consider a coloring $c : \Gamma ' \rightarrow (|{\overline{y}} | \setminus J)^2 \times A$ given by $c(b) = (i,j,a)$ for some choice of $i, j \in |{\overline{y}} | \setminus J$ and $a \in A$ such that $f(a)_i = f(b)_j$. By Lemma 3.15, we may assume that c is constant. Thus, for all $b, d \in \Gamma '$, $f(b)_j = f(a)_i = f(d)_j$ (in other words, condition (3) holds on $\Gamma '$ for $J \cup \{ j \}$). Add j to J and replace $\Gamma$ with $\Gamma '$. Repeat this process. Since $|{\overline{y}} |$ is finite, this will eventually terminate. This gives us the desired conclusion. $\square$

We use Proposition 4.14 and Proposition 4.15 in Sect. 6.4 to compute ${\textbf{K}}$-ranks for particular choices of ${\textbf{K}}$.

5 Dividing lines

Before defining and studying ${\textbf{K}}$-ranks, we first connect the notions discussed above with the ideas considered in [7].

Definition 5.1

Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class. Define ${\mathcal {C}} _{\textbf{K}}$ to be the class of all complete theories T with infinite models such that there exists a ${\textbf{K}}$-configuration into some partial type $\pi$ (in this case, we will say that T admits a ${\textbf{K}}$-configuration).

Note that our definition of ${\mathcal {C}} _{\textbf{K}}$ coincides with the definition of ${\mathfrak {C}}_{\textbf{K}}$ from [7] in the case where ${\textbf{K}}$ is an indecomposable strong amalgamation Fraïssé class (see Observation 2.12 of [7]). In that paper, the authors establish a quasi-order on theories, use this quasi-order to define classes of theories, and show that these classes are exactly those of the form ${\mathcal {C}} _{\textbf{K}}$ for some indecomposable strong amalgamation Fraïssé class, ${\textbf{K}}$ (see Theorem 2.17 of [7] for more details).

How do the classes ${\mathcal {C}} _{\textbf{K}}$ relate to known dividing lines in model theory? First of all, ${\mathcal {C}} _{\textbf{S}} = {\mathcal {C}} _{\textbf{E}}$ is the class of all complete theories with infinite models. What about more interesting ${\textbf{K}}$? The following theorem describes the relationship of ${\mathcal {C}} _{\textbf{K}}$ to the classes of theories that are stable, NIP, and k-dependent.

Theorem 5.2

(Proposition 4.31 of [7], Proposition 5.2 of [4]) Let T be a complete first-order theory with infinite models.

• (1) T is stable if and only if $T \notin {\mathcal {C}} _\textbf{LO}$.

• (2) T has NIP if and only if $T \notin {\mathcal {C}} _{\textbf{G}}$.

• (3) For all $k \ge 2$, T has $(k-1)$-dependence if and only if $T \notin {\mathcal {C}} _{{\textbf{H}} _k}$.

Proof

If $\varphi ({\overline{y}} ; {\overline{z}} )$ is a witness to the order property, then the map I sending < to

$$\begin{aligned} \varphi ^*({\overline{y}} _0, {\overline{z}} _0; {\overline{y}} _1, {\overline{z}} _1) = \varphi ({\overline{y}} _0; {\overline{z}} _1) \end{aligned}$$

witnesses that there exists an $\textbf{LO}$-configuration into ${\mathfrak {C}} ^{|{\overline{y}} |+|{\overline{z}} |}$. Similar arguments can be made for the $(k-1)$-independence property and ${\textbf{H}} _k$-configurations for $k \ge 2$; see the proof of Lemma 2.2 of [13].

$\square$

Definition 5.3

Given two strong amalgamation Fraïssé classes ${\textbf{K}} _0$ and ${\textbf{K}} _1$, we say that

$$\begin{aligned} {\textbf{K}} _0 \lesssim {\textbf{K}} _1 \end{aligned}$$

if the theory of the Fraïssé limit of ${\textbf{K}} _1$ is in ${\mathcal {C}} _{{\textbf{K}} _0}$. We say

$$\begin{aligned} {\textbf{K}} _0 \sim {\textbf{K}} _1 \end{aligned}$$

if ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$ and ${\textbf{K}} _1 \lesssim {\textbf{K}} _0$.

Proposition 5.4

Fix strong amalgamation Fraïssé classes ${\textbf{K}} _0$, ${\textbf{K}} _1$, and ${\textbf{K}} _2$.

• (1) $\lesssim$ is a quasi-order on strong amalgamation Fraïssé classes.

• (2) ${\textbf{K}} _0 \lesssim {\textbf{K}} _0 *{\textbf{K}} _1$.

• (3) if ${\textbf{K}} _0 \lesssim {\textbf{K}} _2$ and ${\textbf{K}} _1 \lesssim {\textbf{K}} _2$, then ${\textbf{K}} _0 *{\textbf{K}} _1 \lesssim {\textbf{K}} _2$.

• (4) ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$ if and only if ${\mathcal {C}} _{{\textbf{K}} _1} \subseteq {\mathcal {C}} _{{\textbf{K}} _0}$.

• (5) ${\textbf{K}} _0 \sim {\textbf{K}} _1$ if and only if ${\mathcal {C}} _{{\textbf{K}} _0} = {\mathcal {C}} _{{\textbf{K}} _1}$.

Proof

For each $i < 3$, let $L_i$ be the language of ${\textbf{K}} _i$ and let $T_i$ be the theory of the Fraïssé limit of ${\textbf{K}} _i$.

(1): By Lemma 4.4, $T_0$ admits a ${\textbf{K}} _0$-configuration. Hence, ${\textbf{K}} _0 \lesssim {\textbf{K}} _0$. So $\lesssim$ is reflexive.

Assume that ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$ and ${\textbf{K}} _1 \lesssim {\textbf{K}} _2$. Then, $T_1$ admits a ${\textbf{K}} _0$-configuration and $T_2$ admits a ${\textbf{K}} _1$-configuration. By Lemma 4.6, $T_1$ admits a parameter-free ${\textbf{K}} _0$-configuration and, by Lemma 4.7, $T_2$ admits an injective ${\textbf{K}} _1$-configuration. So, by Proposition 4.13, $T_2$ admits a ${\textbf{K}} _0$-configuration. Thus, ${\textbf{K}} _0 \lesssim {\textbf{K}} _2$. So $\lesssim$ is transitive.

(2): Let $T_0 *T_1$ be the theory of the Fraïssé limit of ${\textbf{K}} _0 *{\textbf{K}} _1$. By (1), $T_0 *T_1$ admits a $({\textbf{K}} _0 *{\textbf{K}} _1)$-configuration. However, ${\textbf{K}} _0$ is a reductive subclass of ${\textbf{K}} _0 *{\textbf{K}} _1$. By Lemma 4.10, $T_0 *T_1$ admits a ${\textbf{K}} _0$-configuration.

(3): Assume ${\textbf{K}} _0 \lesssim {\textbf{K}} _2$ and ${\textbf{K}} _1 \lesssim {\textbf{K}} _2$. Thus, $T_2$ admits a ${\textbf{K}} _0$-configuration and a ${\textbf{K}} _1$-configuration. By Proposition 4.11, $T_2$ admits a $({\textbf{K}} _0 *{\textbf{K}} _1)$-configuration. Therefore, ${\textbf{K}} _0 *{\textbf{K}} _1 \lesssim {\textbf{K}} _2$.

(4), ($\Rightarrow$): Assume ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$ and $T \in {\mathcal {C}} _{{\textbf{K}} _1}$. By Lemma 4.6, $T_1$ admits a parameter-free ${\textbf{K}} _0$-configuration. By Lemma 4.7, T admits an injective ${\textbf{K}} _1$-configuration. By Proposition 4.13, T admits a ${\textbf{K}} _0$-configuration. Thus, $T \in {\mathcal {C}} _{{\textbf{K}} _0}$.

(4), ($\Leftarrow$): Assume ${\mathcal {C}} _{{\textbf{K}} _1} \subseteq {\mathcal {C}} _{{\textbf{K}} _0}$. By Lemma 4.4, $T_1$ is in ${\mathcal {C}} _{{\textbf{K}} _1}$. Therefore, it is in ${\mathcal {C}} _{{\textbf{K}} _0}$. Therefore, ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$.

(5): Follows immediately from (4). $\square$

From this proposition, we get a characterization of when a free superposition of two classes is equivalent to one of the classes. This corollary is a generalization of two results from [7], namely Corollary 3.10 and Theorem 4.24.

Corollary 5.5

Suppose ${\textbf{K}} _0$ and ${\textbf{K}} _1$ are strong amalgamation Fraïssé classes. Then, ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$ if and only if ${\textbf{K}} _0 *{\textbf{K}} _1 \sim {\textbf{K}} _1$.

Proof

($\Rightarrow$): Assume ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$. By Proposition 5.4 (2), ${\textbf{K}} _1 \lesssim {\textbf{K}} _0 *{\textbf{K}} _1$. By Proposition 5.4 (1), ${\textbf{K}} _1 \lesssim {\textbf{K}} _1$. By Proposition 5.4 (3), ${\textbf{K}} _0 *{\textbf{K}} _1 \lesssim {\textbf{K}} _1$. Thus, ${\textbf{K}} _0 *{\textbf{K}} _1 \sim {\textbf{K}} _1$.

($\Leftarrow$): Assume ${\textbf{K}} _0 *{\textbf{K}} _1 \sim {\textbf{K}} _1$. By Proposition 5.4 (2), ${\textbf{K}} _0 \lesssim {\textbf{K}} _0 *{\textbf{K}} _1$. By Proposition 5.4 (1), ${\textbf{K}} _0 \lesssim {\textbf{K}} _1$. $\square$

Corollary 5.6

If ${\textbf{K}}$ is a strong amalgamation Fraïssé class and $n \ge 1$, then ${\textbf{K}} ^{*n} \sim {\textbf{K}}$.

Proof

Follows from Corollary 5.5 by induction. $\square$

Corollary 5.7

(Corollary 3.10 of [7]) Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class and T the theory of the Fraïssé limit of ${\textbf{K}}$. Then, T is unstable if and only if ${\textbf{K}} *\textbf{LO} \sim {\textbf{K}}$.

Proof

By Theorem 5.2 (1), T is unstable if and only if $T \in {\mathcal {C}} _{\textbf{LO} }$, which holds if and only if $\textbf{LO} \lesssim {\textbf{K}}$. By Corollary 5.5, $\textbf{LO} \lesssim {\textbf{K}}$ if and only if ${\textbf{K}} *\textbf{LO} \sim {\textbf{K}}$. $\square$

Corollary 5.8

(Theorem 4.24 of [7]) Let $L_0$ be a finite relational language where each relation symbol is at least binary. Let ${\textbf{H}} _{L_0}$ be the class of all $L_0$-hypergraphs (see Example 3.11). Let k be the largest arity among relation symbols in $L_0$. Then,

$$\begin{aligned} {\textbf{H}} _{L_0} \sim {\textbf{H}} _k. \end{aligned}$$

Proof

Let $k_0 \le \dots \le k_{n-1} = k$ list off all arities (with repetition) of the relation symbols in $L_0$. Then,

$$\begin{aligned} {\textbf{H}} _{L_0} = {\textbf{H}} _{k_0} *\dots *{\textbf{H}} _{k_{n-1}}. \end{aligned}$$

Notice that ${\textbf{H}} _m \lesssim {\textbf{H}} _\ell$ for each $m \le \ell$. To see this, suppose that E is the m-ary relation symbol for ${\textbf{H}} _m$, R is the $\ell$-ary relation symbol for ${\textbf{H}} _\ell$, and ${\mathfrak {C}}$ is a monster model of the theory of the Fraïssé limit of ${\textbf{H}} _\ell$. Fix ${\overline{c}} \in {\mathfrak {C}} ^{\ell - m}$ and set

$$\begin{aligned} I(E)(x_0, \dots , x_{m-1}) = R(x_0, \dots , x_{m-1}, {\overline{c}} ). \end{aligned}$$

It is easy to check that this creates an ${\textbf{H}} _m$-configuration into ${\mathfrak {C}}$ (similar to Example 4.3).

So, by Corollary 5.5,

$$\begin{aligned} {\textbf{H}} _{k_0} *\dots *{\textbf{H}} _{k_{n-1}} \sim {\textbf{H}} _{k_{n-1}}. \end{aligned}$$

Therefore, ${\textbf{H}} _{L_0} \sim {\textbf{H}} _k$. $\square$

6 ${\textbf{K}}$-Ranks

In this section, instead of looking at which theories admit a ${\textbf{K}}$-configuration (into any type) for some strong amalgamation Fraïssé class ${\textbf{K}}$, we want to pay close attention to a fixed partial type in the target. We aim to count the number of “independent copies” of a single class ${\textbf{K}}$ that we can code into a partial type. Let T be a complete L-theory with monster model ${\mathfrak {C}}$ and let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a finite relational language $L_0$.

Definition 6.1

Fix $n \ge 1$ and $\pi$ a partial type in T. We say that $\pi$ has ${\textbf{K}}$-rank n if

• (1) there exists a ${\textbf{K}} ^{*n}$-configuration into $\pi$, and

• (2) there does not exist a ${\textbf{K}} ^{*(n+1)}$-configuration into $\pi$.

We say $\pi$ has ${\textbf{K}}$-rank $\infty$ if there exists a ${\textbf{K}} ^{*n}$-configuration into $\pi$ for all $n < \omega$. We say $\pi$ has ${\textbf{K}}$-rank 0 if there does not exist a ${\textbf{K}}$-configuration into $\pi$. We denote the ${\textbf{K}}$-rank of $\pi$ by $\textrm{Rk} _{\textbf{K}} (\pi )$.

We can apply Lemma 4.5 and Proposition 4.11 to get a few immediate results about ${\textbf{K}}$-rank.

Proposition 6.2

(Superadditivity of ${\textbf{K}}$-rank) For all partial types $\pi _0$ and $\pi _1$,

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (\pi _0 \times \pi _1) \ge \textrm{Rk} _{\textbf{K}} (\pi _0) + \textrm{Rk} _{\textbf{K}} (\pi _1). \end{aligned}$$

Proof

Follows immediately from Proposition 4.11. $\square$

Definition 6.3

We say $\textrm{Rk} _{\textbf{K}}$ is additive if, for all partial types $\pi _0$ and $\pi _1$, if $\textrm{Rk} _{\textbf{K}} (\pi _0) < \infty$ and $\textrm{Rk} _{\textbf{K}} (\pi _1) < \infty$, then

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (\pi _0 \times \pi _1) = \textrm{Rk} _{\textbf{K}} (\pi _0) + \textrm{Rk} _{\textbf{K}} (\pi _1). \end{aligned}$$

For example, dp-rank is additive in the above sense [11]. Similarly, op-dimension is additive [6]. This leads to the following question.

Question 6.4

Under what conditions on ${\textbf{K}}$ and T is ${\textbf{K}}$-rank additive?

We present some partial results to Question 6.4 later in this section (see Example 6.10 and Example 6.17).

Lemma 6.5

If $\pi _0({\overline{y}} )$ and $\pi _1({\overline{y}} )$ are partial types in T and $\pi _0({\overline{y}} ) \vdash \pi _1({\overline{y}} )$, then

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (\pi _0) \le \textrm{Rk} _{\textbf{K}} (\pi _1). \end{aligned}$$

Proof

Follows immediately from Lemma 4.5. $\square$

Overloading notation, for each $n \ge 1$, we can define $\textrm{Rk} _{\textbf{K}} (n)$ as follows: Fix an arbitrary n-tuple of variables ${\overline{y}}$ from T and set

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (n) = \textrm{Rk} _{\textbf{K}} ({\overline{y}} = {\overline{y}} ). \end{aligned}$$

This is clearly independent of the choice of ${\overline{y}}$.

Lemma 6.6

For all $1 \le n< m < \omega$,

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (n) \le \textrm{Rk} _{\textbf{K}} (m). \end{aligned}$$

Proof

Suppose $\textrm{Rk} _{\textbf{K}} (n) = \ell$. Then, there exists a ${\textbf{K}} ^{*\ell }$-configuration into ${\mathfrak {C}} ^n$. Clearly there exists an ${\textbf{S}}$-configuration into ${\mathfrak {C}} ^{m-n}$. By Proposition 4.11, there exists a $({\textbf{K}} ^{*\ell } *{\textbf{S}} )$-configuration into ${\mathfrak {C}} ^m$. Since ${\textbf{K}} ^{*\ell } *{\textbf{S}} = {\textbf{K}} ^{*\ell }$, we get that $\textrm{Rk} _{\textbf{K}} (m) \ge \ell$. $\square$

Using the terminology of Sect. 5, note that $T \in {\mathcal {C}} _{\textbf{K}}$ if and only if T is a complete theory with infinite models such that $\textrm{Rk} _{\textbf{K}} (n) > 0$ for some $n \ge 1$. Moreover, by Corollary 5.6, if $T \in {\mathcal {C}} _{{\textbf{K}} }$, then T has types with arbitrarily large ${\textbf{K}}$-rank and, if $T \notin {\mathcal {C}} _{{\textbf{K}} }$ (but T is a complete theory with infinite models), then all types in T have ${\textbf{K}}$-rank 0.

In the following subsections, we will analyze ${\textbf{K}}$-rank for particular choices of ${\textbf{K}}$.

6.1 Linear order rank

For this subsection, we consider the strong amalgamation Fraïssé class $\textbf{LO}$. For any $m \ge 1$, let $L_m$ be the language of $\textbf{LO} ^{*m}$, which consists of m binary relation symbols $<_i$ for $i < m$.

It turns out that $\textbf{LO}$-rank is closely related to op-dimension. For any partial type in any theory, we get that the op-dimension is an upper bound for the $\textbf{LO}$-rank. Moreover, if the target theory has NIP, then op-dimension coincides with $\textbf{LO}$-rank.

Proposition 6.7

For any partial type $\pi$ in any theory T,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (\pi ) \le \textrm{opDim} (\pi ). \end{aligned}$$

Proof

Assume $\textrm{Rk} _\textbf{LO} (\pi ) \ge m$. Let ${\mathfrak {C}}$ be a monster model for T and let $(I, f_A)_{A \in \textbf{LO} ^{*m}}$ be an $\textbf{LO} ^{*m}$-configuration. So, for all $A \in \textbf{LO} ^{*m}$, for all $a, b \in A$, for all $i < m$,

$$\begin{aligned} A \models a<_i b \Longleftrightarrow {\mathfrak {C}} \models I(<_i)(f_A(a), f_A(b)). \end{aligned}$$

Fix $n < \omega$. We will use this configuration to build an IRD-pattern of depth m and length n in $\pi$. Begin by creating an $A \in \textbf{LO} ^{*m}$ with universe ${}^m (2n)$ by setting, for all $g, h \in A$ and $i < m$, $g <_i h$ if $g(i) < h(i)$ or $g(i) = h(i)$ and $g(j) < h(j)$ for minimal $j < m$ such that $g(j) \ne h(j)$. Clearly, for all $i < m$, for all $g, h \in A$,

$$\begin{aligned} g(i)< h(i) \Longrightarrow A \models g <_i h \end{aligned}$$

(but not conversely).

For $g \in {}^m n$, let ${\overline{d}} _g = f_A(g')$, where $g' \in {}^m (2n)$ is such that $g'(i) = 2g(i) + 1$ for all $i < m$. For $j < n$, let ${\overline{c}} _j = f_A(h')$, where $h' \in {}^m (2n)$ is such that $h'(i) = 2j$ for all $i < m$. Then, for all $g \in {}^m n$, $i < m$, and $j < n$,

$$\begin{aligned} {\mathfrak {C}} \models I(<_i)({\overline{d}} _g, {\overline{c}} _j) \Longleftrightarrow 2g(i) + 1< 2j \Longleftrightarrow g(i) < j. \end{aligned}$$

Thus, for each $g \in {}^m n$,

$$\begin{aligned} \pi ({\overline{y}} ) \cup \{ I(<_i)({\overline{y}} , {\overline{c}} _j)^{\text {iff } g(i)< j} : i< m, j < n \} \end{aligned}$$

is consistent. This is an IRD-pattern of depth m and length n in $\pi$. Since n was arbitrary, by compactness, $\pi$ has op-dimension $\ge m$. $\square$

Before showing that $\textbf{LO}$-rank and op-dimension coincide for NIP theories, we mention a trick (essentially Proposition 1.18 of [6]) that follows from the fact that $\textbf{LO} ^{*m}$ has the Ramsey property.

Remark 6.8

Suppose that T is a complete L-theory for any language L, $\pi$ is a partial type in T, ${\textbf{K}}$ is a Ramsey class with Fraïssé limit $\Gamma$, and there exists a ${\textbf{K}}$-configuration into $\pi$. Then, by Theorem 3.12 of [15], the function f in Lemma 4.2 can be chosen so that, for all $n < \omega$, ${\overline{a}} , {\overline{b}} \in \Gamma ^n$,

$$\begin{aligned} \textrm{qftp} _{L_0}({\overline{a}} ) = \textrm{qftp} _{L_0}({\overline{b}} ) \Longrightarrow \textrm{tp} _L(f({\overline{a}} )) = \textrm{tp} _L(f({\overline{b}} )). \end{aligned}$$

Since $\textbf{LO}$ is a Ramsey class, $\textbf{LO} ^{*m}$ is a Ramsey class by Theorem 1.5 of [1]. Therefore, in particular, this holds when ${\textbf{K}} = \textbf{LO} ^{*m}$.

Proposition 6.9

If T has NIP, then, for all partial types $\pi$,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (\pi ) = \textrm{opDim} (\pi ). \end{aligned}$$

This proof loosely follows the proof of Theorem 3.4 of [8], modified to fit into our current framework.

Proof

The previous proposition gives us $\textrm{Rk} _\textbf{LO} (\pi ) \le \textrm{opDim} (\pi )$. To prove the converse, suppose that $\pi$ has op-dimension $\ge m$. Therefore, there exists an IRD-pattern of depth m and length $\omega$ in $\pi$. That is, there exist $L({\mathfrak {C}} )$-formulas $\varphi _i({\overline{y}} , {\overline{z}} _i)$ for $i < m$ and ${\overline{c}} _{i,j} \in {\mathfrak {C}} ^{|{\overline{z}} _i|}$ for $i < m$ and $j < \omega$ such that, for all $g : m \rightarrow \omega$, the partial type

$$\begin{aligned} \pi ({\overline{y}} ) \cup \{ \varphi _i({\overline{y}} , {\overline{c}} _{i,j})^{\text {iff } g(i)< j} : i< m, j < \omega \} \end{aligned}$$

is consistent. Say it is realized by ${\overline{b}} _g \in {\mathfrak {C}} ^{|{\overline{y}} |}$. By coding tricks, we may assume that there exists an L-formula $\varphi ({\overline{y}} , {\overline{z}} )$ such that $\varphi _i = \varphi$ for all $i < m$.

First, we create a function $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$, where $\Gamma$ is the Fraïssé limit of $\textbf{LO} ^{*m}$. Fix $A \in \textbf{LO} ^{*m}$ and suppose that $n = |A|$. Choose an injective function $\eta : A \rightarrow {}^m n$ such that, for all $a, a' \in A$ and for all $i < m$, $\eta (a)(i) < \eta (a')(i)$ if and only if $a <_i a'$. For all $i < m$, $j < n$, and $a \in A$, notice that

$$\begin{aligned} {\mathfrak {C}} \models \varphi ({\overline{b}} _{\eta (a)}, {\overline{c}} _{i,j}) \Longleftrightarrow \eta (a)(i) < j. \end{aligned}$$

Therefore, for all $i < m$, for all $<_i$-cuts Y of A, there exists ${\overline{c}} \in {\mathfrak {C}} ^{|{\overline{z}} |}$ such that

$$\begin{aligned} Y = \{ a \in A : {\mathfrak {C}} \models \varphi ({\overline{b}} _{\eta (a)}, {\overline{c}} ) \}. \end{aligned}$$

Consider the function $a \mapsto {\overline{b}} _{\eta (a)}$ from A to $\pi ({\mathfrak {C}} )$. By compactness, there exists a function $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ such that, for all $i < m$, for all $<_i$-cuts Y of $\Gamma$, there exists ${\overline{c}} \in {\mathfrak {C}} ^{|{\overline{z}} |}$ such that

$$\begin{aligned} Y = \{ a \in \Gamma : {\mathfrak {C}} \models \varphi (f(a), {\overline{c}} ) \}. \end{aligned}$$

By Remark 6.8, we can assume that $f : \Gamma \rightarrow \pi ({\mathfrak {C}} )$ is a generalized indiscernible. Therefore, for each $k < \omega$ and each quantifier-free $L_m$-type $p(x_0, \dots , x_{k-1})$, we have an associated L-type $p^*({\overline{y}} _0, \dots , {\overline{y}} _{k-1})$ (over the same parameters as $\pi$ and $\varphi$) extending $\pi ({\overline{y}} _0) \cup \dots \cup \pi ({\overline{y}} _{k-1})$ such that, for all ${\overline{a}} \in \Gamma ^k$, if ${\overline{a}} \models p$, then $f({\overline{a}} ) \models p^*$.

Since T has NIP, $\varphi ({\overline{y}} , {\overline{z}} )$ has VC-dimension $< k$ for some $k < \omega$. In other words,

$$\begin{aligned} {\mathfrak {C}} \models \lnot \exists {\overline{y}} _0 \dots \exists {\overline{y}} _{k-1} \bigwedge _{s \in {}^k 2} \left( \exists {\overline{z}} \bigwedge _{\ell < k} \varphi ({\overline{y}} _\ell , {\overline{z}} )^{s(\ell )} \right) . \end{aligned}$$

For each $t \in {}^m 2$, define the quantifier-free 2-$L_m$-type $p_t(x_0, x_1)$ as follows: $p_t \vdash x_0 \ne x_1$ and, for all $i < m$, $p_t \vdash x_0 <_i x_1$ if and only if $t(i) = 1$. We can extend this to a quantifier-free k-$L_m$-type $q_t(x_0, \dots , x_{k-1})$ as follows: for all $\ell \ne \ell '$, $q_t \vdash x_\ell \ne x_{\ell '}$ and, for all $i < m$, for all $\ell < k - 1$, $q_t \vdash x_\ell <_i x_{\ell +1}$ if and only if $t(i) = 1$.

Now fix $t, t' \in {}^m 2$ distinct. We may assume, by perhaps swapping t and $t'$, that there exists $i_0 < m$ such that $t(i_0) = 1$ and $t'(i_0) = 0$. Since $\varphi$ has VC-dimension $< k$, there exists $s \in {}^k 2$ such that

$$\begin{aligned} q_t^*({\overline{y}} _0, \dots , {\overline{y}} _{k-1}) \vdash \lnot \exists {\overline{z}} \bigwedge _{\ell < k} \varphi ({\overline{y}} _\ell , {\overline{z}} )^{s(\ell )}. \end{aligned}$$

We define $q_r$ and $\sigma _r$ recursively as follows: Let $q_0 = q_t$ and $\sigma _0$ the identity permutation on k. Fix $r \ge 0$ and assume that we have constructed $q_r$ and $\sigma _r$ such that

$$\begin{aligned} q_r(x_0, \dots , x_{k-1}) \vdash x_{\sigma _r(0)}<_{i_0} x_{\sigma _r(1)}<_{i_0} \dots <_{i_0} x_{\sigma _r(k-1)}. \end{aligned}$$

(1)

Then, choose $\ell _r < k-1$ minimal such that $s(\sigma _r(\ell _r)) = 0$ and $s(\sigma _r(\ell _r + 1)) = 1$. Note that, if no such $\ell _r$ exists, then

$$\begin{aligned} q_r^*({\overline{y}} _0, \dots , {\overline{y}} _{k-1}) \vdash \exists {\overline{z}} \bigwedge _{\ell < k} \varphi ({\overline{y}} _{\sigma _r(\ell )}, {\overline{z}} )^{s(\sigma _r(\ell ))}, \end{aligned}$$

since it is a $<_{i_0}$-cut. In particular, $\ell _0$ exists.

Let $\sigma _{r+1} = \sigma _r \circ (\ell _r \ \ell _r + 1)$ and let $q_{r+1}$ be $q_r$ except, for each $i < m$, we replace

$$\begin{aligned} (x_{\ell _r}<_i x_{\ell _r+1})^{t(i)} \text { with } (x_{\ell _r} <_i x_{\ell _r+1})^{t'(i)}. \end{aligned}$$

In particular, we maintain that $q_{r+1}$ and $\sigma _{r+1}$ satisfy (1). Terminate the construction when we first have

$$\begin{aligned} q_{r+1}^*({\overline{y}} _0, \dots , {\overline{y}} _{k-1}) \vdash \exists {\overline{z}} \bigwedge _{\ell < k} \varphi ({\overline{y}} _\ell , {\overline{z}} )^{s(\ell )} \end{aligned}$$

Choose ${\overline{a}} \in \Gamma ^k$ such that ${\overline{a}} \models q_r$. Let

$$\begin{aligned}&\psi _{t,t'}({\overline{y}} _0, {\overline{y}} _1) := \ \lnot \exists {\overline{z}} \bigl ( \varphi (f(a_0), {\overline{z}} )^{s(0)} \wedge \dots \wedge \varphi (f(a_{\ell _r-1}), {\overline{z}} )^{s(\ell _r-1)} \wedge \\&\quad \varphi ({\overline{y}} _0, {\overline{z}} )^{s(\ell _r)} \wedge \varphi ({\overline{y}} _1, {\overline{z}} )^{s(\ell _r+1)} \wedge \\&\quad \varphi (f(a_{\ell _r+2}), {\overline{z}} )^{s(\ell _r+2)} \wedge \dots \wedge \varphi (f(a_{k-1}), {\overline{z}} )^{s(k-1)} \bigr ). \end{aligned}$$

Consider the set

$$\begin{aligned} \Gamma ' = \{ a \in \Gamma : (a_0, \dots , a_{\ell _r-1}, a, a_{\ell _r+2}, \dots , a_{k-1}) \models q_r |_{x_0, \dots , x_{\ell _r}, x_{\ell _r+2}, \dots , x_{k-1}} \}. \end{aligned}$$

Since $\textbf{LO} ^{*m}$ is definably self-similar, $\Gamma ' \cong \Gamma$. Notice that, for all $a, b \in \Gamma '$,

• If $(a,b) \models p_t$, then $(a_0, \dots , a_{\ell _r-1}, a, b, a_{\ell _r+2}, \dots , a_{k-1}) \models q_r$, hence ${\mathfrak {C}} \models \psi _{t,t'}(f(a), f(b))$.

• If $(a,b) \models p_{t'}$, then $(a_0, \dots , a_{\ell _r-1}, a, b, a_{\ell _r+2}, \dots , a_{k-1}) \models q_{r+1}$, hence ${\mathfrak {C}} \models \lnot \psi _{t,t'}(f(a), f(b))$.

Replace $\Gamma$ with $\Gamma '$ and repeat this process for all distinct $t, t' \in {}^m 2$.

For $t \in {}^m 2$, let

$$\begin{aligned} \psi _t({\overline{y}} _0, {\overline{y}} _1) := \bigwedge _{t' \in {}^m 2, t' \ne t} \psi _{t,t'}({\overline{y}} _0, {\overline{y}} _1). \end{aligned}$$

Finally, for $i < m$, let

$$\begin{aligned} \psi _i({\overline{y}} _0, {\overline{y}} _1) := \bigvee _{t \in {}^m 2, t(i) = 1} \psi _t({\overline{y}} _0, {\overline{y}} _1). \end{aligned}$$

Then, it is clear that, for all $a, b \in \Gamma$ and $i < m$,

$$\begin{aligned} a <_i b \text { if and only if } {\mathfrak {C}} \models \psi _i(f(a), f(b)). \end{aligned}$$

By Lemma 4.2, there exists an $\textbf{LO} ^{*m}$-configuration into $\pi$. Thus, $\textrm{Rk} _{\textbf{LO} }(\pi ) \ge m$. $\square$

Note that this proof uses generalized indiscernibles; this is the only such use in this paper. In future work, we would like to remove the need for indiscernibility so that arguments such as these can be generalized to Fraïssé classes without the Ramsey Property.

Example 6.10

(NIP) Suppose T has NIP. Then $\textbf{LO}$-rank is precisely op-dimension. In particular, $\textbf{LO}$-rank is additive (see Theorem 2.2 of [6]).

If T is distal, then op-dimension coincides with dp-rank (see Remark 3.2 of [6]). Therefore, for distal T, $\textbf{LO}$-rank is dp-rank.

In the next example, we show that $\textbf{LO}$-rank can jump from 0 to $\infty$ in a theory with the independence property.

Example 6.11

Let L consist of infinitely many binary relation symbols $R_i$ for $i < \omega$ and let T be the model companion of the theory of L-hypergraphs. Then,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (1) = 0 \text { and } \textrm{Rk} _\textbf{LO} (2) = \infty . \end{aligned}$$

Proof

Let ${\mathfrak {C}}$ be a monster model for T and let $\Gamma$ be the Fraïssé limit of $\textbf{LO}$. Towards a contradiction, suppose there exists an $\textbf{LO}$-configuration into ${\mathfrak {C}}$ over some small $C \subseteq {\mathfrak {C}}$. Since $\textbf{LO}$ is definably self-similar, there exists a function $f : \Gamma \rightarrow {\mathfrak {C}}$ satisfying the conclusion of Proposition 4.14. Thus, since L is a binary language, for all $a, b \in \Gamma$, the type $\textrm{tp} _L(f(a), f(b) / C)$ is determined by the type $\textrm{tp} _L(f(a), f(b))$. On the other hand, since T is symmetric,

$$\begin{aligned} \textrm{tp} _L(f(a), f(b)) = \textrm{tp} _L(f(b), f(a)). \end{aligned}$$

Therefore, $\Gamma \models a < b$ if and only if $\Gamma \models b < a$, a contradiction.

On the other hand, fix $m < \omega$. For each $i < m$, let

$$\begin{aligned} I(<_i)(y_{0,0}, y_{0,1}, y_{1,0}, y_{1,1}) = R_i(y_{0,0}, y_{1,1}). \end{aligned}$$

For each $A \in \textbf{LO} ^{*m}$, there exists a function $f_A : A \rightarrow {\mathfrak {C}} ^2$ such that, for all $a, b \in A$ and $i < m$,

$$\begin{aligned} A \models a<_i b \Longleftrightarrow {\mathfrak {C}} \models I(<_i)(f_A(a), f_A(b)). \end{aligned}$$

Hence, $(I, f_A)_{A \in \textbf{LO} ^{*m}}$ is an $\textbf{LO} ^{*m}$-configuration into ${\mathfrak {C}} ^2$. $\square$

6.2 Equivalence class rank

For this subsection, we consider the strong amalgamation Fraïssé class ${\textbf{E}}$. For any $m \ge 1$, let $L_m$ be the language of ${\textbf{E}} ^{*m}$, which consists of m binary relation symbols, $E_i$ for $i < m$.

It turns out that ${\textbf{E}}$-rank is bounded above by dp-rank.

Proposition 6.12

For any partial type $\pi$ in any theory T,

$$\begin{aligned} \textrm{Rk} _{\textbf{E}} (\pi ) \le \textrm{dpRk} (\pi ). \end{aligned}$$

Proof

This follows similarly to the proof of Proposition 6.7. Suppose $\textrm{Rk} _{\textbf{E}} (\pi ) \ge m$. Let $\Gamma$ be the Fraïssé limit of ${\textbf{E}} ^{*m}$ and let ${\mathfrak {C}}$ be a monster model for T. Let $(I, f_A)_{A \in {\textbf{E}} ^{*m}}$ be an ${\textbf{E}} ^{*m}$-configuration into ${\mathfrak {C}}$. So, for all $i < m$, for all $A \in {\textbf{E}} ^{*m}$, for all $a, b \in A$,

$$\begin{aligned} A \models E_i(a,b) \Longleftrightarrow {\mathfrak {C}} \models I(E_i)(f_A(a), f_A(b)). \end{aligned}$$

Fix $n < \omega$. Create $A \in {\textbf{E}} ^{*m}$ with universe ${}^m n$ by setting, for all $i < m$ and $g, h \in A$,

$$\begin{aligned} A \models E_i(g, h) \Longleftrightarrow g(i) = h(i). \end{aligned}$$

For $g \in A$, let ${\overline{c}} _g = f_A(g)$. Thus, for all $i < m$, for all $g, h \in A$,

$$\begin{aligned} {\mathfrak {C}} \models I(E_i)({\overline{c}} _g, {\overline{c}} _h) \Longleftrightarrow g(i) = h(i). \end{aligned}$$

For each $j < n$, overloading notation, let j denote the function from m to n that is constantly j. Then, for each $g \in {}^m n$, we have that

$$\begin{aligned} \pi ({\overline{y}} ) \cup \{ I(E_i)({\overline{y}} , {\overline{c}} _j)^{\text {iff } g(i) = j} : i< m, j < n \} \end{aligned}$$

is consistent (realized by ${\overline{c}} _g$). This is an ICT-pattern of depth m and length n in $\pi$. Since n was arbitrary, by compactness, $\pi$ has dp-rank $\ge m$. $\square$

Moreover, ${\textbf{E}}$-rank is bounded below by the dimension of the target type (assuming the target theory has infinite models).

Proposition 6.13

For all theories T with infinite models,

$$\begin{aligned} \textrm{Rk} _{{\textbf{E}} }(m) \ge m. \end{aligned}$$

Proof

Since T has infinite models, there exists an injective function $g : \omega \rightarrow {\mathfrak {C}}$. Fix a tuple of variables ${\overline{y}}$ and let $m = |{\overline{y}} |$. Fix $A \in {\textbf{E}} ^{*m}$ and choose $n < \omega$ such that A embeds into $n^{m+1}$ viewed as an element of ${\textbf{E}} ^{*m}$ as in Lemma 3.18.

Thus, we may assume A is this $L_m$-structure on $n^{m+1}$. Let $f_A : A \rightarrow {\mathfrak {C}} ^m$ be given by $f_A({\overline{a}} ) = (g(a_0), \dots , g(a_m))$ for each ${\overline{a}} \in n^{m+1}$.

For each $i < m$, let

$$\begin{aligned} I(E_i)(y_{0,0}, \dots , y_{0,m}, y_{1,0}, \dots , y_{1,m}) = \left[ y_{0,i} = y_{1,i} \right] . \end{aligned}$$

It is easy to check that $(I, f_A)_{A \in {\textbf{E}} ^{*m}}$ is an ${\textbf{E}} ^{*m}$-configuration into ${\overline{y}} = {\overline{y}}$. Thus, $\textrm{Rk} _{{\textbf{E}} }(m) \ge m$. $\square$

We say that a theory T is dp-minimal if $\textrm{dpRk} (y = y) = 1$ for some (any) single variable y in T. Combining the previous two results, we conclude that ${\textbf{E}}$-rank is precisely equal to the dimension of the target type in dp-minimal theories.

Corollary 6.14

Let T be a dp-minimal theory with infinite models. Then, $\textrm{Rk} _{\textbf{E}} (m) = m$.

Proof

Let ${\overline{y}}$ be an m-tuple of variables from T. By Proposition 6.13,

$$\begin{aligned} \textrm{Rk} _{{\textbf{E}} }({\overline{y}} = {\overline{y}} ) \ge | {\overline{y}} |. \end{aligned}$$

Since dp-rank is subadditive [11], $\textrm{dpRk} ({\overline{y}} = {\overline{y}} ) \le |{\overline{y}} |$. So, by Proposition 6.12,

$$\begin{aligned} \textrm{Rk} _{{\textbf{E}} }({\overline{y}} = {\overline{y}} ) \le \textrm{dpRk} ({\overline{y}} = {\overline{y}} ) \le |{\overline{y}} |. \end{aligned}$$

Thus, $\textrm{Rk} _{\textbf{E}} ({\overline{y}} = {\overline{y}} ) = \textrm{dpRk} ({\overline{y}} = {\overline{y}} ) = |{\overline{y}} |$. $\square$

Question 6.15

If T is dp-minimal and $\pi$ is a partial type in T, then does $\textrm{Rk} _{{\textbf{E}} }(\pi ) = \textrm{dpRk} (\pi )$? More generally, under what conditions does $\textrm{Rk} _{{\textbf{E}} }(\pi ) = \textrm{dpRk} (\pi )$?

Although this question is still open, we have examples where ${\textbf{E}}$-rank and dp-rank differ, even in an NIP theory.

Example 6.16

Fix $k \ge 2$ and let T be the theory of the Fraïssé limit of $\textbf{LO} ^{*k}$. We claim that, in the theory T,

$$\begin{aligned} \left\lfloor \frac{k}{2} \right\rfloor \le \textrm{Rk} _{\textbf{E}} (1) < k. \end{aligned}$$

(On the other hand, $\textrm{dpRk} (y = y) = k$, so these ranks disagree.)

Proof

Let $m = \lfloor k/2 \rfloor$ and fix $A \in {\textbf{E}} ^{*m}$. As in the proof of Proposition 6.13, there exists $n < \omega$ such that A embeds into $X = n^{m+1}$ with $L_m$-structure given in Lemma 3.18. For each $i < m$, we define two linear orders $<_{2i}$ and $<_{2i+1}$ on X as follows: for all ${\overline{a}} , {\overline{b}} \in X$, let

• ${\overline{a}} <_{2i} {\overline{b}}$ if $a_i < b_i$ or $a_i = b_i$ and $a_{j_0} < b_{j_0}$ where $j_0 = \min \{ j < n : a_j \ne b_j \}$, and

• ${\overline{a}} <_{2i+1} {\overline{b}}$ if $a_i > b_i$ or $a_i = b_i$ and $a_{j_0} < b_{j_0}$ where $j_0 = \min \{ j < n : a_j \ne b_j \}$.

It is clear from definition that, for all $i < m$, for all ${\overline{a}} , {\overline{b}} \in X$,

$$\begin{aligned} E_i({\overline{a}} , {\overline{b}} ) \Longleftrightarrow ({\overline{a}}<_{2i} {\overline{b}} \leftrightarrow {\overline{a}} <_{2i+1} {\overline{b}} ). \end{aligned}$$

If $k = 2m + 1$, then define $<_{2m}$ arbitrarily. Since $(X,<_i)_{i < k}$ is an element of $\textbf{LO} ^{*k}$, we get an embedding of X into ${\mathfrak {C}}$, the monster model of T. Composing this function with the one sending A to X, we get a function $f_A : A \rightarrow {\mathfrak {C}}$ such that, for all $a, b \in A$ and $i < m$,

$$\begin{aligned} A \models E_i(a, b) \Longleftrightarrow (f_A(a)<_{2i} f_A(b) \leftrightarrow f_A(a) <_{2i+1} f_A(b)). \end{aligned}$$

For each $i < m$, let

$$\begin{aligned} I(E_i)(y_0, y_1) := \left[ y_0<_{2i} y_1 \leftrightarrow y_0 <_{2i+1} y_1 \right] \end{aligned}$$

Then, $(I, f_A)_{A \in {\textbf{E}} ^{*m}}$ is an ${\textbf{E}} ^{*m}$-configuration into ${\mathfrak {C}}$. Thus, $\textrm{Rk} _{{\textbf{E}} }(1) \ge m$.

On the other hand, suppose that $\Gamma$ is the Fraïssé limit of ${\textbf{E}} ^{*k}$, ${\mathfrak {C}}$ is a monster model of T, and there exists an ${\textbf{E}} ^{*k}$-configuration over a finite C. Since ${\textbf{E}} ^{*k}$ is age indivisible, there exists a function $f : \Gamma \rightarrow {\mathfrak {C}}$ satisfying the conclusion of Proposition 4.14. Fix $a \in \Gamma$ and, for each $s \in {}^k 2$, choose $b_s \in \Gamma$ such that, for all $i < k$, $E_i(a, b_s)$ if and only if $s(i) = 1$. Consider the 2-types in T:

$$\begin{aligned} p_{s,0} = \textrm{tp} _L(f(a), f(b_s)) \text { and } p_{s,1} = \textrm{tp} _L(f(b_s), f(a)). \end{aligned}$$

Since L has only binary relations and each f(a) and $f(b_s)$ have the same L-type over C, these types determine the L-types over C. For any s not the identically 1 function, $f(a) \ne f(b_s)$. Otherwise, suppose that $f(a) = f(b_s)$ where $s \in {}^k 2$ with $s(i) = 0$. Then, we get that

$$\begin{aligned} \textrm{tp} _L(f(a), f(b_1) / C) = \textrm{tp} _L(f(b_s), f(b_1) / C) \end{aligned}$$

(where 1 is the identically 1 function). Since $\Gamma \models E_i(a, b_1)$, this implies that $\Gamma \models E_i(b_s, b_1)$, hence $\Gamma \models E_i(a, b_s)$, which is a contradiction. Similarly, for s and t not identically 1, if $(s,i) \ne (t,j)$, then $p_{s,i} \ne p_{t,j}$. Therefore, we have at least $2 \cdot (2^k - 1)$ many non-equality 2-types in T. On the other hand, there are $2^k$ many non-equality 2-types in T (one type for each possible assignment of $x <_i y$ or $x >_i y$ for all $i < k$). Thus, $2^{k+1} - 2 \le 2^k$, a contradiction. Therefore, there is no ${\textbf{E}} ^{*k}$-configuration into $y = y$. Thus, $\textrm{Rk} _{{\textbf{E}} }(y = y) < k$. $\square$

6.3 Graph rank

For this subsection, we consider the strong amalgamation Fraïssé class ${\textbf{G}}$.

Example 6.17

If T is a theory with NIP, then, for all types $\pi$ in T, $\textrm{Rk} _{\textbf{G}} (\pi ) = 0$. Thus, ${\textbf{G}}$-rank is trivially additive.

Proof

This follows from Theorem 5.2 (2) and Corollary 5.6. $\square$

Similar to $\textbf{LO}$-rank, the ${\textbf{G}}$-rank can jump from 0 to $\infty$ in a theory with the independence property.

Example 6.18

Let L be the language consisting of binary relation symbols $R_i$ for $i < \omega$ and let T be the model companion of the theory of L-structures for which $R_i$ is a triangle-free graph for all $i < \omega$. Then,

$$\begin{aligned} \textrm{Rk} _{\textbf{G}} (1) = 0 \text { and } \textrm{Rk} _{\textbf{G}} (2) = \infty . \end{aligned}$$

Proof

Let ${\mathfrak {C}}$ be a monster model for T. Towards a contradiction, suppose there exists $(I, f_A)_{A \in {\textbf{G}} }$ a ${\textbf{G}}$-configuration into ${\mathfrak {C}}$. Fix $n < \omega$ such that I(E) mentions only $R_i$ for $i < n$. By quanitifier elimination, there exists $S \subseteq {}^n 2$ such that

$$\begin{aligned} I(E)(y_0, y_1) = \bigvee _{s \in S} \bigwedge _{i < n} R_i(y_0, y_1)^{s(i)}. \end{aligned}$$

By swapping E with $\lnot E$ if necessary, we may assume the constant zero function is not in S. If we consider a finite complete graph A, then $f_A(A)$ can be viewed as a complete graph with edge colors in S. By Ramsey’s Theorem, for sufficiently large A, there exists a triangle of a fixed color $s_0 \in S$. By assumption, there exists $i_0 < n$ such that $s_0(i_0) = 1$, so this is an $R_{i_0}$-triangle. This is a contradiction.

Fix an arbitrary $m < \omega$ and define, for each $i < m$, L-formulas as follows:

$$\begin{aligned} I(E_i)(y_{0,0}, y_{0,1}, y_{1,0}, y_{1,1}) = R_i(y_{0,0}, y_{1,1}) \wedge R_i(y_{0,1}, y_{1,0}). \end{aligned}$$

For any $A \in {\textbf{G}} ^{*m}$, there exists a function $f_A : A \rightarrow {\mathfrak {C}} ^2$ such that, for all $a, b \in A$ and $i < m$,

$$\begin{aligned} A \models E_i(a,b) \Longleftrightarrow {\mathfrak {C}} \models I(E_i)(f_A(a), f_A(b)). \end{aligned}$$

That is, $(I, f_A)_{A \in {\textbf{G}} ^{*m}}$ is a ${\textbf{G}} ^{*m}$-configuration into ${\mathfrak {C}} ^2$. $\square$

6.4 Into the random graph

In this subsection, we study the specific case where the target theory is the theory of the random graph. It turns out that ${\textbf{K}}$-rank, for various examples of ${\textbf{K}}$, acts in an interesting manner in this theory.

For this subsection, let T be the theory of the random graph in the language L with a single binary relation R and let ${\mathfrak {C}}$ be a monster model for T. Let ${\textbf{K}}$ be a strong amalgamation Fraïssé class in a language $L_0$ with a single binary relation symbol, E. For any $m \ge 1$, let $L_m$ be the language of ${\textbf{K}} ^{*m}$, which consists of m binary relation symbols; call them $E_i$ for $i < m$. Let $\Gamma$ be the Fraïssé limit of ${\textbf{K}} ^{*m}$.

Fix $n \ge 1$ and, for each $t < 2$, consider the set $X_t = n \times \{ t \}$. Let ${\mathcal {G}} ^n$ be the set of bipartite graphs with parts $X_0$ and $X_1$. Then, $| {\mathcal {G}} ^n | = 2^{n^2}$. Say that $G = (X_0 \cup X_1, F) \in {\mathcal {G}} ^n$ is symmetric if, whenever $\{ (i,0),(j,1) \} \in F$, $\{ (j,0), (i,1) \} \in F$. Let ${\mathcal {G}}_{\textrm{s}} ^n$ be the set of symmetric bipartite graphs with parts $X_0$ and $X_1$ and let ${\mathcal {G}}_{\textrm{ns}} ^n$ be the set of non-symmetric bipartite graphs with parts $X_0$ and $X_1$. Notice that $|{\mathcal {G}}_{\textrm{s}} ^n| = 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) }$. To see this, observe that, for each $i \le j < n$, we can choose whether or not to put $\{ (i,0),(j,1) \}, \{ (j,0), (i,1) \} \in F$. This gives us $\left( {\begin{array}{c}n\\ 2\end{array}}\right) + n = \left( {\begin{array}{c}n+1\\ 2\end{array}}\right)$ choices. Thus,

$$\begin{aligned} | {\mathcal {G}}_{\textrm{ns}} ^n | = 2^{n^2} - 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) } = 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) } \left( 2^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) } - 1 \right) . \end{aligned}$$

For each $G \in {\mathcal {G}} ^n$, let $G^*$ be the graph where we “swap parts” (i.e., $\{ (i,0), (j,1) \}$ is an edge of G if and only if $\{ (j,0), (i,1) \}$ is an edge of $G^*$). Clearly $(G^*)^* = G$ and, for all $G \in {\mathcal {G}} ^n$, $G \in {\mathcal {G}}_{\textrm{s}} ^n$ if and only if $G^* = G$.

Let ${\mathcal {S}} _2$ denote the set of all quantifier-free 2-$L_m$-types over $\emptyset$, $p(x_0, x_1)$, such that $(a_0, a_1) \models p$ for some distinct $a_0, a_1 \in \Gamma$. For $p \in {\mathcal {S}} _2$, let $p^*$ be the type in ${\mathcal {S}} _2$ such that, for all $i < m$,

$$\begin{aligned} p^*(x_0, x_1) \vdash E_i(x_0, x_1) \Longleftrightarrow p(x_0, x_1) \vdash E_i(x_1, x_0). \end{aligned}$$

The next three propositions give conditions on ${\textbf{K}}$ that guarantee that $\textrm{Rk} _{\textbf{K}} (n) = n^2 - 1$ for $n \ge 2$. These conditions are met by $\textbf{LO}$, ${\textbf{G}}$, and ${\textbf{T}}$.

Proposition 6.19

Fix $n \ge 1$. Assume that ${\textbf{K}}$ is either reflexive or irreflexive. Assume also that ${\textbf{K}}$ is either symmetric or trichotomous. Then,

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (n) \ge n^2 - 1. \end{aligned}$$

Moreover, this is witnessed by a parameter-free configuration.

Proof

We may assume $n \ge 2$, since the statement is trivial when $n = 1$.

Let $m = n^2 - 1$ and let ${\overline{y}}$ be an n-tuple of variables from T. Consider the function $g : {\mathcal {S}} _2 \rightarrow {}^m 2$ where, for all $p \in {\mathcal {S}} _2$ and $i < m$,

$$\begin{aligned} g(p)(i) = 1 \Longleftrightarrow p(x_0, x_1) \vdash E_i(x_0, x_1). \end{aligned}$$

Since ${\textbf{K}}$ is symmetric or trichotomous and ${\textbf{K}}$ is reflexive or irreflexive, g is injective. Thus, $|{\mathcal {S}} _2| \le 2^m$.

Choose any injective function $h : {\mathcal {S}} _2 \rightarrow {\mathcal {P}} ({\mathcal {G}} ^n)$ with the following conditions:

• (1) If ${\textbf{K}}$ is symmetric, then, for all $p \in {\mathcal {S}} _2$, $h(p) = \{ G, G^* \}$ for some $G \in {\mathcal {G}} ^n$.

• (2) If ${\textbf{K}}$ is trichotomous, then, for all $p \in {\mathcal {S}} _2$, $h(p) = \{ G \}$ for some $G \in {\mathcal {G}}_{\textrm{ns}} ^n$ and $h(p^*) = (h(p))^*$.

To see that such an h exists, we have to consider two cases:

• Case 1. ${\textbf{K}}$ is symmetric.

In this case, the number of allowed outputs for h is

$$\begin{aligned} | {\mathcal {G}}_{\textrm{s}} ^n | + \frac{1}{2} | {\mathcal {G}}_{\textrm{ns}} ^n |&= 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) } + \frac{1}{2} \left( 2^{n^2} - 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) } \right) \\&= 2^{n^2-1} + 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) - 1} \ge 2^{n^2 - 1}. \end{aligned}$$

• Case 2. ${\textbf{K}}$ is trichotomous.

In this case, the number of allowed outputs for h is

$$\begin{aligned} | {\mathcal {G}}_{\textrm{ns}} ^n | = 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) } \left( 2^{\left( {\begin{array}{c}n\\ 2\end{array}}\right) } - 1 \right) \ge 2^{n^2 - 1}. \end{aligned}$$

In either case, the number of allowed outputs for h is at least

$$\begin{aligned} 2^{n^2-1} = 2^m \ge | {\mathcal {S}} _2 |. \end{aligned}$$

Therefore, such a function h exists.

For each $G = (X_0 \cup X_1, F) \in {\mathcal {G}} ^n$, let

$$\begin{aligned} \varphi _G(y_{0,0}, \dots , y_{0,n-1}, y_{1,0}, \dots , y_{1,n-1}) = \bigwedge _{ i, j < n } R(y_{0,i}, y_{1,j})^{\text {iff } \{ (i,0), (j,1) \} \in F}. \end{aligned}$$

Finally, for each $i < m$, let

$$\begin{aligned} I(E_i)({\overline{y}} _0, {\overline{y}} _1) = \bigvee _{p \in {\mathcal {S}} _2, p(x_0, x_1) \vdash E_i(x_0, x_1)} \left( \bigvee _{G \in h(p)} \varphi _G({\overline{y}} _0, {\overline{y}} _1) \right) . \end{aligned}$$

For any $A \in {\textbf{K}} ^{*m}$, consider the set $n \times A$ and endow it with an R-graph structure as follows: For all distinct $a, b \in A$, choose some $G = (X_0 \cup X_1, F) \in h(\textrm{qftp} _{L_0}(a,b))$. For all $i, j < n$, define

$$\begin{aligned} R((i, a), (j, b)) \Longleftrightarrow \{ (i,0), (j,1) \} \in F \end{aligned}$$

and add no other R-edges among $n \times \{ a, b \}$. Since ${\mathfrak {C}}$ is a model of the random graph, this R-structure on $n \times A$ embeds into ${\mathfrak {C}}$, say via $g : (n \times A) \rightarrow {\mathfrak {C}}$. Define $f_A : A \rightarrow {\mathfrak {C}} ^n$ by setting $f_A(a) = ( g(i,a) )_{i < n}$. Then, it is clear that, for all $a, b \in A$ and $i < m$,

$$\begin{aligned} A \models E_i(a,b) \Longleftrightarrow \models I(E_i)(f_A(a), f_A(b)). \end{aligned}$$

Thus, $(I, f_A)_{A \in {\textbf{K}} ^{*m}}$ is a ${\textbf{K}} ^{*m}$-configuration into ${\overline{y}} = {\overline{y}}$. Moreover, notice that this gives us a parameter-free configuration. $\square$

Proposition 6.20

Fix $n \ge 1$. Assume that ${\textbf{K}}$ is definably self-similar and fully relational. Then,

$$\begin{aligned} \textrm{Rk} _{\textbf{K}} (n) \le n^2. \end{aligned}$$

Proof

Fix $m \ge 1$ and let ${\overline{y}}$ be an n-tuple of variables from T. Suppose that there exists a ${\textbf{K}} ^{*m}$-configuration into ${\overline{y}} = {\overline{y}}$. By Proposition 3.16, since ${\textbf{K}}$ is definably self-similar, ${\textbf{K}} ^{*m}$ is definably self-similar. Since ${\textbf{K}} ^{*m}$ is definably self-similar, we may assume that there exist I, f, and J satisfying the conclusion of Proposition 4.15. That is, $I : \textrm{sig} (L_0) \rightarrow L({\mathfrak {C}} )$, $f : \Gamma \rightarrow {\mathfrak {C}} ^n$, and $J \subseteq |{\overline{y}} |$ are such that

• (1) for all $i < m$, for all $a,b \in \Gamma$, $\Gamma \models E_i(a,b)$ if and only if ${\mathfrak {C}} \models I(E_i)(f(a), f(b))$;

• (2) for all $a, b \in \Gamma$, $\textrm{tp} _L(f(a) / C) = \textrm{tp} _L(f(b) / C)$;

• (3) for all $j \in J$ and all $a, b \in \Gamma$, $f(a)_j = f(b)_j$; and

• (4) for all $p \in {\mathcal {S}} _2$, there exist $a_p, b_p \in \Gamma$ such that $(a_p, b_p) \models p$ and, for all $i, j \in |{\overline{y}} | \setminus J$, $f(a_p)_i \ne f(b_p)_j$.

Since L is a binary language, condition (2) tells us that the type $\textrm{tp} _L(f(a_p), f(b_p))$ determines the type $\textrm{tp} _L(f(a_p), f(b_p) / C)$.

We get a function $h : {\mathcal {S}} _2 \rightarrow {\mathcal {G}} ^n$ as follows: Fix $p \in {\mathcal {S}} _2$. For all $i, j < n$, we put $\{ (i,0), (j,1) \}$ in the edge set of h(p) if and only if $R(f(a_p)_i, f(b_p)_j)$. If we have $p, p' \in {\mathcal {S}} _2$ distinct, then $\textrm{tp} _L(f(a_p), f(b_p))$ and $\textrm{tp} _L(f(a_{p'}), f(b_{p'}))$ disagree on some formula of the form $R(y_{0,i}, y_{1,j})$. Therefore, $h(p) \ne h(p')$. Hence, h is injective.

Since ${\textbf{K}}$ is fully relational, by Proposition 3.23, ${\textbf{K}} ^{*m}$ is fully relational. Thus, $| {\mathcal {S}} _2 | \ge 2^m$. On the other hand, $| {\mathcal {G}} ^n | = 2^{n^2}$. Therefore, $2^m \le 2^{n^2}$. Thus, $m \le n^2$. $\square$

Proposition 6.21

Assume that ${\textbf{K}}$ is either reflexive or irreflexive. Assume that ${\textbf{K}}$ is definably self-similar and fully relational.

• (1) If ${\textbf{K}}$ is trichotomous, then $\textrm{Rk} _{\textbf{K}} (n) < n^2$ if $n \ge 1$.

• (2) If ${\textbf{K}}$ is symmetric, then $\textrm{Rk} _{\textbf{K}} (n) < n^2$ if $n \ge 2$.

Proof

Fix $m \ge 1$ and $n \ge 1$. Let $h : {\mathcal {S}} _2 \rightarrow {\mathcal {G}} ^n$ be the injective function from the proof of Proposition 6.20 and consider the map $p \mapsto (a_p, b_p)$ from that proof. We will show that h is not surjective.

• Case 1. ${\textbf{K}}$ is trichotomous.

If $p \in {\mathcal {S}} _2$, then

$$\begin{aligned} \textrm{tp} _L(f(a_p), f(b_p)) \ne \textrm{tp} _L(f(b_p), f(a_p)). \end{aligned}$$

Otherwise, $\textrm{tp} _L(f(a_p), f(b_p) / C) = \textrm{tp} _L(f(b_p), f(a_p) / C)$, hence $E_i(a_p,b_p)$ if and only if $E_i(b_p,a_p)$ for all $i < m$, which is a contradiction. Thus, $h(p) \in {\mathcal {G}}_{\textrm{ns}} ^n \subsetneq {\mathcal {G}} ^n$.

• Case 2. ${\textbf{K}}$ is symmetric and $n \ge 2$.

If $p, p' \in {\mathcal {S}} _2$ are distinct, then

$$\begin{aligned} \textrm{tp} _L(f(a_p), f(b_p)) \ne \textrm{tp} _L(f(b_{p'}), f(a_{p'})). \end{aligned}$$

Otherwise, $\textrm{tp} _L(f(a_p), f(b_p) / C) = \textrm{tp} _L(f(b_{p'}), f(a_{p'}) / C)$, hence $E_i(a_p,b_p)$ if and only if $E_i(b_{p'},a_{p'})$ if and only if $E_i(a_{p'},b_{p'})$ for all $i < m$, which is a contradiction. Since $n \ge 2$, ${\mathcal {G}}_{\textrm{ns}} ^n \ne \emptyset$. If $p, p' \in {\mathcal {S}} _2$ are distinct and $h(p) \in {\mathcal {G}}_{\textrm{ns}} ^n$, then $h(p) \ne (h(p'))^*$.

In either case, we see that h is not surjective. Therefore,

$$\begin{aligned} 2^m \le | {\mathcal {S}} _2 | < | {\mathcal {G}} ^n | = 2^{n^2}. \end{aligned}$$

So $m < n^2$. $\square$

We apply Propositions 6.19, 6.20, and 6.21 to $\textbf{LO}$, ${\textbf{G}}$, and ${\textbf{T}}$.

Example 6.22

(${\textbf{K}} = \textbf{LO}$) For all $n \ge 1$,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (n) = n^2 - 1. \end{aligned}$$

Proof

Since $\textbf{LO}$ is irreflexive and trichotomous, Proposition 6.19 gives us that $\textrm{Rk} _\textbf{LO} (n) \ge n^2 - 1$. Moreover, $\textbf{LO}$ is definably self-similar and fully relational, so Proposition 6.21 gives us that $\textrm{Rk} _\textbf{LO} (n) < n^2$. $\square$

Example 6.23

(${\textbf{K}} = {\textbf{T}}$) For all $n \ge 1$,

$$\begin{aligned} \textrm{Rk} _{\textbf{T}} (n) = n^2 - 1. \end{aligned}$$

Proof

Similar to Example 6.22. $\square$

In this paper, although the focus is not on ${\textbf{T}}$-rank, we do get this result “for free.” In future work, we may examine ${\textbf{T}}$-rank in other contexts.

Example 6.24

(${\textbf{K}} = {\textbf{G}}$) For all $n \ge 1$,

$$\begin{aligned} \textrm{Rk} _{\textbf{G}} (n) = {\left\{ \begin{array}{ll} 1 &{} \text { if } n = 1, \\ n^2 - 1 &{} \text { if } n \ge 2 \end{array}\right. }. \end{aligned}$$

Proof

Since ${\textbf{G}}$ is irreflexive and symmetric, Proposition 6.19 gives us that $\textrm{Rk} _{\textbf{G}} (n) \ge n^2 - 1$. Moreover, ${\textbf{G}}$ is definably self-similar and fully relational, so Proposition 6.21 gives us that $\textrm{Rk} _{\textbf{G}} (n) < n^2$ for $n \ge 2$. To see that $\textrm{Rk} _{\textbf{G}} (1) = 1$, use Proposition 6.20 and Lemma 4.4. $\square$

We now turn our attention to when ${\textbf{K}} = {\textbf{E}}$. This will take more work because ${\textbf{E}}$ is not definably self-similar.

For $t \in {}^m 2$ and ${\overline{a}} , {\overline{b}} \in \omega ^m$, we say that ${\overline{a}} \le _t {\overline{b}}$ if, for all $i < m$,

• $a_i < b_i$ if $t(i) = 1$ and

• $a_i = b_i$ if $t(i) = 0$.

Observe that, for any ${\overline{a}} , {\overline{b}} \in \omega ^m$, there exists at most one $t \in {}^m 2$ such that ${\overline{a}} \le _t {\overline{b}}$.

For positive integers m and n, consider the following property, which turns out to be implied by the existence of an ${\textbf{E}} ^{*m}$-configuration into ${\mathfrak {C}} ^n$:

$(\dagger )_{m,n}$: There exists a function $f : \omega ^m \rightarrow {\mathfrak {C}} ^n$ such that, for all $t, t' \in {}^m 2$, for all ${\overline{a}} , {\overline{b}} , {\overline{a}} ', {\overline{b}} ' \in \omega ^m$ with ${\overline{a}} \le _t {\overline{b}}$ and ${\overline{a}} ' \le _{t'} {\overline{b}} '$,

$$\begin{aligned} \textrm{tp} _L(f({\overline{a}} ), f({\overline{b}} )) = \textrm{tp} _L(f({\overline{a}} '), f({\overline{b}} ')) \Longleftrightarrow t = t'. \end{aligned}$$

In particular, when $t = t'$, $f({\overline{a}} )_\ell = f({\overline{b}} )_\ell$ if and only if $f({\overline{a}} ')_\ell = f({\overline{b}} ')_\ell$ for each $\ell < n$. Moreover, by choosing the constantly zero function for t, we see that the function ${\overline{a}} \mapsto \textrm{tp} _L(f({\overline{a}} ))$ is constant. Restricting to $2^m \subseteq \omega ^m$, we see that, for all ${\overline{a}} , {\overline{b}} \in 2^m$,

$$\begin{aligned} \textrm{tp} _L(f({\overline{0}} ), f({\overline{a}} )) = \textrm{tp} _L(f({\overline{0}} ), f({\overline{b}} )) \Longleftrightarrow {\overline{a}} = {\overline{b}} . \end{aligned}$$

(2)

As advertised, we get the following lemma.

Lemma 6.25

If there exists an ${\textbf{E}} ^{*m}$-configuration into ${\mathfrak {C}} ^n$, then $(\dagger )_{m,n}$ holds.

Proof

Let $(I, f_A)_{A \in {\textbf{E}} ^{*m}}$ be a ${\textbf{E}} ^{*m}$-configuration into ${\mathfrak {C}} ^n$ over $C \subseteq {\mathfrak {C}}$ finite. Fix $k < \omega$. By Lemma A.1, there exists $n < \omega$ such that, for all $c : \left( {\begin{array}{c}n^m\\ \le 2\end{array}}\right) \rightarrow S^L_{2n}(C)$, there exist $Y_0, \dots , Y_{m-1} \in \left( {\begin{array}{c}n\\ k\end{array}}\right)$ such that, for all $t \in {}^m 2$, c is constant on

$$\begin{aligned} X_t = \left\{ \{ {\overline{a}} , {\overline{b}} \} : {\overline{a}} , {\overline{b}} \in \prod _{i < m} Y_i, {\overline{a}} \le _t {\overline{b}} \right\} . \end{aligned}$$

Let $A = n^{m+1}$ be the $L_m$-structure given in Lemma 3.18. In particular, this holds for the coloring c given by, for all ${\overline{a}} , {\overline{b}} \in n^m$ with ${\overline{a}} \le _\textrm{lex} {\overline{b}}$,

$$\begin{aligned} c(\{ {\overline{a}} , {\overline{b}} \}) = \textrm{tp} _L( f_A({\overline{a}} , 0), f_A({\overline{b}} , 0) / C). \end{aligned}$$

As k was arbitrary, by compactness, there exists $f : \omega ^m \rightarrow {\mathfrak {C}} ^n$ such that, for all ${\overline{a}} , {\overline{b}} \in \omega ^m$ and $i < m$, ${\mathfrak {C}} \models I(E_i)(f({\overline{a}} ), f({\overline{b}} ))$ if and only if $a_i = b_i$ and, for all $t \in {}^m 2$, the function $({\overline{a}} , {\overline{b}} ) \mapsto \textrm{tp} _L(f({\overline{a}} ), f({\overline{b}} ) / C)$ is constant for all ${\overline{a}} , {\overline{b}} \in \omega ^m$ with ${\overline{a}} \le _t {\overline{b}}$. In particular, the function ${\overline{a}} \mapsto \textrm{tp} _L(f({\overline{a}} ) / C)$ is constant. Since L is a binary language, the type $\textrm{tp} _L(f({\overline{a}} ), f({\overline{b}} ) / C)$ is determined by the type $\textrm{tp} _L(f({\overline{a}} ), f({\overline{b}} ))$. Therefore, f witnesses that $(\dagger )_{m,n}$ holds.

$\square$

Suppose $(\dagger )_{m,n}$ holds for some $n, m < \omega$, witnessed by f. Let ${\overline{e}} _i$ be the ith standard basis vector. For each $\ell < n$, let

$$\begin{aligned} V_\ell = \left\{ {\overline{a}} \in \omega ^m : f({\overline{0}} )_\ell = f({\overline{a}} )_\ell \right\} . \end{aligned}$$

Lemma 6.26

There exists $I_\ell \subseteq m$ such that

$$\begin{aligned} V_\ell = \{ {\overline{a}} \in \omega ^m : (\forall i \in m \setminus I_\ell )[ a_i = 0 ] \} \end{aligned}$$

In other words, $V_\ell$ is the $\omega$-span of $\{ {\overline{e}} _i : i \in I_\ell \}$.

Proof

Let $I_\ell = \{ i < m : (\exists {\overline{a}} \in V_\ell )[ a_i > 0 ] \}$. We show this works.

Clearly ${\overline{0}} \in V_\ell$. Fix ${\overline{a}} \in V_\ell$ non-zero and $i < m$ such that $a_i > 0$. Notice that, for all $t \in {}^m 2$,

$$\begin{aligned} {\overline{0}} \le _t {\overline{a}} \Longleftrightarrow {\overline{0}} \le _t {\overline{a}} + {\overline{e}} _i. \end{aligned}$$

By $(\dagger )_{m,n}$, since $f({\overline{0}} )_\ell = f({\overline{a}} )_\ell$, $f({\overline{0}} )_\ell = f({\overline{a}} + {\overline{e}} _i)_\ell$. Thus, $f({\overline{a}} )_\ell = f({\overline{a}} + {\overline{e}} _i)_\ell$. By $(\dagger )_{m,n}$, $f({\overline{0}} )_\ell = f({\overline{e}} _i)_\ell$. Thus, ${\overline{e}} _i \in V_\ell$.

Suppose that ${\overline{a}} , {\overline{b}} \in V_\ell$. Then,

$$\begin{aligned} f({\overline{0}} )_\ell = f({\overline{a}} )_\ell \text { and } f({\overline{0}} )_\ell = f({\overline{b}} )_\ell . \end{aligned}$$

By $(\dagger )_{m,n}$, $f({\overline{a}} )_\ell = f({\overline{a}} + {\overline{b}} )_\ell$. Therefore, ${\overline{a}} + {\overline{b}} \in V_\ell$.

Putting these facts together, we get the desired conclusion. $\square$

Lemma 6.27

Suppose $(\dagger )_{m,n}$ holds, witnessed by f. For all $\ell , \ell ' < n$ and ${\overline{a}} \in \omega ^m$, if $f({\overline{0}} )_\ell = f({\overline{a}} )_{\ell '}$, then ${\overline{a}} \in V_\ell \cap V_{\ell '}$.

Proof

By $(\dagger )_{m,n}$, $f({\overline{0}} )_\ell = f(2 {\overline{a}} )_{\ell '}$, hence $f({\overline{a}} )_{\ell '} = f(2 {\overline{a}} )_{\ell '}$. By $(\dagger )_{m,n}$, $f({\overline{0}} )_{\ell '} = f({\overline{a}} )_{\ell '}$, hence ${\overline{a}} \in V_{\ell '}$. On the other hand, by $(\dagger )_{m,n}$, $f({\overline{a}} )_\ell = f(2 {\overline{a}} )_{\ell '}$, hence $f({\overline{0}} )_\ell = f({\overline{a}} )_\ell$. Thus, ${\overline{a}} \in V_\ell$. $\square$

We are now ready to compute $\textrm{Rk} _{\textbf{E}} (n)$.

Example 6.28

(${\textbf{K}} = {\textbf{E}}$) For all $n \ge 1$,

$$\begin{aligned} \textrm{Rk} _{\textbf{E}} (n) = {\left\{ \begin{array}{ll} 1 &{} \text { if } n = 1, \\ n^2 - 1 &{} \text { if } n \ge 2 \end{array}\right. }. \end{aligned}$$

Proof

Since ${\textbf{E}}$ is reflexive and symmetric, Proposition 6.19 says that $\textrm{Rk} _{\textbf{E}} (n) \ge n^2 - 1$. Moreover, Proposition 6.13 says that $\textrm{Rk} _{\textbf{E}} (1) \ge 1$.

Towards a contradiction, suppose $\textrm{Rk} _{\textbf{E}} (1) \ge 2$; hence, $(\dagger )_{2,1}$ holds, say witnessed by $f : \omega ^2 \rightarrow {\mathfrak {C}}$. By (2), this gives us at least four distinct 2-L-types over $\emptyset$. On the other hand, there are only three such types, a contradiction.

So it suffices to show that $\textrm{Rk} _{\textbf{E}} (n) < n^2$ when $n \ge 2$. To accomplish this, we prove, by induction on n, that $(\dagger )_{n^2,n}$ fails.

We will deal with the base case of $n = 2$ at the end. Fix $n \ge 3$ and assume that $(\dagger )_{(n-1)^2,n-1}$ fails. Towards a contradiction, suppose that $(\dagger )_{n^2,n}$ holds, say witnessed by $f : \omega ^{n^2} \rightarrow {\mathfrak {C}} ^n$.

Claim

For all $\ell < n$, $| I_\ell | < (n-1)^2$ (where $I_\ell$ is as defined in Lemma 6.26, for this choice of f).

Proof of Claim

Fix $\ell < n$. Towards a contradiction, suppose $| I_\ell | \ge (n-1)^2$. Let $m = (n-1)^2$, let $\sigma : m \rightarrow I_\ell$ be any injective function, and, for each ${\overline{a}} \in \omega ^m$, let ${\overline{a}} _\sigma \in \omega ^{n^2}$ be given by

$$\begin{aligned} a_{\sigma ,i} = {\left\{ \begin{array}{ll} a_j &{} \text { if } i = \sigma (j), \\ 0 &{} \text { if } i \notin \textrm{im} (\sigma ) \end{array}\right. }. \end{aligned}$$

In particular, ${\overline{a}} _\sigma \in V_\ell$. Hence, for all ${\overline{a}} , {\overline{b}} \in \omega ^m$, $f({\overline{a}} _\sigma )_\ell = f({\overline{b}} _\sigma )_\ell$. Define $f' : \omega ^m \rightarrow {\mathfrak {C}} ^{n-1}$ as follows: For each ${\overline{a}} \in \omega ^m$, let $f'({\overline{a}} ) = f({\overline{a}} _\sigma )$ restricted to exclude the $\ell$th coordinate. It is easy to check that $f'$ satisfies $(\dagger )_{m,n-1}$, contrary to the inductive hypothesis.

$\square$

Let $m = n^2$ and let

$$\begin{aligned} V = \left\{ {\overline{a}} \in 2^m : (\exists \ell < n)(\forall i \in m \setminus I_\ell )[ a_i = 0 ] \right\} . \end{aligned}$$

In other words, V is the union of $2^m \cap V_\ell$ over all $\ell < n$. By the claim, for each $\ell < n$, $|I_\ell | \le (n-1)^2 - 1 = n^2 - 2n$. Thus,

$$\begin{aligned} \left| 2^m \cap V_\ell \right| \le 2^{n^2 - 2n}. \end{aligned}$$

Therefore,

$$\begin{aligned} \left| 2^m \setminus V \right| \ge 2^{n^2} - n2^{n^2 - 2n}. \end{aligned}$$

Claim

$2^{n^2} - n2^{n^2 - 2n} > 2^{n^2 - 1} + 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) - 1}$.

Proof of Claim

Since $n \ge 3$, $(n+1)(n-1) > \frac{1}{2} n (n+1)$. Thus, $n^2 - 2 > \left( {\begin{array}{c}n+1\\ 2\end{array}}\right) - 1$. So

$$\begin{aligned} 2^{n^2 - 2} > 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) - 1}. \end{aligned}$$

Similarly, $(n+1)(n-1) > n(n-1)$. Thus, $n^2 - 2 > n^2 - n - 1$, so

$$\begin{aligned} 2^{n^2 - 2} > 2^{n-1} 2^{n^2 - 2n}. \end{aligned}$$

Since $n \ge 3$, $n < 2^{n-1}$. Therefore,

$$\begin{aligned} 2^{n^2 - 2} > n 2^{n^2 - 2n}. \end{aligned}$$

Putting these together, we get

$$\begin{aligned} 2^{n^2 - 1} > 2^{\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) - 1} + n 2^{n^2 - 2n}. \end{aligned}$$

This gives us the desired conclusion. $\square$

Therefore, by (2),

$$\begin{aligned} \left| \left\{ \textrm{tp} _L(f({\overline{0}} ), f({\overline{a}} )) : {\overline{a}} \in 2^m \setminus V \right\} \right| = | 2^m \setminus V | > | {\mathcal {G}}_{\textrm{s}} ^n | + \frac{1}{2} | {\mathcal {G}}_{\textrm{ns}} ^n |. \end{aligned}$$

However, by Lemma 6.27, for each ${\overline{a}} \in 2^m \setminus V$ and all $\ell , \ell ' < n$, $f({\overline{0}} )_\ell \ne f({\overline{a}} )_{\ell '}$. Hence, each type $\textrm{tp} _L(f({\overline{0}} ), f({\overline{a}} ))$ corresponds to a unique element of ${\mathcal {G}} ^n$ as in the proof of Proposition 6.20. Since ${\textbf{E}} ^{*m}$ is symmetric, as in the proof of Proposition 6.21, we conclude that there are at most $| {\mathcal {G}}_{\textrm{s}} ^n | + \frac{1}{2} | {\mathcal {G}}_{\textrm{ns}} ^n |$ such types. This is a contradiction.

For the base case, towards a contradiction, suppose that $(\dagger )_{4,2}$ holds. This argument proceeds similarly to the general inductive argument. Notice that, for all $\ell < 2$, $|I_\ell | \le 1$ (this follows from a similar argument to the first claim). Thus, $| 2^4 \setminus V | \ge 2^4 - 3 = 13$. On the other hand,

$$\begin{aligned} | {\mathcal {G}} ^2 | + \frac{1}{2} | {\mathcal {G}}_{\textrm{ns}} ^2 | = 12. \end{aligned}$$

$\square$

6.5 Ranks and the independence property

How do the ranks studied above interact with model-theoretic dividing lines (in particular, the independence property)?

As long as $\textbf{LO}$-rank is finite, $\textbf{LO}$-rank grows linearly if T has NIP and grows quadratically if T has the independence property.

Theorem 6.29

Let T be any complete first-order theory such that $\textrm{Rk} _\textbf{LO} (1) < \infty$.

• (1) If T has NIP, then there exists $C \in {\mathbb {R}}$ such that, for all $n \ge 1$,

  $$\begin{aligned} \textrm{Rk} _\textbf{LO} (n) \le Cn. \end{aligned}$$

• (2) If T has the independence property, then there exists $C \in {\mathbb {R}}$ such that, for sufficiently large n,

  $$\begin{aligned} \textrm{Rk} _\textbf{LO} (n) \ge Cn^2. \end{aligned}$$

Proof

(1): As noted in Example 6.10, if T has NIP, then $\textrm{Rk} _\textbf{LO}$ is additive. Thus, if we let $C = \textrm{Rk} _\textbf{LO} (1)$, $\textrm{Rk} _\textbf{LO} (n) = Cn$ for all $n \ge 1$.

(2): Assume that T has the independence property and ${\mathfrak {C}}$ is a monster model for T. By Theorem 5.2 (2) and Lemma 4.7, there exists an injective ${\textbf{G}}$-configuration into ${\mathfrak {C}} ^k$ for some $k < \omega$. Moreover, by Proposition 6.19, for all $m < \omega$, there exists a parameter-free $\textbf{LO} ^{*(m^2 - 1)}$-configuration into ${\mathfrak {C}} _1^m$, where ${\mathfrak {C}} _1$ is a monster model for the theory of the Fraïssé limit of ${\textbf{G}}$. By Proposition 4.13, there exists an $\textbf{LO} ^{*(m^2 - 1)}$-configuration into ${\mathfrak {C}} ^{km}$. Therefore,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (km) \ge m^2 - 1. \end{aligned}$$

For $n \ge k$, let $m = \lfloor n / k \rfloor$. Then, by Lemma 6.6,

$$\begin{aligned} \textrm{Rk} _\textbf{LO} (n) \ge \textrm{Rk} _\textbf{LO} (km) \ge m^2 - 1 \ge \frac{1}{k^2} n^2 - \frac{2}{k} n. \end{aligned}$$

$\square$

In the next few examples, we examine the applicability of the preceding theorem.

Example 6.30

Let T be a complete theory in some language L. Suppose that all indiscernible sequences of singletons are set indiscernible. By Remark 6.8, we can make any $\textbf{LO}$-configuration into an indiscernible one, so there exists no $\textbf{LO}$-configuration into singletons of T. Thus, $\textrm{Rk} _\textbf{LO} (1) = 0$. Therefore, for any such theory T, T has NIP if and only if there exists $C \in {\mathbb {R}}$ such that, for all $n \ge 1$, $\textrm{Rk} _\textbf{LO} (n) \le Cn$. This applies, for example, to the theory of the Fraïssé limit of any irreflexive, symmetric Fraïssé class in a finite relational language.

Example 6.31

Let L consist of infinitely many binary relation symbols $<_i$ for $i < \omega$ and let T be the model companion of the theory which says each $<_i$ is a linear order. Clearly T has quantifier elimination, so T has NIP. Thus, $\textbf{LO}$-rank and op-dimension coincide. Therefore, $\textrm{Rk} _\textbf{LO} (1) = \infty$. So, there are examples of NIP theories for which the theorem does not apply. If we replace “linear order” with “partial order” in the definition of T, we obtain an example of a theory with the independence property such that $\textrm{Rk} _\textbf{LO} (1) = \infty$.

Similar to $\textbf{LO}$-rank, if the target theory has the independence property and ${\textbf{E}}$-rank is finite, then ${\textbf{E}}$-rank necessarily grows quadratically.

Proposition 6.32

Let T be any complete first-order theory with the independence property such that $\textrm{Rk} _{\textbf{E}} (1) < \infty$. Then, there exists $C \in {\mathbb {R}}$ such that, for sufficiently large n,

$$\begin{aligned} \textrm{Rk} _{\textbf{E}} (n) \ge Cn^2. \end{aligned}$$

Proof

This is similar to the proof of Theorem 6.29 (2).

$\square$

Similarly, in any theory with the independence property, so long as ${\textbf{G}}$-rank is finite, ${\textbf{G}}$-rank grows quadratically.

Proposition 6.33

If T is any theory and $\pi$ any partial type with $\textrm{Rk} _{\textbf{G}} (\pi ) \ge 1$, then

$$\begin{aligned} \textrm{Rk} _{\textbf{G}} (\pi ^{\times n}) \ge n^2 - 1. \end{aligned}$$

Proof

This is similar to the proof of Theorem 6.29 (2).

$\square$

From Theorem 6.29, Proposition 6.32, and Proposition 6.33, we obtain the following result about additivity of ranks: If T has the independence property, ${\textbf{K}} = {\textbf{E}}$, $\textbf{LO}$, or ${\textbf{G}}$, and ${\textbf{K}}$-rank is finite, then ${\textbf{K}}$-rank is not additive.

7 Future work

From the study of ${\textbf{K}}$-configurations and ${\textbf{K}}$-rank in the previous sections, we are left with a few open questions.

Question 7.1

Under what conditions is ${\textbf{K}}$-rank a generalization of a known rank in model theory?

In Example 6.10, we establish that $\textbf{LO}$-rank coincides with op-dimension when T has NIP, which implies that $\textbf{LO}$-rank coincides with dp-rank when T is distal. On the other hand, $\textbf{LO}$-rank diverges from op-dimension when T has the independence property. Similarly, ${\textbf{E}}$-rank appears to be related to dp-rank, but the exact relationship remains unclear. Proposition 6.12 establishes that dp-rank is an upper bound for ${\textbf{E}}$-rank while Corollary 6.14 shows that these ranks coincide on ${\mathfrak {C}} ^n$ when T is dp-minimal. On the other hand, even in NIP theories, dp-rank and ${\textbf{E}}$-rank diverge, as shown in Example 6.16. This example is distal, however, which leads to an interesting question

Question 7.2

Do dp-rank and ${\textbf{E}}$-rank coincide for stable theories?

Along a similar line, when is ${\textbf{K}}$-rank additive (Question 6.4)? We see that $\textbf{LO}$-rank, and even ${\textbf{G}}$-rank (trivially), are additive when T has NIP. On the other hand, these ranks fail additivity when moving to theories with the independence property. Is it possible that, more generally, ${\textbf{K}}$-ranks are additive on NIP theories? In particular, is ${\textbf{E}}$-rank additive on NIP theories?

Although we examined a few examples of strong amalgamation Fraïssé classes in this paper, there are other classes that are currently unexplored. We have one result on ${\textbf{T}}$-rank, Example 6.23, and no results on ${\textbf{H}} _k$-rank for $k > 2$. It is possible, for example, that ${\textbf{T}}$-rank coincides with $\textbf{LO}$-rank for some types. Most of the technology developed in this paper relies on the index language being binary, which makes analyzing ${\textbf{H}} _k$-rank more challenging when $k > 2$. In future work, we would like to examine ${\textbf{K}}$-rank for these and other classes, ${\textbf{K}}$.

Finally, Sect. 5 and the relationships to [7] reveal other interesting open questions. For example, we have the strict $\lesssim$-chain

$$\begin{aligned} {\textbf{E}}< \textbf{LO}< {\textbf{G}}< {\textbf{H}} _3< {\textbf{H}} _4 < \dots . \end{aligned}$$

This leads to the following question

Question 7.3

Is $\lesssim$ a linear quasi-order on strong amalgamation Fraïssé classes? In particular, are there any classes strictly between ${\textbf{E}}$ and $\textbf{LO}$?

In other words, is there a non-trivial dividing line, in the sense of ${\mathcal {C}} _{\textbf{K}}$, below stability?

Appendix A. Combinatorial lemmas

Fix $k < \omega$ and let

$$\begin{aligned} {\mathcal {D}} _k = \{ t \in {}^k \{ -1, 0, 1 \} : t(i) = 1 \text { for } i \text { minimal such that } t(i) \ne 0 \}. \end{aligned}$$

For ${\overline{a}} , {\overline{b}} \in \omega ^k$ and $t \in {\mathcal {D}} _k$, define

$$\begin{aligned} {\overline{a}} \le _t {\overline{b}} \text { if, for all } i< k, {\left\{ \begin{array}{ll} a_i < b_i &{} \text { if } t(i) = 1, \\ a_i = b_i &{} \text { if } t(i) = 0, \\ a_i > b_i &{} \text { if } t(i) = -1. \end{array}\right. } \end{aligned}$$

Finally, for all ${\overline{a}} , {\overline{b}} \in \omega ^k$, define

$$\begin{aligned} {\overline{a}} \le _\textrm{lex} {\overline{b}} \text { if } a_i < b_i \text { for } i \text { minimal such that } a_i \ne b_i. \end{aligned}$$

Note that ${\overline{a}} \le _\textrm{lex} {\overline{b}}$ if and only if there exists $t \in {\mathcal {D}} _k$ such that ${\overline{a}} \le _t {\overline{b}}$.

Lemma A.1

For all $k, \ell , m < \omega$, there exists $n < \omega$ such that, for all colorings $c : \left( {\begin{array}{c}n^k\\ \le 2\end{array}}\right) \rightarrow \ell$, there exist $Y_0, \dots , Y_{k-1} \in \left( {\begin{array}{c}n\\ m\end{array}}\right)$ such that, for all $t \in {\mathcal {D}} _k$, c is constant on the set

$$\begin{aligned} X_t = \left\{ \{ {\overline{a}} , {\overline{b}} \} : {\overline{a}} , {\overline{b}} \in \prod _{i < k} Y_i, {\overline{a}} \le _t {\overline{b}} \right\} . \end{aligned}$$

Proof

By induction on k. Let $k = 1$ and fix $\ell , m < \omega$. By Ramsey’s Theorem, there exists n such that, for all colorings $c : \left( {\begin{array}{c}n\\ \le 2\end{array}}\right) \rightarrow \ell$, there exists $Y \in \left( {\begin{array}{c}n\\ m\end{array}}\right)$ such that c is constant on $\left( {\begin{array}{c}Y\\ 1\end{array}}\right)$ and c is constant on $\left( {\begin{array}{c}Y\\ 2\end{array}}\right)$. Since $X_0 = \left( {\begin{array}{c}Y\\ 1\end{array}}\right)$ and $X_{1} = \left( {\begin{array}{c}Y\\ 2\end{array}}\right)$, this is the desired conclusion.

Fix $k, m, \ell < \omega$. Let

$$\begin{aligned} \ell ' = {}^{{\mathcal {D}} _k \times \{ -1, 1 \}} \ell . \end{aligned}$$

By Ramsey’s Theorem, there exists $n' < \omega$ such that, for all colorings $c' : \left( {\begin{array}{c}n'\\ \le 2\end{array}}\right) \rightarrow \ell '$, there exists $Y_k \in \left( {\begin{array}{c}n'\\ m\end{array}}\right)$ such that $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 1\end{array}}\right)$ and $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 2\end{array}}\right)$. Let

$$\begin{aligned} \ell '' = {}^{(n')^2} \ell . \end{aligned}$$

By the inductive hypothesis, there exists $n'' < \omega$ such that, for all colorings $c'' : \left( {\begin{array}{c}(n'')^k\\ \le 2\end{array}}\right) \rightarrow \ell ''$, there exist $Y_0, \dots , Y_{k-1} \in \left( {\begin{array}{c}n''\\ m\end{array}}\right)$ such that, for all $t \in {\mathcal {D}} _k$, $c''$ is constant on $X_t$. Let $n = \max \{ n', n'' \}$.

Fix a coloring $c : \left( {\begin{array}{c}n^{k+1}\\ \le 2\end{array}}\right) \rightarrow \ell$. This induces a coloring $c'' : \left( {\begin{array}{c}(n'')^k\\ \le 2\end{array}}\right) \rightarrow \ell ''$ given by: for each ${\overline{a}} , {\overline{b}} \in (n'')^k$ with ${\overline{a}} \le _\textrm{lex} {\overline{b}}$, for each $i, j \in n'$, let

$$\begin{aligned} c''( \{ {\overline{a}} , {\overline{b}} \} )(i, j) = c( \{ {\overline{a}} {}^{\frown } i, {\overline{b}} {}^{\frown } j \} ). \end{aligned}$$

Thus, there exist $Y_0, \dots , Y_{k-1} \in \left( {\begin{array}{c}n''\\ m\end{array}}\right)$ such that, for all $t \in {\mathcal {D}} _k$, $c''$ is constant on $X_t$. Now define $c' : \left( {\begin{array}{c}n'\\ \le 2\end{array}}\right) \rightarrow \ell '$ as follows: for each $i \le j < n'$, $t \in {\mathcal {D}} _k$, and $s \in \{ -1, 1 \}$, choose ${\overline{a}} , {\overline{b}} \in \prod _{i < k} Y_i$ with ${\overline{a}} \le _t {\overline{b}}$ and set

$$\begin{aligned} c'( \{ i, j \} )(t,s) = {\left\{ \begin{array}{ll} c( \{ {\overline{a}} {}^{\frown } i, {\overline{b}} {}^{\frown } j \} ) &{} \text { if } s = 1, \\ c( \{ {\overline{a}} {}^{\frown } j, {\overline{b}} {}^{\frown } i \} ) &{} \text { if } s = -1. \end{array}\right. } \end{aligned}$$

Since $c''$ is constant on $X_t$ for each t, this function is independent of the choice of ${\overline{a}}$ and ${\overline{b}}$. Thus, there exists $Y_k \in \left( {\begin{array}{c}n'\\ m\end{array}}\right)$ such that $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 1\end{array}}\right)$ and $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 2\end{array}}\right)$. We claim that $Y_0, \dots , Y_k$ work for c.

Fix $t \in {\mathcal {D}} _{k+1}$. If $t(k)=0$, let

$$\begin{aligned} r = c'( \{ i \} )(t |_k, 1 ) \end{aligned}$$

for any choice of $i \in Y_k$. Since $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 1\end{array}}\right)$, this is independent of the choice of i. If $t(k) \ne 0$, let

$$\begin{aligned} r = c'( \{ i, j \})(t |_k, t(k)) \end{aligned}$$

for any choice of $i, j \in Y_k$ with $i < j$. Since $c'$ is constant on $\left( {\begin{array}{c}Y_k\\ 2\end{array}}\right)$, this is independent of the choice of i and j. Then, for any ${\overline{a}} , {\overline{b}} \in \prod _{i \le k} Y_i$ such that ${\overline{a}} \le _t {\overline{b}}$, we have that

$$\begin{aligned} c( \{ {\overline{a}} , {\overline{b}} \} ) = r. \end{aligned}$$

This is what we wanted to prove. $\square$

Corollary A.2

For all $k, \ell , m < \omega$, there exists $n < \omega$ such that, for all colorings $c : n^k \rightarrow \ell$, there exist $Y_0, \dots , Y_{k-1} \in \left( {\begin{array}{c}n\\ m\end{array}}\right)$ such that c is constant on $\prod _{i < k} Y_i$.

Proof

Since any coloring $c : n^k \rightarrow \ell$ can be extended arbitrarily to a coloring $c : \left( {\begin{array}{c}n^k\\ \le 2\end{array}}\right) \rightarrow \ell$, this follows immediately from Lemma A.1.

$\square$