# Planar graphs with separation are dp-minimal

J. de la Nuez González<EMAIL_ADDRESS>Korea Institute for Advanced
Study (KIAS)

###### Abstract.

We prove that given a planar embedding of a graph in the sphere the expansion
of the graph structure by predicates encoding separation of vertices by simple
cycles of the graph is dp-minimal.

##  1\. Introduction

The notion of an NIP theory is a central to classification theory. While it is
usually defined in terms of the absence of uniformly definable families of
sets shattering infinite families of tuples, an alternative characterization
can be given in terms of the boundedness of so called dp-rank (see [3] Section
4.2), which describes the behavior of collections of mutually indiscernible
sequences under the addition of parameters.

The aim of this note is to provide a family of simple geometrical examples of
non-stable theories that are dp-minimal, i.e. for which the dp-rank equals
one. We will assume the reader is familiar with indiscernible sequences and
other basics of model theory. We refer to [4] for a general introduction to
model theory and to [3] for an introduction to NIP theories. We work with
indiscernible sequences indexed by arbitrary infinite linear orders.

######  Definition 1.1.

Two indiscernible sequences $I=(a_{j})_{j\in J}$ and
$I^{\prime}=(a^{\prime}_{j})_{j\in J^{\prime}}$ are mutually indiscernible if
$I$ is indiscernible over $I^{\prime}$ and viceversa.

######  Definition 1.2.

A theory $T$ is dp-minimal if for any model of $M$ of $T$, any two mutually
indiscernible sequences of tuples $(a_{i}^{1})_{i\in J_{1}}$ and
$(a_{i}^{2})_{j\in J_{2}}$ and any element $b$ in $M$ there is $l\in\\{1,2\\}$
such that $(a_{i}^{l})_{i\in J_{l}}$ is indiscernible over $b$.

Fix a countable planar graph $G=(V,E)$ and consider a planar embedding
$\iota:|G|\to S^{2}$ of its geometric realization into the sphere. With
$\iota$ we associate an expansion $G^{\iota}$ of the graph structure $G$ as
follows. For each $n\in\mathbb{N}$ we introduce a new $(n+2)$-ary predicate
symbol $R_{n}$ and we let $G^{\iota}\models R_{n}(a,b,c_{1,},c_{2},\cdots
c_{n})$ if and only $c_{1},c_{2},\cdots c_{n}$ is the sequence of vertices
read along a simple cycle $\gamma$ of the graph, possibly with cyclically
contiguous repetitions, $\\{a,b\\}\cap\\{c_{1},c_{2},\cdots
c_{n}\\}=\emptyset$ and $\iota(a),\iota(b)$ lie on the same connected
component of $S^{2}\setminus\iota(|\gamma|)$.

We prove the following:

######  Theorem 1.3.

The theory $T=Th(G^{\iota})$ is dp-minimal

Note that the theory of a pure planar graph $G$ is known to be stable. In fact
[1] shows that much more in general the theory of any superflat graph is dp-
minimal. Superflat graphs are also long known to be stable (see [2]). The
structure $G^{\iota}$ in generally is not.

##  2\. Basic observations and definitions

From now on we will work in the monster model $\mathbb{G}^{\iota}$ of
$G^{\iota}$, the elements of whose universe we will keep referring to as
vertices. We will refer to a tuple $(c_{1},c_{2}\dots c_{n})$, possibly with
repetitions, read along a simple path in the graph as an $n$ cycle or simply a
cycle. If we drop the condition that $c_{1}$ and $c_{n}$ and connected we
obtain what we will call a path (so by a path we will always intend a simple
path). By a subpath of a path (cycle) we will intend some subsequence (of some
cyclic permutation) of it. Given an $n$-cycle $c$ and $a,b$ outside of $c$ we
say that $c$ does not separate $a$ and $b$ if $R_{n}(a,b,c)$ holds. We
abbreviate this with the expression $a\sim_{c}b$. We also write
$\mathbf{D}^{+}_{c}(a):=\\{b\,|\,a\sim_{c}b\\}$ and
$\mathbf{D}^{-}_{c}(a):=\\{b\,|\,a\nsim_{c}b\\}$.

Let us single out some basic properties encoded in $T$ resulting from the
definition of $G^{\iota}$:

  1. (A)

If $a_{1},a_{2}\cdots a_{m}$ is a path and $a_{1}\nsim_{c}a_{m}$ for some
cycle $c$, then there are $j<j^{\prime}\in\\{1,2,\dots n\\}$ such that
$j^{\prime}-j>1$, $a_{j},a_{j^{\prime}}\notin c$,
$a_{j}\nsim_{c}a_{j^{\prime}}$, and $a_{j+1},a_{j+2},\dots a_{j^{\prime}-1}$
is a subpath of $c$.

  2. (B)

Given two cycles $c_{1},c_{2}$ such that $c_{1}\setminus(c_{1}\cap c_{2})$
lies on a single side of $c_{2}$, then the same is true if we exchange the
roles of $c_{1}$ and $c_{2}$. If this is not the case, then we say that
$c_{1}$ and $c_{2}$ _cross_.

  3. (C)

If $c_{1}$ and $c_{2}$ do not cross, then $\sim_{c_{1},c_{2}}$ divides
$U\setminus c_{1}\cup c_{2}$ in at most three classes, i.e. there is one side
of $\gamma_{1}$ and another of $\gamma_{2}$ which are nested.

######  Remark 2.1.

By A if the intersection of $c_{1}$ and $c_{2}$ is a single path (in
particular, if it contains a single vertex), then $c_{2}$ and $c_{2}$ cannot
cross.

### Cages and nests

By a _cage_ $\mathcal{C}$ we intend a collection $(\gamma_{j})_{j\in J}$,
$|J|\geq 3$ of simple paths of bounded length between two distinct fixed
vertices $u$ and $v$, indexed by a linearly ordered set $J$ and such that the
following properties are satisfied:

  * •

$\gamma_{i}\cap\gamma_{j}=\\{u,v\\}$ for $i\neq j$ in $J$.

  * •

$\gamma_{i}\ast\gamma_{k}^{-1}$ separates $\gamma_{l}\setminus\\{u,v\\}$ from
$\gamma_{j}\setminus\\{u,v\\}$ if and only if up to exchanging $j$ and $l$ and
exchanging $i$ and $k$ either $i<j<k<l$ or $l<i<j<k$ .

Let $\mathcal{C}=(\gamma_{j})_{j\in J}$ be a cage. We will write
$pol(\mathcal{C})=\\{u,v\\}$,
$\mathring{\gamma}_{j}=\gamma_{j}\setminus\\{u,v\\}$ and from this point on
use the convention $\gamma_{i,k}$ to denote the path
$\gamma_{i}\ast\gamma_{k}^{-1}$.

We will also write $C_{j,k}=C_{k,j}=\mathbf{D}^{+}_{\gamma_{j,k}}(d)$, where
$d$ is some vertex of $\mathring{\gamma}_{l}$ for some $l$ between $j$ and
$k$, or $D^{-}_{\gamma_{j,k}}(d)$ where $d$ is some vertex of
$\mathring{\gamma}_{l}$ for some $l\notin\\{j,k\\}$ that is not between $j$
and $k$. It is easy to check that the definition does not depend on the choice
of $d$. Notice that $C_{j,k}\subseteq C_{j^{\prime},k^{\prime}}$ for ordered
pairs of indices $(j,k),(j^{\prime},k^{\prime})\in J^{2}$ if and only if
$j^{\prime}\leq j$ and $k\leq k^{\prime}$.

By a _nest_ $\mathcal{N}$ we mean a sequence $(\nu_{j})_{j\in J}$ of simple
cycles of bounded length that are either disjoint or intersect pair-wise in a
unique vertex $v$ and such that for $i<j<k$ in $J$ the cycle $\nu_{j}$
separates $\nu_{k}\setminus\nu_{j}$ from $\nu_{i}\setminus\nu_{j}$.

Let $pol(\mathcal{N})$ be equal to $\emptyset$ in the first case or $\\{v\\}$
in the second. Write $\mathring{\nu}_{j}=\nu_{j}\setminus pol(\mathcal{N})$.
Now, for some suitable choice of a side $N_{j}$ of $\nu_{j}$ we have
$N_{j}\subset N_{j^{\prime}}$ for $j<j^{\prime}$. In analogy with the previous
definition, for $j<j^{\prime}\in J$ we write
$N_{j,j^{\prime}}:=N_{j^{\prime}}\setminus(\nu_{j}\cup N_{j})$,
$int(\mathcal{N})=\bigcup_{j<j^{\prime}}N_{j,j^{\prime}}$.

The following observation is a consequence of (B):

######  Observation 2.2.

Given an unordered collection $\\{\gamma_{j}\\}_{j\in J}$ of size at least $3$
of paths of bounded length between vertices (possibly equal) vertices $v$ and
$w$ whose mutual intersection is $\\{v,w\\}$ there is a linear order on $J$,
unique up to inversion and cyclic permutation in case $v\neq v$ making
$\\{\gamma_{j}\\}_{j\in J}$ into a cage in case $v\neq w$ or a nest in case
$v=w$.

Given a cage or nest $\mathcal{D}$, we will refer to the set
$int(\mathcal{D}):=\bigcup_{j\neq k}D_{j,k}$ as the _interior_ of
$\mathcal{D}$ and we will write
$\widebar{int}(\mathcal{D}):=int(\mathcal{D})\cup pol(\mathcal{D})$. The
complement of $int(\mathcal{D})$ will be called the _exterior_ of
$\mathcal{D}$ and denoted by $ext(\mathcal{D})$.

######  Definition 2.3.

We say that a sequence of tuples (for instance, a cage or nest) indexed by a
linearly ordered set $J$ is _large_ if $J$ is dense with no upper or lower
bound.

######  Definition 2.4.

We say that a sequence of elements $(a_{i})_{i\in I}$, indexed by a linear
order of size at least $3$ _fits into_ a cage or nest
$\mathcal{D}=(\delta_{j})_{j\in J}$ if $\\{a_{i}\\}$ does not intersect any
$\delta_{j}$ and

  * •

for any $i_{0}<i_{1}<i_{2}$ in $I$ there are $j_{0}<j_{1}<j_{2}<j_{3}$ in $J$
such that
$C_{j_{l},j_{l+1}}\cap\\{a_{i_{0}},a_{i_{1}},a_{i_{2}},a_{i_{3}}\\}=\\{a_{i_{l}}\\}$
for $i=0,1,2$

  * •

for any $j<k$ in $J$ there is $i\in I$ with $a_{i}\in C_{j.k}$.

If no such $\mathcal{D}$ exists we say that $(a_{i})_{i\in I}$ is _free_.

######  Observation 2.5.

If a large sequence $(a_{i})_{i\in I}$ fits into a cage or nest
$\mathcal{D}=(\delta_{l})_{l\in L}$, then there exists $L^{\prime}\subseteq L$
such that $(a_{i})_{i\in I}$ fits into
$\mathcal{D}^{\prime}=(\delta_{l})_{l\in L^{\prime}}$ and
$\mathcal{D}^{\prime}$ is large.

If $\mathcal{D}=(\delta_{l})_{l\in L}$ is already large, then for any dense
subset $L^{\prime}\subseteq L$ the sequence $(a_{i})_{i\in I}$ fits into
$(\delta_{l})_{l\in L^{\prime}}$.

###### Proof.

∎

##  3\. Properties of large cages

######  Lemma 3.1.

Let $\mathcal{D}=\\{\delta_{j}\\}_{j\in J}$ be a large cage or nest. Let $a,b$
be two elements such that either:

  * •

$a\in int(\mathcal{D})$ and $b\in ext(\mathcal{D})$

  * •

$a\in\delta_{i}$ and $b\in\delta_{j}$ for distinct $i,j$

Then every path from $a$ to $b$ must pass through $pol(\mathcal{C})$.

###### Proof.

Let $p$ be a path from $a$ to $b$ and assume without loss of generality that
$p$ does not cross $pol(\mathcal{D})$. Now, there exist an infinity of cycles
with pair-wise intersection equal to $pol(\mathcal{D})$ of the form
$\delta_{k,l}$ separating $a$ from $b$. Since $p$ must intersect either
$\mathring{\delta}_{k}$ or $\mathring{\delta}_{l}$ in each of those cases
implies $p$ has to contain infinitely many vertices. This settles the first
claim. ∎

######  Corollary 3.2.

Let $\mathcal{C}=\\{\gamma_{j}\\}_{j\in J}$ be a large cage and $c$ a cycle.
Then one of the following holds:

  1. (1)

$c\subseteq ext(\mathcal{C})$

  2. (2)

$c\subseteq\widebar{int}(\mathcal{C})$

  3. (3)

$c$ is a concatenation $d*e$, where $e$ and $d$ are paths between the two
poles of $\mathcal{C}$, with $d\subseteq ext(\mathcal{C})$ and
$e\subseteq\widebar{int}(\mathcal{C})$. If $pol(\mathcal{C})\nsubseteq c$,
then there are $c$ can intersect $\mathring{\gamma}_{j}$ for at most one value
of $j$.

###### Proof.

Indeed, if $c$ contains points both in $int(\mathcal{C})$ and
$\widebar{int}(\mathcal{C})^{c}$, then by the previous Lemma it must intersect
$pol(\mathcal{C})$ two times and can only exit $int(\mathcal{C})$ once. ∎

A similar argument shows:

######  Lemma 3.3.

If $\mathcal{N}=(\nu_{j})_{j\in J}$ is a large nest, then for any cycle $c$
either $c\subseteq\widebar{int}(\mathcal{N})$ or $c\subseteq
ext(\mathcal{N})$. In the former case $c$ can intersect $\mathring{\nu}_{j}$
for at most one value of $j$.

######  Lemma 3.4.

Suppose that $c$ is a cycle and $(a_{i})_{i\in I}$ a large sequence disjoint
from $c$ and fitting into a large cage or nest $\mathcal{D}=(\delta_{l})_{l\in
L}$. If we partition $I$ into two sets according to the side of $c$ in which
$a_{i}$ lies the resulting partition contains a subinterval $J$ of $I$.
Moreover:

  * •

If $\mathcal{D}$ is a nest and $J$ is bounded on both sides or if
$pol(\mathcal{D})\nsubseteq c$, then $J$ is empty or a singleton.

  * •

If $\mathcal{D}$ is a cage and $c$ is as in case 3 of Corollary 3.2, then both
$J$ and $I\setminus J$ are unbounded and non-empty intervals.

###### Proof.

By Observation 2.5 we may assume $\bigcup\mathcal{D}\setminus pol(D)$ is
disjoint from $c$.

Consider first the case in which $\mathcal{D}$ is a cage and
$pol(\mathcal{D})\subset c$ and. Adding the one or two subpaths of $c$ that
lie in $\widebar{int}(\mathcal{D})$ to $\mathcal{D}$ we obtain a new cage by
Observation 2.2 and the result easily follows.

Take $i_{0}<i_{1}<i_{2}<i_{3}$ in $I$. If $c$ separates
$\\{a_{i_{0}},a_{i_{2}}\\}$ from $\\{a_{i_{1}},a_{i_{3}}\\}$. Then some cycle
of the form $\delta_{l}$ (if $\mathcal{D}$ is a nest) or
$\delta_{l,l^{\prime}}$ (if $\mathcal{D}$ is a cage) separates
$\\{a_{i_{0}},a_{i_{1}}\\}$ from $\\{a_{i_{2}},a_{i_{3}}\\}$ and thus must
cross $c$. This impossible unless $\mathcal{D}$ is a cage and
$pol(\mathcal{D})\subseteq c$ in which case it is ruled out by the argument
above.

Suppose now that $c$ separates $\\{a_{i_{0}},a_{i_{1}}\\}$ from
$\\{a_{i_{2}},a_{i_{3}}\\}$.

If $\mathcal{D}$ a cage then there are $l<l^{\prime}$ in $L$ such that
$\delta_{l,l^{\prime}}$ separates $\\{a_{i_{1}},a_{i_{2}}\\}$ from
$\\{a_{i_{0}},a_{i_{3}}\\}$, which implies that $c$ and
$\delta_{l,l^{\prime}}$ cross, and thus $pol(\mathcal{D})\subseteq c$.

If $\mathcal{D}$ is a nest there are distinct $l<l^{\prime}$ such that
$\delta_{l}$ separates $a_{i_{0}}$ from $a_{i_{1}},a_{i_{2}},a_{i_{3}}$ and
$\delta_{l^{\prime}}$ separates $a_{i_{0}},a_{i_{1}},a_{i_{2}}$ from
$a_{i_{3}}$. It follows from property C that $\delta_{l}$ and
$\delta_{l^{\prime}}$ must lie in distinct sides of $c$. This implies that
$pol(\mathcal{D})\subseteq c$ and both $J$ and $I\setminus J$ are unbounded
(each of the two sides of $c$ contains one side of either $\delta_{l}$ or
$\delta_{l^{\prime}}$).

∎

######  Lemma 3.5.

Let each of $\mathcal{D}=(\delta_{j})_{j\in J}$ and
$\mathcal{E}=(\epsilon_{k})_{k\in K}$ be either a large cage or a large nest
with a pole. Then either $pol(\mathcal{E})\subseteq\widebar{int}(\mathcal{D})$
or $pol(\mathcal{E})\subseteq ext(\mathcal{D})$. Moreover if
$pol(\mathcal{D})\neq pol(\mathcal{E})$ then one of the following mutually
exclusive possibilities hold:

  * •

$int(\mathcal{D})\cap int(\mathcal{E})=\emptyset$

  * •

up to exchanging $\mathcal{D}$ and $\mathcal{E}$ there exist $j,k\in J$ such
that $\widebar{int}(\mathcal{D})\setminus pol(\mathcal{E})\subset E_{j,k}$.

###### Proof.

If $pol(\mathcal{E})\cap int(\mathcal{D})$ and
$pol(\mathcal{E})\cap\widebar{int}(\mathcal{D})^{c}$ are both non-empty, then
Lemma 3.1 implies the existence of $v\in pol(\mathcal{E})$ contained in
$\mathring{\epsilon}_{i},\mathring{\epsilon}_{j}$ for different $i\neq j$: a
contradiction, hence the first claim.

For the second claim suppose that
$|pol(\mathcal{D})|=max\\{|pol(\mathcal{D})|,|pol(\mathcal{E})|\\}$.

Consider first the case in which $pol(\mathcal{E})\subseteq ext(\mathcal{D})$.
Take $j^{\prime}<k^{\prime}<l^{\prime}$ in $K$. In view of Corollary 3.2 we
must have
$\epsilon_{j^{\prime}}\cup\epsilon_{k^{\prime}}\cup\epsilon_{l^{\prime}}\subseteq
ext(\mathcal{D})$ and then either $int(\mathcal{D})\subseteq
E_{j^{\prime},l^{\prime}}$ or $E_{j^{\prime},l^{\prime}}\subseteq
ext(\mathcal{D})$. If the former does not hold for any
$j^{\prime}<l^{\prime}$, then $int(\mathcal{D})\cap
int(\mathcal{E})=\emptyset$.

Assume now that $pol(\mathcal{E})\subseteq\widebar{int}(\mathcal{D})$. Choose
$j_{0}<k_{0}$ in $J$ such that $pol(\mathcal{E})\setminus
pol(\mathcal{D})\subseteq D_{j_{0},k_{0}}$. We claim that
$int(\mathcal{E})\subseteq D_{j_{0},k_{0}}$. Indeed, otherwise there are
infinite sequences $j^{\prime}_{1}>j^{\prime}_{2}\dots$ and
$k^{\prime}_{1}<k^{\prime}_{2}<\dots$ in $J^{\prime}$ such that for every $n$
either $\epsilon_{j_{n}}$ or $\epsilon_{k_{n}}$ is not contained in
$D_{j_{0},k_{0}}$. Since $pol(\mathcal{E})$ intersects $D_{j_{0},k_{0}}$, it
follows that $\delta_{j_{0}}\cup\delta_{k_{0}}$ and
$\epsilon_{j_{n}}\cup\epsilon_{k_{n}}$ must intersect in at least two
vertices, one of which must lie outside of $pol(\mathcal{E})$. This implies
that one of $\delta_{j_{0}}$ or $\delta_{k_{0}}$ contains an infinite number
of distinct vertices: a contradiction.

∎

######  Corollary 3.6.

Let $\mathcal{D}=(\delta_{j})_{j\in J}$ and
$\mathcal{D^{\prime}}=(\delta^{\prime}_{j})_{j\in J^{\prime}}$ be either a
large cage or a large nest. If a large sequence $(a_{i})_{i\in I}$ fits into
both $\mathcal{D}$ and $\mathcal{D}^{\prime}$, then $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ are either both cages or both nests,
$pol(\mathcal{D})=pol(\mathcal{D}^{\prime})$ and
$int(\mathcal{D})=int(\mathcal{D}^{\prime})$.

###### Proof.

From Lemmas 3.4 and 3.5 it follows that
$pol(\mathcal{D})=pol(\mathcal{D}^{\prime})$.

After replacing $J$ and $J^{\prime}$ with cofinal dense subsets we may assume
$\mathring{\delta}_{j}$ and $\mathring{\delta}^{\prime}_{j^{\prime}}$ are
disjoint for any $j\in J$ and $j^{\prime}\in J^{\prime}$. Using Lemma 3.4 in
case both $\mathcal{D}$ and $\mathcal{D}^{\prime}$ are nests we conclude that
we can merge $\mathcal{D}$ and $\mathcal{D}^{\prime}$ into a larger cage or
nest $\mathcal{D}^{\prime\prime}=(\delta_{j})_{j\in J^{\prime\prime}}$,
$J^{\prime}=J^{\prime}\cup J^{\prime}$. The assumption that $(a_{i})_{i\in I}$
fits into both $\mathcal{D}$ and $\mathcal{D}^{\prime}$ implies $J$ and
$J^{\prime}$ are both dense and cofinal in $J^{\prime\prime}$, from which it
follows that $int(\mathcal{D})=int(\mathcal{D}^{\prime})$. ∎

As a further corollary we get:

######  Corollary 3.7.

Let a sequence of elements $(a_{i})_{i\in I}$ fit into a large cage or nest
$\mathcal{D}$. Then $int(\mathcal{D})$ and $pol(\mathcal{D})$ are invariant
under any automorphism of $\mathbb{G}^{\iota}$ fixing $\\{a_{i}\\}_{i\in I}$
set-wise.

##  4\. Indiscernibles and cages

We start with a couple of observations regarding cages and indiscernible
sequences of elements.

######  Lemma 4.1.

Let $(a_{j})_{j\in J}$ be a large sequence of elements indiscernible over some
set $B$ of parameters and assume that $(a_{j})_{j\in J}$ fits into a large
nest or cage $\mathcal{D}$. Then $B\subseteq ext(\mathcal{D})$.

###### Proof.

We will focus on the case in which $\mathcal{D}=(\delta_{l})_{l\in L}$ is a
cage, since the case in which it is a nest is formally identical. Assume the
result is false and pick $l_{2}<l_{3}\in L$ such that $b\in C_{l_{2},l_{3}}$.
Now, choose $l_{0},l_{1},l_{4},l_{5}$ such that $l_{0}<l_{1}<l_{2}$ and
$l_{3}<l_{4}<l_{5}$. By definition, there exists $j_{0}<j_{1}<j_{3}<j_{4}$ in
$J$ such that $a_{j_{m}}\in C_{l_{m},l_{m+1}}$, $m\in\\{0,1,3,4\\}$. Let $N$
be the maximum length of the cycles $\gamma_{l,l^{\prime}}$ and consider the
following formula over $b$:

$\displaystyle\phi(x_{1},x_{2},x_{3})\cong\exists z_{1}\dots
z_{N}\,R_{N}(x_{1},b,z)\wedge\neg R_{N}(x_{2},b,z)\wedge\neg R_{N}(x_{3},b,z)$

∎

The cycle $\gamma_{l_{1},l_{3}}$ witnesses
$\models\phi(a_{j_{1}},a_{j_{3}},a_{j_{4}})$. On the other, after removing
finitely many components from $(a_{j})_{j\in J}$ and $\mathcal{D}$ we may
assume one can add $b$ to the sequence $(a_{j})_{j\in J}$ between the position
of $a_{j_{1}}$ and $a_{j_{3}}$ and obtain a new sequence fitting into
$\mathcal{D}$. Lemma 3.4 then implies the formula
$\phi(a_{j_{0}},a_{j_{1}},a_{j_{3}})$ cannot hold, contradicting
indiscernibility of $(a_{j})_{j\in J}$ over $B$.

######  Observation 4.2.

Assume that $(a_{j})_{j\in J}$ is an indiscernible sequence and there is some
infinite $J^{\prime}\subseteq J$ such that $(a_{j})_{j\in J^{\prime}}$ fits
into a cage (nest). Then $(a_{j})_{j\in J}$ fits into a cage (nest).

###### Proof.

By compactness, if any finite subsequence of a sequence $I=(a_{j})_{j\in J}$
fits into a cage with components of uniformly bounded length, then so does
$I$. ∎

######  Lemma 4.3.

Suppose we are given an indiscernible sequence of cycles, $(c_{j})_{j\in J}$.
Then one of the following holds:

  1. (a)

Either the sequence $(c_{j})_{j\in J}$ is a nest $\mathcal{D}^{0}$ or it
contains finitely many cages $\mathcal{D}^{1},\dots\mathcal{D}^{m}$ with
disjoint interiors.

In this case given vertices $b$ and $b^{\prime}$ that do not appear in the
$c_{j}$ we have the following:

     * •

If $(c_{j})_{j\in J}$ is indiscernible over $b$ there is one alternation in
the truth value of $b\sim_{c_{j}}b^{\prime}$ as $j$ ranges in $J$ if $b\in
int(\mathcal{D}^{l})$ for $\mathcal{D}^{l}$ and none otherwise

     * •

If $b^{\prime},b^{\prime\prime}$ belong to $int(\mathcal{D}^{l})$, where
$\mathcal{D}^{l}=(\delta^{l})_{j\in J}$ is as above, then there are two
alternations in the truth value of $b^{\prime}\sim_{c_{j}}b^{\prime\prime}$
only if $j<j^{\prime}$ in $J$ with $\\{b^{\prime},b^{\prime\prime}\\}\cap
D_{j,j^{\prime}}^{l}=\\{b^{\prime}\\}$ exists.

.

  2. (b)

We have $|c_{j}\cap c_{j^{\prime}}|=2$ for distinct $j,j^{\prime}$ and if
$(c_{j})_{j\in J}$ is indiscernible over $b$, then
$\\{\mathbf{D}^{-}_{c_{j}}(b)\\}_{j\in J}$ is a family of disjoint sets.

###### Proof.

We will consider the case in which $c_{j}$ and $c_{j^{\prime}}$ have at least
two vertices in common for $j,j^{\prime}\in J$. If not, then $(c_{j})_{j\in
J}$ is easily seen to be a nest and the required property can be checked using
simpler versions of the same arguments.

We start by noticing that given a linearly ordered set $J$ any indiscernible
sequence $(\gamma_{j})_{j\in J}$ of paths between two vertices $u,v$
intersecting pair-wise only on $\\{u,v\\}$ which is indiscernible must be a
cage with respect to the same linear order on $J$.

Suppse $c_{i}=(c_{i}^{k})_{k=1}^{n}$. If we let $F\subset\\{1,\cdots n\\}$ be
the set of indices such that $c_{j}^{l}$ is constant for all $j$ then
$c_{j}^{k}\neq c_{j^{\prime}}^{k^{\prime}}$ whenever $j\neq j^{\prime}$ and at
least one of $k,k^{\prime}$ does not belong to $F$. Let $\mathcal{P}$ be the
collection of all pairs $(k,l)$ of cyclically consecutive indices of $F$ (in
that order) which are not cyclically consecutive in $\\{1,2\cdots n\\}$ and
for any $(k,l)\in\mathcal{P}$ let $\gamma^{k,l}_{j}$ be the subpath $c_{j}$
from $c_{j}^{k}$ to $c_{j}^{l}$. Then
$\mathcal{C}^{k,l}:=(\gamma_{j}^{k,l})_{j\in J}$ is a cage.

######  Observation 4.4.

For any distinct $(k_{0},k_{1}),(k_{2},k_{3})\in\mathcal{P}$ and any
$j_{1}<j_{2}$ in $J$ it cannot be that $\mathring{\gamma}^{k_{2},k_{3}}_{j}$
contains vertices in $int((\gamma_{j})_{j\in(j_{1},j_{2})})$ for $j\leq j_{1}$
or $j\geq j_{2}$.

###### Proof.

Otherwise it follows from Lemma 4.1 that the sequence
$(\mathring{\gamma}_{j}^{k_{0},k_{1}})_{j\in(j_{1},j_{2})}$ is not
indiscernible over $c_{j_{1}}$ or $c_{j_{2}}$ respectively, contradicting the
indiscernibility of $(c_{j})_{j\in J}$. ∎

Assume first that $\mathcal{P}$ is not of the form $\\{(k,l),(l,k)\\}$ and
pick any distinct $(k_{0},k_{1}),(k_{2},k_{3})\in\mathcal{P}$. We claim that
$int(\mathcal{C}^{(k_{0},k_{1})})\cap
int(\mathcal{C}^{(k_{2},k_{3})})=\emptyset$. Otherwise by Lemma 3.5 there
exist $j_{1}<j_{2}$ in $J$ such that $int(\mathcal{C}^{k_{0},k_{1}})\subseteq
C^{k_{2},k_{3}}_{j_{1},j_{2}}$, contradicting the observation above.

If $\mathcal{P}=\\{(k,l),(l,k)\\}$ and $int(\mathcal{C}^{l,k})\cap
int(\mathcal{C}^{k,l})\neq\emptyset$, then $int(\mathcal{C}^{k,l})$ contains
$\mathring{\gamma}_{j}^{l,k}$ for some $j_{0}\in J$. By the observation above
no $v\in\mathring{\gamma}_{j}^{l,k}$ can belong to
$C^{k,l}_{j^{\prime},j^{\prime\prime}}$ for
$j^{\prime}<j^{\prime\prime}<j_{0}$ or $j_{0}<j^{\prime}<j^{\prime\prime}$. By
indiscernibility $\mathring{\gamma}^{l,k}_{j}$ must lie in
$C^{k,l}_{j^{\prime},j^{\prime\prime}}$ for any
$j^{\prime}<j<j^{\prime\prime}$.

So we have the following alternative:

  1. (1)

$int(\mathcal{C}^{k,l})\cap
int(\mathcal{C}^{k^{\prime},l^{\prime}})=\emptyset$ for any two distinct
$(k,l),(k^{\prime},l^{\prime})\in\mathcal{P}$

  2. (2)

up to exchanging $\mathcal{C}$ and $\mathcal{C}^{\prime}$ there is a cage
$\mathcal{C}^{\prime}=(\beta^{\prime}_{j})_{j\in J\times\\{1,2\\}}$ where
$J\times\\{1,2\\}$ is ordered lexicographically and
$\beta^{\prime}_{(j,1)}=\beta^{k,l}_{j}$ and
$\beta^{\prime}_{(j,2)}=\beta^{l,k}_{j}$.

One can now check by inspection that given $b,b^{\prime}$ outside of
$\cup_{j\in J}c_{j}$ there is at most one alternation in the truth value of
$b\sim_{c_{j}}b^{\prime}$ for each pair $(d,(k,l))$, where
$d\in\\{b,b^{\prime}\\}$ and $(k,l)\in\mathcal{P}$ and $d\in
int(\mathcal{C}^{k.l})$.

In cases 1 there can be at most two such pairs and in fact at most one in case
$(c_{j})_{j}$ is indiscernible over $b$, since by Lemma 4.1 the latter implies
$b\notin int(\mathcal{C}^{k,l})$ for any $(k,l)\in\mathcal{P}$. If
$b,b^{\prime}\in int(\mathcal{C}^{k,l})$ and there are two alternations, it
can be easily seen by inspection that $j,j^{\prime}$ with the desired
properties exist.

In case 2 we have that $\\{\mathbf{D}^{-}_{c_{j}}(b)\\}_{j\in J}$ is a family
of disjoint sets as in the second alternative of the statement.

∎

######  Lemma 4.5.

Let $I=(a_{j})_{j\in J}$ be a non-constant large sequence of elements
indiscernible over some set $B$ of parameters and $c$ a cycle in which none of
the $a_{j}$ appear. If we partition $J$ into two sets $J_{1}$ and $J_{2}$
according to the side of $c$ each $a_{j}$ lies in then either:

  1. (a)

up to exchanging $J_{1}$ and $J_{2}$ we have $J_{1}=\\{i_{0}\\}$,
$J_{2}=J\setminus\\{i_{0}\\}$ and all $b\in B$ lie on the opposite side of $c$
from $a_{i_{0}}$.

  2. (b)

$J_{1}$ and $J_{2}$ are both infinite, $J_{1}$ is an interval and
$(a_{j})_{j\in J}$ fits into a cage or nest

###### Proof.

Suppose first $B\neq\emptyset$ and fix some $b\in B$. Let
$J^{\prime}=\\{j\,|\,a_{j}\sim_{c}b\\}$, $J^{\prime\prime}=J\setminus
J^{\prime}$. We claim that it is not possible to have $J_{1}<j_{2}<J_{3}$,
where $J_{i}\subseteq J^{\prime\prime}$ are infinite and $j_{2}\in
J^{\prime}$. Indeed, if this is the case, up to extending and then restricting
$I$ we may as well assume that $J=J_{1}\cup\\{j_{2}\\}\cup J_{3}$ and there
are $c_{j}$, $j\in J$ such that $(c_{j}a_{j})_{j\in J}$ indiscernible over $b$
and with $c=c_{j_{2}}$. (For $j\in J$ let $c^{\prime}_{j}$ be the image of $c$
by an automorphism of $\mathbb{G}^{\iota}$ restricting to an order preserving
permutation of $(a_{j})_{j\in J}$ sending $j_{2}$ to $j$. Pick an
indiscernible sequence indexed over $J$ realizing the EM-type of
$(a_{j}c^{\prime}_{j})_{j\in J}$. Use an automorphism to bring it first
components to $(a_{j})_{j\in J}$.) Notice that we then have a double
alternation:

$a_{j_{2}}\nsim_{c_{j_{1}}}b,\,\,\,a_{j_{2}}\sim_{c_{j_{2}}}b,\,\,\,a_{j_{2}}\nsim_{c_{j_{3}}}b$

for $j_{1}\in J_{1}$, $j_{3}\in J_{3}$. According to Lemma 4.3 if this happens
then $\\{\mathbf{D}^{-}_{c_{j}}(b)\\}_{j\in J}$ are disjoint, contradicting
$\mathbf{D}^{-}_{c_{j}}(b)=\\{a_{i}\\}_{i\neq j}$.

Next we show that (independently of $B$) if there are infinite $J_{1}<J_{2}$
in $J$ such that $c$ separates $\\{a_{j}\\}_{j\in J_{1}}$ from
$\\{a_{j}\\}_{j\in J_{2}}$, then $I$ fits into a cage. Using Observation 4.2
we may assume that $J=\mathbb{Q}$, $J_{1}=\mathbb{Q}_{<0}$ and
$J_{2}=\mathbb{Q}_{\geq 0}$ and that there is an indiscernible sequence
$(a_{j}c_{j})_{j\in J}$ with $c_{0}=c$. Lemma 4.3 then yields the desired
result: every element in the sequence must lie in the interior of either the
nest or one of the finitely many cages and this cage should be the same for
some infinite subsequence of them. Since for any distinct $j_{0},j_{1}\in J$
there are two alternations in the truth value of
$a_{j_{0}}\sim_{c_{j}}a_{j_{1}}$ as $j$ ranges in $J$ it follows that this
infinite subsequence fits into a cage and thus the entire sequence does by
Observation 4.2.

Assume now that $I$ does not fit into a cage or nest and let
$\\{J,J^{\prime}\\}$ be the partition of $J$ induced by $c$. We argue that
there cannot be three alternations between $J$ and $J^{\prime}$. If this is
the case then up to reversing the orientation of $J$ we have
$j_{1}<J_{2}<j_{3}<J_{4}^{\prime}$, where $j_{1},j_{3}\in J$ and
$J_{2},Jl4\subseteq J^{\prime}$ are infinite. Since $I_{\restriction
J_{2}\cup\\{j_{3}\\}\cup J_{4}}$ is indiscernible over $a_{j_{1}}$ we obtain a
contradiction with the claim of the previous paragraph.

Since any finite sub-interval of $J$ is a singleton, in fact either $J_{1}$ is
a singleton or empty. In both cases our first claim ensures that if $I$ is
indiscernible over $b$, then $c$ separates $b$ from $I$.

∎

##  5\. The envelope of a free indiscernible sequence

######  Definition 5.1.

Given some free non-constant sequence of elements $I=(a_{j})_{j\in J}$ we let
$\mathcal{S}(I)_{j}$ be the collection of all cycles which separate $a_{j}$
from $I\setminus\\{a_{j}\\}$ and

$\mathcal{X}(I)_{j}=\bigcup_{c\in\mathcal{S}(I)_{j}}\mathbf{D}^{+}_{c}(a_{j})\cup
c.$

For the remainder of the section $I=(a_{j})_{j\in J}$ will be a free non-
constant indiscernible sequence of elements.

######  Definition 5.2.

We say that a vertex in $\mathcal{X}(I)_{j}$ is _external_ if it is not
contained in $\mathbf{D}^{+}_{c}(a_{j})$ for any $c\in\mathcal{S}(I)_{j}$.

######  Definition 5.3.

Let $A$ be a finite collection of vertices. By the complementary regions of
$A$ we mean the equivalence classes of the vertices in $V\setminus A$ by the
equivalence relation given by:

  * •

$b\sim b^{\prime}$ if and only if $b\sim_{d}b^{\prime}$ for all cycles
$d\subseteq A$

######  Lemma 5.4.

Let $c,c^{\prime}$ two cycle, $a$ a vertex and suppose that $|c\cap
c^{\prime}|\geq 2$. Then each complementary region $D$ of $c\cup c^{\prime}$
is of the form $\mathbf{D}^{+}_{d}(b)$ for some cycle $d\subset c\cup
c^{\prime}$ and some $b\in D$.

###### Proof.

Fix $b\in D$ and consider the collection $\mathcal{P}=\\{p_{1},\dots p_{k}\\}$
of maximal subpaths of $c^{\prime}$ with interior in $\mathbf{D}^{+}_{c}(b)$.
Clearly, for no such subpath $p$ can the two endvertices coincide, since that
would imply $p$ is the whole $c^{\prime}$ and $|c\cap c^{\prime}|=1$. By
induction it is easy to construct cycles $d_{0}=c$, $d_{1},d_{2}\dots d_{k}$
such that the complementary region of
$c\cup(c^{\prime}\setminus\mathbf{D}^{+}_{c}(b))\cup p_{1},\dots p_{k}$
coincides with $\mathbf{D}^{+}_{d_{k}}(b)$. ∎

######  Lemma 5.5.

Assume $\mathcal{S}(I)_{j_{0}}\neq\emptyset$ for $j_{0}\in J$. Then any two
external vertices of $\mathcal{X}(I)_{j_{0}}$ are contained in a common cycle
$c\in\mathcal{S}(I)_{j}$.

###### Proof.

Let $v_{1}$ and $v_{2}$ be external vertices contained in
$d_{1},d_{2}\in\mathcal{S}(I)_{j_{0}}$ respectively. We may assume
$v_{i}\notin d_{3-i}$. It cannot be the case that $|d_{1}\cap d_{2}|\leq 1$,
since this implies that $d_{i}\setminus
d_{3-i}\subseteq\mathbf{D}^{+}_{d_{3-i}}(a_{j_{0}})$ for some $i$, so that
$v_{i}$ cannot be external.

Thus, we can apply Lemma 5.4 to $d_{1}$ and $d_{2}$. One of the four
complementary regions of $d_{1}\cup d_{2}$ contains $a_{j_{0}}$ and by Lemma
4.5 one of the others must contain $\\{a_{j}\\}_{j\neq j_{0}}$. By Lemma 5.4
the latter must be of the form $\mathbf{D}^{-}_{e}(a_{j_{0}})$ for some cycle
$e\subset d_{1}\cup d_{2}$. Since $d_{1}\cup
d_{2}\subseteq\mathbf{D}^{+}_{e}(a_{j_{0}})\cup e$ and $v_{1},v_{2}$ are
external, it follows that $v_{1},v_{2}\in e$, as desired. ∎

For future reference we also record the following:

######  Lemma 5.6.

For any finite set $F\subseteq\mathcal{X}(I)_{j}$ there exists some cycle
$c\in\mathcal{S}(I)_{j}$ such that $F\subseteq\mathbf{D}^{+}_{c}(a_{j})\cup
c$.

###### Proof.

Indeed, for any two cycles $c,c^{\prime}\in\mathcal{S}(I)$ either $|c\cap
c^{\prime}|=1$ and we may assume that $\mathbf{D}^{+}_{c}(a_{j})\cup
c\subseteq\mathbf{D}^{+}_{c^{\prime}}(a_{j})\cup c^{\prime}$ or $|c\cap
c^{\prime}|$ and Lemma 5.4 provides some cycle $e\subseteq c\cup c^{\prime}$
such that $\mathbf{D}^{+}_{c}(a_{j})\cup
c\cup\mathbf{D}^{+}_{c^{\prime}}(a_{j})\subseteq
e\cup\mathbf{D}^{+}_{e}(a_{j})$. The result now easily follows by induction. ∎

######  Lemma 5.7.

For distinct $j_{1},j_{2}$ in $J$ the intersection
$\mathcal{X}(I)_{j_{1}}\cap\mathcal{X}(I)_{j_{2}}$ consists of at most one
vertex, external in both $\mathcal{X}(I)_{j_{1}}$ and
$\mathcal{X}(I)_{j_{2}}$.

###### Proof.

We may assume $\mathcal{S}(I)_{j}\neq\emptyset$ for all $j$. Suppose
$\mathcal{X}(I)_{j_{1}}\cap\mathcal{X}(I)_{j_{2}}$ contains distinct vertices
$v,v^{\prime}$ for $j_{0}\neq j_{1}$.

Notice that given $c_{1}\in\mathcal{S}(I)_{j_{1}}$ and
$c_{2}\in\mathcal{S}(I)_{j_{2}}$ it cannot be that $c_{2}$ lies entirely in
$c_{1}\cup\mathbf{D}^{+}_{c_{1}}(a_{j_{1}})$, or else we would have
$\\{a_{j}\\}_{j\in
J\setminus\\{a_{j_{0}},a_{j_{1}}\\}}\subseteq\mathbf{D}^{-}_{c_{2}}(a_{j_{2}})\subseteq\mathbf{D}^{+}_{c_{1}}(a_{j_{1}})$.

Thus, if the intersection
$\mathbf{D}^{+}_{c_{1}}(a_{j_{i}})\cap(\mathbf{D}^{+}_{c_{2}}(a_{j_{3-i}})\cup
c_{3-i})$ is non-empty for some $c_{1}\in\mathcal{S}(I)_{j_{i}}$ and some
$c_{2}\in\mathcal{S}(I)_{j_{2}}$, then $c_{1}$ and $c_{2}$ must cross.

Otherwise for any such $c_{1},c_{2}$ we can choose $v$ and $v^{\prime}$ to be
external in both $\mathcal{X}(I)_{j_{1}}$ and $\mathcal{X}(I)_{j_{2}}$.

Remark 2.1 in the first situation and Lemma 5.5 in the second there must be
$c_{1}\in\mathcal{S}(I)_{j_{1}}$ and $c_{2}\in\mathcal{S}(I)_{j_{2}}$ with at
least two vertices in common.

Notice that $a_{j_{1}}$ and $a_{j_{2}}$ lie in different complementary regions
from each other and any $a_{j}$, $j\in J\setminus\\{j_{1},j_{2}\\}$. Lemma 5.4
yields some cycle $d\subseteq c_{1}\cup c_{2}$ such that
$\mathbf{D}^{-}_{d}(a_{j_{1}})\cap\\{a_{j}\\}_{j\in J}=\\{a_{j}\\}_{j\in
J^{\prime}}$ for some infinite subset $J^{\prime}\subseteq
J\setminus\\{j_{1},j_{2}\\}$, contradicting Lemma 4.5.

∎

######  Lemma 5.8.

For distinct $j_{1},j_{2}$ in $J$ there exist a unique vertex
$p_{j_{1},j_{2}}\in\mathcal{X}(I)_{j_{1}}$ such that any path (possibly
consisting of a single vertex) from $\mathcal{X}(I)_{j_{1}}$ and
$\mathcal{X}(I)_{j_{2}}$ intersecting $\mathcal{X}(I)_{j_{1}}$ only at its
endpoints must start at $p_{j_{1},j_{2}}$.

###### Proof.

If $\mathcal{S}(I)_{j}=\emptyset$, this is trivial. Suppose the condition does
not hold and $p_{1}$ and $p_{2}$ minimal paths form $\mathcal{X}(I)_{j_{1}}$
to $\mathcal{X}(I)_{j_{2}}$ (i.e. no subpath has the same property) starting
at distinct external vertices, $v_{1}$ and $v_{2}$ respectively and ending at
external vertices $w_{1},w_{2}$ of $\mathcal{X}(I)_{j_{2}}$.

Using Lemma 5.5 in case $p_{1}$ and $p_{2}$ do not intersect, we can find some
simple path $q$ between $v_{1}$ and $v_{2}$ whose interior lies outside of
$\mathcal{X}(I)_{j_{1}}$.

By Lemma 5.5, there must be two non-degenerate paths $r,r^{\prime}$ contained
in $\mathcal{X}(I)_{j_{1}}$ between $v_{1}$ and $v_{2}$ with
$r*r^{\prime}\in\mathcal{S}(I)_{j_{1}}$. Without loss of generality
$d_{1}:=r*q$ and $d_{2}:=r^{\prime}*q^{-1}$ are cycles.

So for any $i=1,2$ we have that $\\{j\in
J\,|a_{j}\in\mathbf{D}^{+}_{d_{i}}(a_{j_{1}})\\}$ is equal to either the whole
$J$ or $\\{a_{j}\\}_{j\in J\setminus\\{j_{3}\\}}$ for some $j_{3}\in
J\setminus\\{j_{1}\\}$. The latter cannot hold, since it implies that
$\\{j\,|\,a_{j}\in\mathbf{D}^{+}_{d_{3-i}}(a_{j_{1}})\\}=J\setminus\\{j_{1}\\}$,
i.e, $d_{3-i}\in\mathcal{S}(I)_{j_{1}}$. The former implies that $d_{2}$
separates $\\{a_{j}\\}_{j\in J}$ into two sets of cardinality at least two,
contradicting Lemma 4.5. ∎

######  Lemma 5.9.

Assume that for any distinct $j,j^{\prime}\in J$ there is a path between the
sets $\mathcal{X}(I)_{j}$ and $\mathcal{X}(I)_{j^{\prime}}$. Then there is a
(unique) vertex $nod(I)$ such that for any distinct $j,j^{\prime}\in J$ any
path from $\mathcal{X}(I)_{j}$ to $\mathcal{X}(I)_{j^{\prime}}$ passes through
$v$.

###### Proof.

For distinct $j,j^{\prime}\in J$ let $B_{j,j^{\prime}}$ be the union of
$\mathcal{X}(I)_{j}\cup\mathcal{X}(I)_{j^{\prime}}$ and the collection
$\mathcal{Q}_{j,j^{\prime}}$ of all the paths between $\mathcal{X}(I)_{j}$ and
$\mathcal{X}(I)_{j^{\prime}}$ intersecting
$\mathcal{X}(I)_{j}\cup\mathcal{X}(I)_{j^{\prime}}$ only at the endpoints.
Notice that any automorphism of $\mathbb{G}$ fixing $a_{j}$ and
$a_{j^{\prime}}$ must preserve $\mathcal{X}(I)_{j}$ and
$\mathcal{X}(I)_{j^{\prime}}$ set-wise and thus $B_{j,j^{\prime}}$.

We may assume $\mathbb{N}\subseteq J$. For $j>2$ let $V_{j}$ the collection of
vertices in $B_{1,2}$ that can be joined to $\mathcal{X}(I)_{j}$ by a path
whose interior lies outside of $B_{1,2}$.

We claim that $|V_{j}|=1$. Indeed, suppose $V_{i}$ contains distinct vertices
$v_{1},v_{2}$. By Lemma 5.7 we may assume $v_{1}\notin\mathcal{X}(I)_{1}$.
Since any two external vertices of $\mathcal{X}(I)_{j}$ are connected by Lemma
5.5, we easily find a path in $\mathcal{Q}_{1,2}$ that is closer to
$\mathcal{X}(I)_{j}$ than $v_{1}$ along a path between $v_{1}$ and
$\mathcal{X}(I)_{j}$, contradicting $v_{1}\in V_{j}$. Write
$\\{u_{j}\\}=V_{j}\cap B_{1,2}$.

We must have $u_{j}\in\mathcal{Q}_{1,2}$ since otherwise
$d(\mathcal{X}(I)_{j},\mathcal{X}(I)_{1})\neq
d(\mathcal{X}(I)_{j},\mathcal{X}(I)_{2})$, contrary to indiscernibility.
Finally, we claim that $u_{j}$ is a constant $u$ for $j>2$. Suppose not. Since
$u_{j}$ is easily seen to be definable from $a_{1},a_{2},a_{j}$, in that case
all $u_{j}$ must be different for $j>2$.

Choose some $q_{j}\in\mathcal{Q}_{1,2}$ with $u_{j}\in q_{j}$.We may assume
$(q_{j}u_{j})_{j>2}$ is indiscernible. Using the fact that all $q_{j}$, $j>2$
have the same endpoints one can see from the proof of Lemma 4.3 that
$u_{j}\in\mathring{\gamma}_{j}$, where $\mathcal{C}=(\gamma_{j})_{j>2}$ with
$\gamma_{j}$ is a subpath of $q_{j}$ in constant position.

Let $d_{j}\in\mathcal{S}(I)_{j}$ be either $a_{j}$ in case
$\mathcal{S}(I)_{j}=\emptyset$ or a cycle in $\mathcal{S}(I)_{j}$ at minimal
distance from $A_{1,2}$ in case $\mathcal{S}(I)_{j}\neq\emptyset$. We may
assume $(d_{j}q_{j})_{j\leq 3}$ all have the same type.

If $d_{j}\subseteq ext(\mathcal{C})$, then by Lemma 3.1 any path from $d_{j}$
to any point in $int(\mathcal{C})$ has to go through
$pol(\mathcal{C})\subseteq B_{1,2}$, contradicting that $V_{j}=\\{u_{j}\\}$.
By Lemma 5.7 we must have $|d_{j}\cap pol(\mathcal{C})|\leq 1$ and thus
$d_{j}\subseteq int(\mathcal{C})$, which implies $a_{j}\in int(\mathcal{C})$
for $j\geq 3$. Since $a_{1},a_{2}\in ext(\mathcal{C})$, this contradicts Lemma
4.5.

We claim that for any $2<j_{1}<j_{2}$ any path from $X(I)_{j_{1}}$ to
$X(I)_{j_{2}}$ must pass through $u$. We can go from $a_{j_{1}}$ to $a_{1}$ by
a first using a shortest path $r_{1}$ to $u$ from $a_{j_{1}}$ and then moving
inside a path $\mathcal{Q}_{1,2}$ to $a_{1}$. The result is in
$\mathcal{Q}_{j_{1},1}$.

Let $r_{2}$ a path from $a_{j_{2}}$ to $u$ conjugate to $r_{1}$ over
$a_{1},a_{2}$. If a path from $a_{j_{2}}$ to $a_{j_{1}}$ that does not go
through $u$ exists, then either $r_{2}$ does not have minimal length among all
paths from $a_{j_{2}}$ to $B_{1,j_{1}}$ or there are two points in
$B_{1,j_{1}}$ that are the starting points of paths to $a_{j_{2}}$ with
interior outside of $B_{1,j_{1}}$, which contradicts the fact that any
automorphism of $\mathbb{G}^{\iota}$ fixing $a_{j_{1}},a_{j_{2}}$ and taking
$a_{2}$ to $a_{j_{1}}$ must take $B_{1,2}$ to $B_{1,j_{1}}$.

So for any distinct $j_{1},j_{2},j_{3}$ in $J$ there exist a vertex that must
lie in any path between $\mathcal{X}(I)_{j_{k}}$ and
$\mathcal{X}(I)_{j_{k^{\prime}}}$ for any distinct
$k,k^{\prime}\in\\{1,2,3\\}$. Some simple considerations regarding the
distance of such vertex from $\mathcal{X}(I)_{j_{k}}$ yield that in fact said
vertex must be the same for any such triple. ∎

######  Definition 5.10.

We let $nod(I)$ equal to the vertex $u$ provided by the previous lemma in case
$\mathcal{X}(I)_{j}$ and $\mathcal{X}(I)_{j^{\prime}}$ are connected by some
path for distinct $j,j^{\prime}$ and $\emptyset$ otherwise.

######  Definition 5.11.

Suppose we are given a free indiscernible sequence of elements
$I=(a_{j})_{j\in J}$. Let $\mathcal{H}(I)_{j}$ the collection of all vertices
connected to $X(I)_{j}$ by a path that does not pass through $nod(I)$.

We define $env_{I}(a_{j})$ as the union of all vertices that are either in
$\mathcal{H}(I)_{j}$ or in $\mathbf{D}^{-}_{c}(a_{j^{\prime}})$ for some cycle
contained in $\mathcal{H}(I)_{j}\cup nod(I)$ and some (equivalently, any)
$j^{\prime}\in J\setminus\\{j\\}$. Finally, we let $env(I):=\bigcup_{j\in
J}env_{I}(a_{j})$.

######  Observation 5.12.

Suppose that $c$, $c^{\prime}$ and $d$ are cycles and $a,a^{\prime},b,v$
vertices such that $a,a^{\prime}\notin c\cup c^{\prime}$ and:

  1. (1)

$(\mathbf{D}^{+}_{c}(a)\cup c)\cap(\mathbf{D}^{+}_{c^{\prime}}(a^{\prime})\cup
c^{\prime})\subseteq\\{v\\}$

  2. (2)

$d$ is connected to $c^{\prime}$ by a path $p$ that does not go through $v$

  3. (3)

$c\cap d\subseteq\\{v\\}$

Then $\mathbf{D}^{+}_{c}(a)\cup c\subseteq\mathbf{D}^{+}_{d}(b)\cup d$ or
$(\mathbf{D}^{+}_{c}(a)\cup c)\cap(\mathbf{D}^{+}_{d}(b)\cup
d)\subseteq\\{v\\}$.

###### Proof.

Suppose the conclusion does not hold. By 1 and 3 we have that
$c^{\prime}\setminus c$ and $d\setminus c$ lie entirely on one side of $c$ and
in fact the same side, by 2. By 1 this side is $\mathbf{D}^{-}_{c}(a)$. It
then follows that $\mathbf{D}^{+}_{c}(a)\cup
c\subseteq\mathbf{D}^{+}_{d}(b)\cup d$ or $(\mathbf{D}^{+}_{c}(a)\cup
c)\cap(\mathbf{D}^{+}_{d}(b)\cup d)\subseteq\\{v\\}$ ∎

We note the following easy fact:

######  Observation 5.13.

If $a\in env_{I}(a_{j})$ is connected with $b$ by a path that does not go
through $nod(I)$, then $b\in env_{I}(a_{j})$.

######  Lemma 5.14.

The sets $env_{I}(a_{j})$ and $env_{I}(a_{j^{\prime}})$ are not connected by a
path that does not pass through $nod(I)$.

###### Proof.

Otherwise there are distinct indices $j_{1}$ and $j_{2}$ so that $b\in
env_{I}(a_{j_{1}})\cap env_{I}(a_{j_{2}})$.

Suppose that $b$ is separated from $I$ by cycles $d_{1}$ and $d_{2}$, where
$d_{i}$ is connected to some $c_{i}\in\mathcal{S}(I)_{j_{i}}$ by some path
$p_{i}$ that does not pass through $nod(I)$.

From Observation 5.12 applied to $d_{1},d_{2},a_{2},b$ with $b$ in place of
$a$ and $w$ it follows that $\mathbf{D}^{+}_{d_{1}}(b)\cup
d_{1}\subseteq\mathbf{D}^{+}_{d_{2}}(b)\cup d_{2}$. The symmetric argument
yields the opposite inclusion so that $d_{1}=d_{2}$, contradicting the
defining property of $nod(I)$.

Similarly, if $d_{2}$ as above exists but there is also
$d_{1}\in\mathcal{S}(I)_{j_{1}}$ such that
$b\in\mathbf{D}^{+}_{d_{1}}(a_{j_{1}})\cup d_{1}$, then an analogous
application of 5.12 yields
$a_{j_{1}}\in\mathbf{D}^{+}_{d_{1}}(a_{j_{1}})\subseteq\mathbf{D}^{+}_{d_{2}}(b)$,
contradicting the fact that $d_{2}$ separates $b$ and $I$.

If
$b\in\mathbf{D}^{+}_{d_{1}}(a_{j_{1}})\cap\mathbf{D}^{+}_{d_{2}}(a_{j_{2}})$
where $d_{i}\in\mathcal{S}(I)_{j_{i}}$, then $d_{1}$ and $d_{2}$ have to
cross, contradicting Lemma 5.7. The remaining cases are straightforward from
the defining property of $nod(I)$. ∎

The following can be easily checked by inspecting the definitions above:

######  Lemma 5.15.

Given $b\in env_{I}(a_{j})$ there exists some formula $\phi(x,y;z)$ such that
$\models\phi(a_{j},a_{j^{\prime}},b)$ for any $j^{\prime}\in
J\setminus\\{j\\}$ and $\phi(a^{\prime}_{j_{0}},a^{\prime}_{j_{1}},z)$ implies
$z\in env_{I}(a^{\prime}_{j_{0}})$ for any free indiscernible sequence
$(a^{\prime}_{j})_{j\in J^{\prime}}$.

######  Corollary 5.16.

For $j\in J$ the sequence $I$ is not indiscernible over any point $b\in
env_{I}(a_{j})$.

###### Proof.

Fix $b\in env_{I}(a_{j_{0}})$, $j_{0}\in J$ and consider the formula
$\phi(x,y,z)$ as above. Pick $j_{0}<j_{1}<j_{2}$ in $J$. Then
$\phi(a_{j_{0}},a_{j_{2}},b)$ and if $I$ is indiscernible over $b$ we then
have $\phi(a_{j_{1}},a_{j_{2}},b)$, so that $b\in env_{I}(j_{1})$,
contradicting 5.14. ∎

######  Corollary 5.17.

Any automorphism of $\mathbb{G}^{\iota}$ preserving $I$ setwise must preserve
$env(I)$ setwise.

######  Lemma 5.18.

Let $c$ be a cycle. Then either $env(I)$ is contained on one side of $c$ (so
in particular $env(I)\cap c=\emptyset$) or $c\subseteq env_{I}(a_{j})\cup
nod(I)$ for some $j\in J$. In the latter case we have $b\sim_{c}b^{\prime}$
for all $b,b^{\prime}\in(env_{I}(a_{j})\cup nod(I))^{c}$.

###### Proof.

If $a_{j}\in c$ for some $j$, then $c\nsubseteq env_{I}(a_{j})$, so assume
not. Likewise, if $c$ separates $a_{j_{0}}$ from $I\setminus\\{a_{j_{0}}\\}$,
then $c\subseteq\mathcal{S}(I)_{j_{0}}$. So assume $c$ does not separate $I$.
If it is connected to $\mathcal{S}(I)_{j}$ by a path that does not go through
$nod(I)$ for some $j$, then $c\subseteq env_{I}(a_{j})$ by definition, so
assume not.

Then $\mathcal{S}(I)_{j}$ lies on the $I$-side of $c$ for all $j$ and
therefore so does $\mathcal{H}(I)_{j}$ from definition 5.11. Then for any
$d\subseteq\mathcal{H}(I)_{j}\cup nod(I)$ that does not separate $I$ either
$c\subseteq\mathbf{D}^{-}_{d}(I)$ or $(\mathbf{D}^{-}_{d}(I)\cup
d)\cap\mathbf{D}^{-}_{c}(I)=\emptyset$. It follows that all of $env(I)$ lies
on the same side of $c$. If $c\subseteq env_{I}(a_{j})\cup nod(I)$ it is easy
to see that one side of $c$ is contained in $env(I)(a_{j})$ (there are two
possibilities according to whether $c$ separates $I$). ∎

##  6\. Proof of dp-minimality

######  Definition 6.1.

For a large indiscernible sequence of elements $I=(a_{j})_{j\in J}$ that fits
into a cage or nest $\mathcal{D}$ we let $env(I)=int(\mathcal{D})$. Notice
that this does not depend on the choice of $\mathcal{D}$ by Corollary 3.6.

Given an indiscernible sequence of tuples $(a_{j})_{j\in J}$,
$a_{j}=(a_{j}^{l})_{l=1}^{n}$ such that $(a^{l}_{j})_{j\in J}$ is not constant
for any $1\leq l\leq m$ we let $env(I)=\bigcup_{l=1}^{m}env((a^{l}_{j})_{j\in
J})$.

######  Definition 6.2.

Given a large indiscernible sequence of elements we write
$\widebar{env}(I)=env(I)\cup pol(\mathcal{D})$ if $env(I)$ is the interior of
a cage or nest $\mathcal{D}$ and $\widebar{env}(I)=env(I)\cup nod(I)$ if $I$
is free.

######  Lemma 6.3.

Let $I=(a_{j})_{j\in J}$, $a_{j}=(a_{j}^{l})_{l=1}^{n}$ be a large
indiscernible sequence of tuples. Then $I$ is indiscernible over a set $B$ of
parameters if and only if $B\cap env(I)=\emptyset$.

###### Proof.

We have already seen that if $B\cap env(I)\neq\emptyset$, then $I$ is not
indiscernible over $B$ (Lemma 4.1 and Corollary 5.16).

Let $\lambda:J\to J$ an order-preserving bijection. Take an automorphism
$\sigma$ of $\mathbb{G}^{\iota}$ sending $a_{j}$ to $a_{\lambda(j)}$. It is
clear from the definition that $\sigma$ preserves $env(I^{l})$ for each of the
non-constant components of $I^{l}$ of $I$. We claim that
$\sigma_{*}:=\sigma_{\restriction env(I)}\cup id_{env(I)^{c}}$ is an
automorphism of $\mathbb{G}^{\iota}$. At the level of graphs this is clear
from Lemma 3.1 and Observation 5.13 as long as $\sigma$ does not flip the two
poles of the cage associated to $I^{l}$ for some $l$. However, we can always
choose $\sigma$ so that this is the case, since the group of order preserving
automorphisms of $J$ does not contain a subgroup of index two.

Given a cycle $c$ we need to show that $\sim_{\sigma^{*}(c)}$ is the psush-
forward of $\sim_{c}$ by automorphism $\sigma^{*}$. Fix $b,b^{\prime}$ outside
of $c\cup env(I)\cup c$ and $b^{\prime\prime}\in env(I)\cup c$. It suffices to
show that $b\sim_{c}b^{\prime}$ if and only if
$b\sim_{\sigma^{*}(c)}\sigma(b)$. t

Assume first that $c\subseteq\widebar{env}(I^{l})$ for some $1\leq l\leq n$
and $c$ does not separate $I^{l}$ into two subsequences unbounded on one side
(this happens, in particular, if $c\subseteq\widebar{env}(I^{l})$ and $I^{l}$
is free). Then any two elements outside of $\widebar{env}(I^{l})$ are on the
same side of $c$ (see Lemma 5.18) and since $\sigma(c)=\sigma^{*}(c)$ has the
same property we have $\sigma(b)\sim_{\sigma(c)}b$. Then $b\sim_{c}b^{\prime}$
is equivalent to $\sigma(b)\sim_{\sigma(c)}\sigma(b^{\prime})$, in turn
equivalent $b\sim_{\sigma(c)}\sigma(b^{\prime})$ and we are done.

By virtue of Corollaries 3.2 and 5.18 and Lemma 3.2 the other possibility is
that $c$ contains a collection of finitely many subpaths $p_{1},\dots p_{r}$
with disjoint interior, where for each $1\leq i\leq m$ either $p_{i}$ crosses
from pole to pole a cage $\mathcal{D}^{i}=(\delta^{i}_{l})_{l\in L}$ in which
$I^{k_{i}}$ fits or $r=1$ and $p_{1}=c$ is contained in a nest
$\mathcal{D}^{1}$ in which some $I^{k_{1}}$ fits and separates $I^{k_{1}}$
into two subsequences unbounded on one side.

We might as well just consider the first subcase, since the other is almost
formally identical. It is easy to see that
$b^{\prime}\sim_{\sigma^{*}(c)}b^{\prime\prime}$ if and only if
$b^{\prime}\sim_{\sigma(c)}b^{\prime\prime}$ for any $b,b^{\prime\prime}\in
int(\mathcal{D}^{l})$. If $d\in int(\mathcal{D}^{i})\setminus
D^{i}_{l,l^{\prime}}$ for some $l<l^{\prime}$ in $L$ such that $c\cap
int(\mathcal{D}^{i})\subseteq D^{i}_{l,l^{\prime}}$. Then it is easy to see
that the truth value of $b\sim_{c^{\prime}}d$ is the same for any $c^{\prime}$
that is the result of replacing $p_{i}$ by $\delta^{i}_{l^{\prime\prime}}$ for
some $l^{\prime\prime}\in(l,l^{\prime\prime})$ and of replacing
$p_{i^{\prime}}$ by any path between the poles of $\mathcal{C}^{i^{\prime}}$
for $1\leq i^{\prime}\leq m$, $i\neq i^{\prime}$. The same holds for
$\sigma^{*}(c)$. It follows that if $j$ is large enough
$a^{k_{i}}_{j}\sim_{c}b$ if and only if $a^{k_{i}}_{j}\sim_{\sigma^{*}(c)}b$
while on the other hand $a^{k_{i}}_{j}\sim_{c}b^{\prime}$ if and only if
$\sigma(a^{k_{i}}_{j})\sim_{\sigma(c)}b^{\prime}$ if and only if
$a^{k_{i}}_{j}\sim_{\sigma^{*}(c)}\sigma(b^{\prime})$. This concludes the
proof.

∎

######  Lemma 6.4.

Two large indiscernible sequences of tuples $I=(a_{j})_{j\in J}$,
$I^{\prime}=(a^{\prime}_{j})_{j\in J^{\prime}}$ are mutually indiscernible
only if $env(I)\cap env(I^{\prime})=\emptyset$.

###### Proof.

We may assume $I$ and $I^{\prime}$ are sequences of elements. By the previous
Lemma we know that $env(I)\cap I^{\prime}=env(I^{\prime})\cap I=\emptyset$.

There are three possible cases.

### Both $I$ and $I^{\prime}$ fit into a cage or nest

Assume $I$ fits into $\mathcal{D}$ and $I^{\prime}$ into
$\mathcal{D}^{\prime}$, where each of $\mathcal{D}=(\delta_{l})_{l\in L}$ and
$\mathcal{D}^{\prime}=(\delta_{l})_{l\in L^{\prime}}$ is either a large cage
or a large nest.

If $pol(\mathcal{D})\neq pol(\mathcal{D}^{\prime})$ it follows from Lemma 3.5
that either $int(\mathcal{D})$ and $int(\mathcal{D}^{\prime})$ are disjoint or
one of the two sets is contained in the other, contradicting the fact that
$I\cap int(\mathcal{D}^{\prime})=I^{\prime}\cap int(\mathcal{D})=\emptyset$.

Suppose now $pol(\mathcal{D})=pol(\mathcal{D}^{\prime})$. Consider first the
case in which $\mathcal{D}$ and $\mathcal{D}^{\prime}$ are nests. For any
$l\in L$ either $\delta_{l}\subset ext(\mathcal{D}^{\prime})$ or
$\delta_{l}\subseteq D_{l^{\prime}_{0},l^{\prime}_{1}}$ for a pair
$l^{\prime}_{0},l^{\prime}_{1}\in L^{\prime}$.

In the latter case it cannot be that $\delta^{\prime}_{l^{\prime}_{0}}$ and
$\delta^{\prime}_{l^{\prime}_{1}}$ lie on the same side of $\delta_{l}$ for
then one side of $\delta_{l}$ must be contained in
$D^{\prime}_{l^{\prime}_{0},l^{\prime}_{1}}$ and thus $I\cap
int(\mathcal{D}^{\prime})\neq\emptyset$. So in that case $\delta_{l}$ must
separate the sequence $(\delta^{\prime}_{l^{\prime}})_{l^{\prime}\in L}$ into
two unbounded intervals.

If $\delta_{l}$ lies in $ext(\mathcal{D}^{\prime})$ for all $l\in L$, then
either $int(\mathcal{D}^{\prime})\subseteq int(\mathcal{D})$, which is
impossible, or $int(\mathcal{D})\cap int(\mathcal{D}^{\prime})$. We are left
with two possibilities:

  * •

There are $l_{0}<l_{1}<l_{2}\in L$ such that $\delta_{l_{k}}$ lies in
$\widebar{int}(\mathcal{D}^{\prime})$ for $k=0,1,2$. In this case
$D_{l_{0},l_{2}}\subseteq int(\mathcal{D}^{\prime})$ and $I\cap
int(\mathcal{D}^{\prime})\neq\emptyset$.

  * •

There are $l_{0},l_{1}\in L$ with
$\delta_{l_{0}}\subseteq\widebar{int}(\mathcal{D}^{\prime})$ and
$\delta_{l_{1}}\subseteq ext(\mathcal{D}^{\prime})$. It follows that
$D_{l_{0},l_{1}}$ contains $\mathring{\delta}^{\prime}_{l^{\prime}}$ for
infinitely many values of $l^{\prime}\in L$ and thus $D_{l_{0},l_{1}}\cap
I^{\prime}\neq\emptyset$.

The case analysis when $\mathcal{D}$ and $\mathcal{D}^{\prime}$ is entirely
analogous.

### The sequence $I$ fits into a cage or nest and $I^{\prime}$ is free

Suppose that $I$ fits into a large cage or nest
$\mathcal{D}=(\delta_{l})_{l\in L}$. Let $c$ be a cycle. By Lemmas 3.2 and 3.3
we have three possibilities for $c$:

  1. (1)

$c\subseteq ext(\mathcal{D})$

  2. (2)

$c\subseteq D_{l_{1},l_{2}}\cup\delta_{l_{1},l_{2}}$ for $l_{1}<l_{2}$ in $L$.

  3. (3)

$\mathcal{D}=(\delta_{l})_{l\in L}$ is a cage and $c$ is of the form $p*q$,
where $p$ lies in $ext(\mathcal{D})$ and $q$ crosses $int(\mathcal{D})$ from
pole to pole

If $c\in\mathcal{S}(I^{\prime})_{j^{\prime}}$ for some $j^{\prime}\in
J^{\prime}$, then we can rule out 2 since it implies that either $I\setminus
D_{l_{1},l_{2}}\subseteq\mathcal{X}(I^{\prime})_{j^{\prime}}$ or
$\mathcal{X}(I^{\prime})_{j^{\prime}}\subseteq int(\mathcal{D})$. Likewise, we
can rule out 3, since it implies
$I\cap\mathcal{X}(I^{\prime})_{j^{\prime}}\neq\emptyset$. Since $I\cap
env(I^{\prime})=\emptyset$, we conclude that
$\mathcal{X}(I^{\prime})_{j^{\prime}}\subseteq ext(\mathcal{D})$.

Observe that any path $q$ which starts at
$\mathcal{X}(I^{\prime})_{j^{\prime}}$ and does not pass through
$nod(I^{\prime})$ must stay in $ext(\mathcal{D})$. Otherwise $q$ crosses
$pol(\mathcal{D})$ and indiscernibility of $I^{\prime}$ over $I$ implies any
two such sets can be joined by a path avoiding $nod(I^{\prime})$, against
Lemma 5.14.

Suppose now $c$ is a cycle that is connected to
$\mathcal{S}(I^{\prime})_{j^{\prime}}$ by a path $q$ that does not go through
$nod(I^{\prime})$. The preceding remarks exclude cases 2 and 3 above, so
$c\subseteq ext(\mathcal{D})$. In case 1. Recall that
$\mathbf{D}^{-}_{c}(I^{\prime})\subseteq env_{I}(a^{\prime}_{j^{\prime}})$.
Since $I\cap env_{I}(a^{\prime}_{j^{\prime}})=\emptyset$ we must have
$\mathbf{D}^{-}_{c}(I^{\prime})\subseteq ext(\mathcal{D})$ and thus
$env(I^{\prime})\subseteq ext(\mathcal{D})=env(I)^{c}$ as desired.

### Both $I$ and $I^{\prime}$ are free

Suppose now both $I$ and $I^{\prime}$ are free and $env_{I}(a_{j})\cap
env_{I^{\prime}}(a^{\prime}_{j^{\prime}})\neq\emptyset$ for some and hence for
all $j\in J$ and $j^{\prime}\in J^{\prime}$. Fix $j_{0}\in J$ such that
$env_{I}(a_{j_{0}})$ does not intersect $nod(I^{\prime})$.

Recall that $\mathcal{H}(I)_{j}$ is the collection of vertices in
$env_{I}(a_{j_{0}})$ that can be joined to $\mathcal{X}(I)_{j}$ by a path that
does not pass through $nod(I)$. As a consequence of Lemma 5.5, the subset
$K_{j_{0}}$ of those vertices in $\mathcal{H}(I)_{j}$ that are not contained
in $\mathbf{D}^{+}_{c}(a_{j})$ for a cycle $c\in\mathcal{S}(I)_{j}$ is
connected.

It follows that $env_{I^{\prime}}(a^{\prime}_{j^{\prime}})$ cannot intersect
$K_{j_{0}}$ for any $j^{\prime}\in J^{\prime}$, since otherwise by
indiscernibility of $I^{\prime}$ over $I$ the same would hold for any other
$j^{\prime\prime}\in J^{\prime}$, and there would exist a path from
$env_{I^{\prime}}(a^{\prime}_{j^{\prime}})$ to
$env_{I^{\prime}}(a^{\prime}_{j^{\prime\prime}})$ avoiding $nod(I^{\prime})$,
contrary to 5.14.

Consider any $c^{\prime}\in\mathcal{S}(I^{\prime})_{j^{\prime}}$. We claim
that $c^{\prime}\cap\mathcal{X}(I)_{j_{0}}=\emptyset$. Suppose not. If
$c^{\prime}$ contains points both in and outside $\mathcal{X}(I)_{j_{0}}$,
then it has to intersect $K_{j_{0}}$. So in fact
$c^{\prime}\subseteq\mathcal{X}(I)_{j_{0}}$. But then it follows from Lemma
5.6 that $c^{\prime}\subset\mathbf{D}^{+}_{c}(a_{j_{0}})\cup c$ for some $c\in
S(I)_{j_{0}}$, which implies that $I^{\prime}\cap
env(a_{j_{0}})\neq\emptyset$, since $c^{\prime}$ separates $a_{j^{\prime}}$
and $I^{\prime}\setminus\\{a_{j^{\prime}}\\}$.

We conclude that
$\mathcal{X}(I^{\prime})_{j_{{}^{\prime}}}\cap\mathcal{X}(I)_{j_{0}}=\emptyset$.
Consider now $c\subset\mathcal{H}(I)_{j_{0}}\cup nod(I)$,
$c\notin\mathcal{S}(I)_{j}$. We claim that
$c^{\prime}\subseteq\mathbf{D}^{-}_{c}(I)$. By Lemma 5.6 and the discussion
above, we may assume that $c$ contains point in $K_{j_{0}}$, so $c\cap
c^{\prime}=\emptyset$. If $c^{\prime}\subseteq\mathbf{D}^{-}_{c}(I)$, then
either $I\subseteq\mathbf{D}^{+}_{c^{\prime}}(a_{j^{\prime}})$ or
$\mathbf{D}^{+}_{c^{\prime}}(a_{j^{\prime}})\subseteq\mathbf{D}^{-}_{c}(I)\subseteq
env_{I}(a_{j_{0}})$: a contradiction either way. So
$\mathbf{D}^{+}_{c^{\prime}}(a^{\prime}_{j^{\prime}})\cap\mathbf{D}^{-}_{c}(I)=\emptyset$.
We conclude that
$env_{I}(a_{j_{0}})\cap\mathcal{X}(I^{\prime})_{j^{\prime}}=\emptyset$.

Since $K_{j_{0}}\cap env_{I^{\prime}}(a_{j^{\prime}})=\emptyset$, it follows
that $\mathcal{H}(I^{\prime})_{j^{\prime}}\cap env_{I}(a_{j_{0}})=\emptyset$.
Let $c^{\prime}\subset\mathcal{H}(I^{\prime})_{j^{\prime}}$ be a cycle that
does not separate $I^{\prime}$. It easily follows that either
$env_{I}(a_{j_{0}})\subseteq\mathbf{D}^{-}_{c^{\prime}}(I^{\prime})\subseteq
env_{I^{\prime}}(a_{j^{\prime}})$ or
$env_{I}(a_{j_{0}})\cap\mathbf{D}^{-}_{c^{\prime}}(I^{\prime})=\emptyset$: a
contradiction.

∎

Given the tools above the proof of dp-minimality is straightforward.

###### Proof of Theorem 1.3.

Suppose we are given two sequences of tuples $I_{1}$ and $I_{2}$ that are
mutually indiscernible. We may assume both sequences are large. Lemma 6.4
implies $env(I_{1})\cap env(I_{2})=\emptyset$ so $b\notin env(I_{i})$ for some
$i\in\\{1,2\\}$ so that $I_{i}$ is indiscernible over $b$ by 6.3. ∎

## References

  * [1] Anton Bobkov.  Computations of Vapnik-Chervonenkis Density in Various Model-Theoretic Structures.  PhD thesis, 2017.
  * [2] Klaus-Peter Podewski and Martin Ziegler.  Stable graphs.  Fund. Math, 100(2):101–107, 1978.
  * [3] Pierre Simon.  A guide to NIP theories.  Cambridge University Press, 2015.
  * [4] Katrin Tent and Martin Ziegler.  A course in model theory.  Number 40. Cambridge University Press, 2012.


# Airavata: Introducing Hindi Instruction-tuned LLM

Jay Gala1 Thanmay Jayakumar1 Jaavid Aktar Husain1,3 Aswanth Kumar4
Mohammed Safi Ur Rahman Khan1 Diptesh Kanojia5 Ratish Puduppully6
Mitesh M. Khapra1,2 Raj Dabre7 Rudra Murthy8 Anoop Kunchukuttan1,2,9
1Nilekani Centre at AI4Bharat 2IIT Madras 3IIIT D&M Kancheepuram
4Flipkart 5University of Surrey 6A∗STAR 7NICT 8IBM Research 9Microsoft

https://ai4bharat.github.io/airavata
---
Figure 1: Image Courtesy: DALL-E 3 (Betker et al., 2023).

##  1 Introduction

The last year has witnessed tremendous interest and activity in the world of
Large Language Models (LLMs). LLMs hold the potential to unlock exciting
applications in artificial intelligence thanks to their ability to comprehend
complex natural language instructions and excel in a broad spectrum of tasks
involving language, knowledge, reasoning, and creative generation. To foster
research, innovation, and widespread adoption, an open ecosystem is essential.
We have observed significant advancements in this area with the launch of
models like Llama 2 (Touvron et al., 2023) and Mistral (Jiang et al., 2023),
as well as their instruction-tuned variants such as Llama 2 Chat (Touvron et
al., 2023), Mistral-Instruct (Jiang et al., 2023), and Zephyr (Tunstall et
al., 2023), among others. Major progress has also been made in developing
datasets for pre-training (e.g., RedPajama (Computer, 2023)), instruction
tuning (e.g., Alpaca (Taori et al., 2023), UltraChat (Ding et al., 2023),
Dolly (Conover et al., 2023), OpenAssistant (Köpf et al., 2023), LMSYS-Chat
(Zheng et al., 2023a)), and evaluation benchmarks (e.g., AlpacaEval (Dubois et
al., 2023), MT-Bench (Zheng et al., 2023b)). However, most of these
advancements have been predominantly centered on the English language.

There is limited support for Indian languages, which can be attributed to the
incidental inclusion of some Indian language data that slipped through the
data filters during the pre-training of these language models. However, the
representation of data, the efficacy of tokenizers, and task performance for
Indian languages are considerably behind that of English. The performance in
Indian languages, even on closed-source models such as ChatGPT (OpenAI, 2022),
GPT-4 (Achiam et al., 2023), and others, is inferior compared to English
(Ahuja et al., 2023). Therefore, there is an urgent need to develop a similar
ecosystem of tools, models, and datasets for Indian languages to foster
research and innovation. In pursuit of this objective, we have recently
collaborated with Sarvam AI to launch OpenHathi (SarvamAI, 2023), an open-
source foundational model for Hindi, developed by extending Llama 2 (Touvron
et al., 2023).

Today, we announce the next step – an initial release of “Airavata”, an
instruction-tuned model for Hindi built by finetuning OpenHathi (SarvamAI,
2023) with diverse, instruction-tuning Hindi datasets to make it better suited
for assistive tasks.

Along with the model, we also share the instruction tuning
datasets111https://huggingface.co/datasets/ai4bharat/indic-instruct-data-v0.1
to enable further research for IndicLLMs. We rely on human-curated, license-
friendly instruction-tuned datasets to build “Airavata”. We do not use data
generated from proprietary models like GPT-4 (Achiam et al., 2023), etc. We
think this is a more sustainable way of building instruction-tuned models at
scale for most Indic languages, where relying on distilled data from
commercial models would increase costs and restrict their free usage in
downstream applications due to licensing restrictions.

We also compile a collection of evaluation
benchmarks222https://huggingface.co/collections/ai4bharat/airavata-evaluation-
suite-65b13b7b68165de71ba0b333 along with an evaluation framework to compare
various LLMs for their abilities on diverse tasks when instructed in Hindi.
Using this benchmark and human judgments, we compare different LLMs to
quantify the current state of their Hindi capabilities. We conduct a detailed
analysis of Airavata’s performance on various Natural Language Understanding
(NLU) and Natural Language Generation (NLG) tasks and find that the
instruction fine-tuning helps align the model to various NLU tasks. There is
significant potential for improvement in NLG tasks, which require the creation
of larger, more diverse instruction datasets as well as innovations in
aligning English model representations to Hindi representations to drive
better cross-lingual transfer.

##  2 Instruction Tuning Dataset Creation

High-quality instruction tuning datasets are important for the good
performance of LLMs. However, there are few diverse datasets for Hindi.
Following (Wei et al., 2023), we rely on translating high-quality English-
supervised instruction-tuning datasets into Hindi. We use IndicTrans2 (Gala et
al., 2023), the state-of-the-art open-source MT model for Indian languages,
for translation. Some previous works (Li et al., 2023; Wei et al., 2023) have
used ChatGPT (OpenAI, 2022) to translate instructions and/or generate
responses into Hindi to better use context during translation (IndicTrans2 and
most MT models are sentence-level). However, this is not cost-effective, and
the translation quality of ChatGPT (OpenAI, 2022) is lower than IndicTrans2
(Gala et al., 2023), and its generation quality in Hindi might not be up to
the mark (Ahuja et al., 2023). A future avenue of work would be improving
translation quality when document context is available.

We sample examples from different datasets listed in Table 1 to ensure
balanced representations across all the tasks while fitting into our
instruction tuning budget. We translate the instructions, input, and outputs
into Hindi. This results in a total of 404k examples spanning English and
Hindi language. The translated Hindi examples were filtered to retain high-
quality examples. Specifically, examples were retained only when the chrF++
score (Popović, 2017) between the back-translated example and the
corresponding English example was 50 or above. The final dataset used for
instruction tuning contains 385k examples. Table 1 shows the details of the
final training dataset. The dataset can be found on the HuggingFace
Hub.333https://huggingface.co/datasets/ai4bharat/indic-instruct-data-v0.1

Dataset | Unfiltered | Filtered
---|---|---
English | Hindi | English | Hindi
FLAN-v2 (Longpre et al., 2023) | 67,463 | 67,463 | 67,463 | 65,228
Anthropic-HHH (Bai et al., 2022) | 5,000 | 5,000 | 5,000 | 4,911
Dolly (Conover et al., 2023) | 15,011 | 15,011 | 15,011 | 14,880
OpenAssistant (Köpf et al., 2023) | 19,945 | 20,128 | 19,945 | 16384
LymSys-Chat (Zheng et al., 2023a) | 50,000 | 50,000 | 50,000 | 37,422
WikiHow | 20,400 | 6,055 | 20,400 | 6,055
Anudesh | 5,234 | 7,577 | 5,234 | 7,577
Total | 183,053 | 171,234 | 183,053 | 152,457
Table 1: Instruction Fine-tuning Training Dataset Details

We also create two native Hindi Instruction datasets:

  * •

wikiHow: wikiHow444https://www.wikihow.com/Main-Page is an online wiki-style
platform that serves as a valuable resource for a diverse array of how-to
articles spanning numerous topics. The articles on the platform are human-
moderated, ensuring a high-quality standard. The questions users pose in these
articles closely align with potential use cases for this model, making it a
rich resource for training models. Additionally, this might also help induce
reasoning capabilities and generate logical step-by-step responses. We curate
around 20k and 6k articles in English and Hindi, respectively, resulting in a
total of around 27k articles. We currently formulate the data as a completion
task given either question or question along with a few initial steps. The
dataset is released under the CC-0 license.

  * •

Anudesh: Anudesh is a crowd-sourced collection of prompts accompanied by
responses generated from the Llama-2 70B model. Participants are provided with
clear guidelines detailing the nature of the interaction required, including
the specific language to be employed. These languages encompass a range that
includes Indic languages, English, transliterated Indic, as well as a blend of
Indic and English in a code-mixed format. Contributors craft their prompts in
adherence to these directives and the specified language criteria.
Subsequently, these prompts are then paired with the corresponding translated
outputs from the Llama 2 70B model (Touvron et al., 2023). The dataset is
released under CC-BY-4.0 license. More details about the interactions will be
released soon.

We provide a brief description of all the existing instruction datasets used
in addition to the above (and corresponding licenses) below:

  * •

FLAN-v2 (Longpre et al., 2023): A collection of NLP tasks that combines a
number of existing NLP datasets with various data augmentations, introduced by
Chung et al. (2022). We sample around 67K examples for our training mixture.
The dataset is released under the Apache-2.0 license.

  * •

Anthropic-HHH (Bai et al., 2022): A collection of human-collected preference
data for aligning the models to be helpful and harmless. We sample 5K
conversations from the “chosen" column for our training mixture. The dataset
is released under the MIT license.

  * •

Dolly (Conover et al., 2023): A corpus of more than 15K records generated by
thousands of Databricks employees to enable LLMs to exhibit the magical
interactivity of ChatGPT. The dataset is released under the CC-BY-SA-3.0
license.

  * •

OpenAssistant (Köpf et al., 2023): A collection of human-generated, human-
annotated assistant-style conversation corpus consisting of 38K messages,
resulting in over 3K conversation trees and around 20K conversations. The
dataset is released under the Apache-2.0.

  * •

LymSys-Chat (Zheng et al., 2023a): A collection of 1M real-world conversations
spanning 25 SOTA LLMs similar to OpenAssistant (Köpf et al., 2023). We sample
50K conversations for our training mixture. The dataset is released under the
LMSYS-Chat-1M Dataset License
Agreement.555https://huggingface.co/datasets/lmsys/lmsys-chat-1m#lmsys-
chat-1m-dataset-license-agreement

  * •

NMT (Gala et al., 2023): A multi-domain human-annotated dataset containing 50K
bitext English-Hindi translation pairs from BPCC-Human (Gala et al., 2023) to
enable better cross-lingual transfer. The dataset is released under the CC-
BY-4.0 license.

##  3 Supervised Fine-tuning

We fine-tune the OpenHathi model using the above-compiled datasets. We perform
parameter-efficient fine-tuning with LoRA (Hu et al., 2022). The
hyperparameters used are listed in the Table 2.

Hyper-Parameter | Value
---|---
LoRA Rank | 16
LoRA alpha | 32
LoRA Dropout | 0.05
LoRA Target Modules | q_proj, v_proj, k_proj, gate_proj
| up_proj, down_proj
Epochs | 4
Learning rate | 5e-4
Batch Size | 128
Floating Point Precision | bfloat16
Table 2: Hyperparameters for Fine-tuning

During fine-tuning, the loss was computed only for the output tokens. We used
the OpenInstruct framework666https://github.com/allenai/open-instruct for
fine-tuning and customizing it for our requirements (our custom version is
available as IndicInstruct777https://github.com/AI4Bharat/IndicInstruct). One
fine-tuning example corresponds to one example in the dataset. However, this
is suboptimal since many tokens are wasted as padding tokens. We plan to
optimize this process by packing multiple dataset examples into a single fine-
tuning example (Iyer et al., 2022; Krell et al., 2023).

###  3.1 Model Selection

We fine-tune the OpenHathi model for 4 epochs and save the model after each
epoch. We evaluate the checkpoint of each epoch on the dev set
(IndicSentiment, IndicCOPA, IndicXNLI, IndicQA, and Flores devtest) and
compare the average performance. We observe that the checkpoint of epoch 3
performs well on NLU tasks, while the checkpoint of epoch 4 performs well on
NLG tasks. We perform checkpoint averaging, where we interpolate the weights
of the above two checkpoints to obtain a model that performs well across both
NLU and NLG tasks. We found the best interpolation factor to be around 0.6.

$\mathrm{interpolated\hskip
2.0ptweights}=0.6\times\mathrm{checkpoint_{3}}+(1-0.6)\times\mathrm{checkpoint_{4}}$

###  3.2 Full vs. LoRA finetuning

There are two prevalent methods for instruction fine-tuning for LLMs: Full
fine-tuning and LoRA. Full fine-tuning (FFT) involves updating all the model
parameters, whereas LoRA (Hu et al., 2022) fine-tuning involves introducing a
small set of additional parameters and only updating it. We perform an
ablation study to examine both the fine-tuning strategies to train two models,
one employing full fine-tuning and the other by LoRA fine-tuning. For the
context of this ablation study, we consider the FLAN v2 (Longpre et al., 2023)
subset from our instruction dataset spanning English and Hindi. For our
evaluation, we used a subset of NLU tasks in Hindi, along with BoolQ (Clark et
al., 2019) and MMLU (Hendrycks et al., 2021) tasks in English, as development
sets to decide between full fine-tuning and LoRA fine-tuning (Figure 2). We
observed that FFT models outperform the OpenHathi base model (SarvamAI, 2023)
in IndicCopa (Doddapaneni et al., 2022) and IndicXParaphrase (Doddapaneni et
al., 2022) tasks. However, the FFT model performed poorly on English tasks
compared to the base model as well as the LoRA fine-tuned model. LoRA fine-
tuned model demonstrated improvements or similar performance as the OpenHathi
base model on both Hindi NLU and English tasks. As a result, we decided to
proceed with LoRA fine-tuning for training our final model. We report results
on the LoRA fine-tuned final model in the subsequent section.

Figure 2: Ablation experiment to understand the performance gaps between Full
fine-tuning and LoRA fine-tuning across a mix of English and Hindi NLU tasks.

##  4 Evaluation on NLP Benchmarks

We evaluate our model on the standard NLU and NLG benchmarks, which include
native Hindi test sets from IndicXTREME (Doddapaneni et al., 2022) and Indic
NLG Suite (Kumar et al., 2022). Further, to test the knowledge and reasoning
capabilities of the model in Hindi, we translate the English benchmarks such
as MMLU (Hendrycks et al., 2021), Hellaswag (Zellers et al., 2019), ARC (Clark
et al., 2018), Winogrande (Sakaguchi et al., 2020) and BoolQ (Clark et al.,
2019) and use these to evaluate our final model. The IndicTrans2 (Gala et al.,
2023) model was employed for translating the benchmarks. Although this is not
the perfect evaluation setup however, due to limited resources, we rely on
this method as a proxy indicator for assessing trends in the performance of
the model in terms of reasoning capabilities in Hindi. An important future
direction would involve creating equivalent benchmarks in the native language
instead of solely relying on this method.

###  4.1 Results

Tables 3, 4, 5 and 6 shows the comparison of Airavata with the base model
(OpenHathi) and the translate-test baseline using the Llama 2 7B Chat model.
In the translate-test approach, the Hindi input is translated into English
using the IndicTrans2 model and is used as a prompt to the Llama 2 7B Chat
model. We observe that Airavata significantly outperforms the OpenHathi model
on most tasks, demonstrating that fine-tuning on the IndicInstruct dataset
helps align the base model to a variety of tasks. Moreover, the performance of
the translate-test approach with the Llama 2 7B Chat model has a lot of
variance, while Airavata consistently performs well across tasks. OpenHathi
and Airavata exhibit comparable performance in the translation task. OpenHathi
benefits from its extensive training on parallel corpora, resulting in a
highly proficient base model for the translation task. We observe mixed
results on generation tasks, indicating the scope for further improvement of
Airvata, especially in open-ended text generation capabilities. Table 4 shows
the performance of Airavata and other models on English test sets and the
respective machine-translated Hindi test set. We observe a 5-15 point
performance gap between the English baseline and the respective Hindi baseline
across various tasks for both OpenHathi and Airavata models. This indicates
limited cross-lingual transfer of English knowledge to Hindi, highlighting the
need for future research to improve cross-lingual alignment to maximize
knowledge transfer between English and Hindi.

| 0-Shot | 5-Shot
---|---|---
| OpenHathi | Llama2 7B Chat | Airavata | OpenHathi | Llama2 7B Chat | Airavata
| (translate-test) | (translate-test)
IndicSentiment | 72.89 | 97.85 | 95.81 | 96.59 | 98.43 | 97.01
IndicCopa | 68.69 | 76.53 | 63.75 | 42.77 | 78.34 | 72.97
IndicXNLI | 16.67 | 23.67 | 73.26 | 42.25 | 47.96 | 74.70
IndicXParaphrase | 71.72 | 09.54 | 76.53 | 66.67 | 48.56 | 69.87

Table 3: F1 scores on Indic NLU and Commonsense Reasoning tasks | Variant | 0-Shot | 5-Shot
---|---|---|---
| OpenHathi | Airavata | OpenHathi | Airavata
MMLU | English | 36.16 | 41.39 | 40.12 | 43.28
Hindi (Translated) | 32.27 | 34.96 | 35.13 | 36.00
BoolQ | English | 52.63 | 73.00 | 64.46 | 62.02
Hindi (Translated) | 58.56 | 64.50 | 65.69 | 51.47
ARC Easy | English | 57.28 | 70.50 | 62.12 | 71.04
Hindi (Translated) | 44.28 | 54.00 | 49.87 | 54.84
Arc Challenge | English | 39.85 | 45.90 | 46.25 | 48.29
Hindi (Translated) | 32.68 | 35.92 | 36.60 | 36.26
Hella Swag | English | 31.48 | 34.37 | 32.45 | 36.83
Hindi (Translated) | 25.59 | 25.37 | 24.85 | 24.84
Winogrande | English | 49.17 | 49.72 | - | -
Table 4: Accuracy on English NLU and Commonsense Reasoning tasks and its translated variants | Metric | 0-Shot | 5-shot
---|---|---|---
OpenHathi | Airavata | OpenHathi | Airavata
Flores | chrF++ | 55.41 | 54.82 | 54.98 | 54.24
BLEURT | 0.7103 | 0.6970 | 0.7115 | 0.7084
IN22-Gen | chrF++ | 54.23 | 53.78 | 54.53 | 52.81
BLEURT | 0.7156 | 0.7012 | 0.7181 | 0.7037
Table 5: chrF++ and BLEURT scores on English-Hindi translation task | Metric | 1-shot
---|---|---
OpenHathi | Llama 2 7B Chat | Airavata
(translate-test)
Indic QA (No Context) | F1 | 17 | 4.58 | 21.01
Indic QA (With Context) | F1 | 20.69 | 19.59 | 37.69
Indic Headline | Rouge L | 11.26 | 23.06 | 12.32
BLEURT | 0.4682 | 0.4590 | 0.3793
IndicWikiBio | Rouge L | 20.45 | 41.01 | 10.66
BLEURT | 0.5185 | 0.6415 | 0.4279
Table 6: F1, Rouge L and BLEURT scores on Indic NLG tasks

##  5 Human Evaluation

We assess Airavata using authentic prompts provided by real users, evaluating
its performance across five distinct abilities outlined in Table 7.

AbilityName | Ability
---|---
Long | Ability to generate long-form text like writing essays, speeches, reports, etc.
Fact-Ops | Ability to give factual opinions and explanations like seeking recommendations,
| seeking advice, opinions, explanations, etc.
Content | Ability to make content accessible like summarizations, layman
| explanations, etc
Lang-Creativity | Ability to be creative in language like finding anagrams, rhyming words,
| vocabulary enhancement, etc
Culture | Ability to answer questions related to Indian Culture.
Table 7: Description of abilities to test through human evaluation

We define a set of intents and domains of focus, which are then provided to
users, along with clear instructions on the type of prompts they should
construct. More details about the benchmark will be released soon.

Along with Airavata, we also evaluate ChatGPT (OpenAI, 2022), GPT-4 (Achiam et
al., 2023) and BactrianX-llama-7B (Li et al., 2023) models for the same
abilities. BactrianX-llama-7B is an instructed fine-tuned model for Hindi
directly fine-tuned with the Llama base model on a multilingual instruction
dataset. This multilingual instruction dataset consisted of machine-translated
instructions from Alpaca Taori et al. (2023) and Dolly Conover et al. (2023)
datasets, followed by response generation from ChatGPT (OpenAI, 2022).
Annotators were presented with a prompt and a randomly selected response from
any of the models and were instructed to provide ratings based on the metrics
outlined in Table 8.

Metric | Details | Range
---|---|---
IFA: Instruction Following Ability |  This assesses the model’s ability to accurately and effectively follow the instructions provided in the prompt | 0-2
CNS: Closeness to Native Speaker |  This assesses how naturally and fluently the model’s responses align with the way a native Hindi speaker would express the same ideas. | 0-2
CQ: Content Quality |  This evaluates the response in terms of its factual accuracy, logical flow of ideas, and overall informational relevance. | 0-2
Table 8: Rubrics for Human Evaluation

In addition to the above metrics, we also ask the human evaluators to give a
final score between 1 and 5, reflecting their overall satisfaction with the
response.

We sample a set of 50
prompts888https://huggingface.co/datasets/ai4bharat/human-eval covering
various intents and domains (more details about the benchmark will be made
available soon) and generate the responses from all three models. The prompt-
response pairs were shuffled randomly and anonymized, ensuring no indication
of the generating model, before being presented to the annotators for
evaluation. Annotators were instructed to assess responses strictly adhering
to the aforementioned rubrics. We report the various results in Figures 3, 4
and 5.

Figure 3: Average satisfaction scores for various models based on a Likert
scale between 1 and 5 reported by Human annotators. Figure 4: Human evaluation
scores for assessing the instruction following and content generation
abilities of the models based on the rubrics described in Table 8.

Our observations suggest that while Airavata still trails significantly behind
GPT-4 in terms of its ability to follow instructions and the quality of its
content, it performs relatively better when generating natural-sounding Hindi
content compared to both GPT-4 and ChatGPT. Notably, Airavata outperforms the
BactrianX-llama-7B model by a significant margin. This difference in
performance can be attributed to a lack of vocabulary expansion in BactrainX-
llama-7B to accommodate additional Hindi tokens and its lack of continual pre-
training in Hindi. Furthermore, BactrainX-llama-7B may be trained on a lower-
quality dataset for instruction tuning that was completely generated using
ChatGPT. The OpenHathi model and Airavata, however, have addressed these
shortcomings and show substantial improvements over the BactrainX-llama-7B
model. We will explore these performance trends across various capabilities in
more detail below.

Figure 5: Fine-grained human evaluation of content generation abilities of the
models described in Table 7.

The findings indicate that amongst all abilities, Airavata particularly excels
in providing factual opinions and explanations, as demonstrated by the earlier
examples. However, the model struggles with tasks demanding creative language
usage, likely because our SFT data lacks components emphasizing creativity.
When comparing GPT-4 and ChatGPT (GPT-3.5) performance, GPT-4 generally
surpasses its counterpart in knowledge-intensive or creativity-demanding
tasks. Nevertheless, it’s noteworthy that ChatGPT either outperforms or
competes well in tasks emphasizing language generation, such as long-form
content creation, offering factual opinions, and ensuring content
accessibility.

We acknowledge that our current human evaluation is not robust and thorough
due to the limited number of prompts in our set and each prompt and response
pair being evaluated by only one annotator. However, our evaluation still
offers valuable preliminary insights that will inform our efforts to improve
the model. Expanding the instruction dataset to include content covering a
diverse range of abilities can help improve the model’s capabilities. At the
same time, it is important to acknowledge that a significant portion of
knowledge stems from English, which possesses the most extensive knowledge
repository. Therefore, achieving better cross-lingual alignment between Hindi
and English representations is essential for accurately answering factual
questions and minimizing erroneous responses.

##  6 Resources

You can find all the details about the project in this section. We release the
following resources to facilitate further research in instruction-tuning for
Indian language LLMs.

  * •

Airavata Github Repository (for fine-tuning and evaluation)

  * •

Airavata SFT Dataset Collection: Huggingface

  * •

Airavata Evaluation Dataset Collection: Huggingface

##  7 Summary and Future Outlook

We release Airavata, an open-source, instruction-tuned Hindi model
demonstrating promising performance across various tasks compared to existing
open-source models. We provide both datasets and models to facilitate further
research in improving Hindi LLMs. This marks an initial stride towards
developing high-quality, open-source LLMs for Indian languages that require
multi-faceted efforts ranging from the creation of extensive pre-training
datasets, diverse instruction tuning datasets, and high-quality foundational
models.

##  8 Limitations

Airavata, like other LLMs, faces common challenges such as potential
hallucinations, resulting in the generation of fabricated information, and may
struggle with accuracy in complex or specialized topics. There is also a risk
of generating objectionable or biased content. Its understanding of cultural
nuances and effectiveness in mixed-language contexts may be constrained.
Furthermore, the model’s performance is closely tied to the quality and scope
of its training data, influencing its efficacy and reliability. It is crucial
to note that this model is designed for research purposes and is not
recommended for any production use-cases.

## References

  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, et al.  Gpt-4 technical report.  2023\.  URL https://api.semanticscholar.org/CorpusID:257532815.
  * Ahuja et al. (2023) Kabir Ahuja, Harshita Diddee, Rishav Hada, Millicent Ochieng, Krithika Ramesh, Prachi Jain, Akshay Nambi, Tanuja Ganu, Sameer Segal, Mohamed Ahmed, Kalika Bali, and Sunayana Sitaram.  MEGA: Multilingual evaluation of generative AI.  In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pp. 4232–4267, Singapore, December 2023. Association for Computational Linguistics.  doi: 10.18653/v1/2023.emnlp-main.258.  URL https://aclanthology.org/2023.emnlp-main.258.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv: 2204.05862_ , 2022.
  * Betker et al. (2023) James Betker, Gabriel Goh, Li Jing, Tim Brooks, Jianfeng Wang, Linjie Li, Long Ouyang, Juntang Zhuang, Joyce Lee, Yufei Guo, Wesam Manassra, Prafulla Dhariwal, Casey Chu, Yunxin Jiao, and Aditya Ramesh.  Improving image generation with better captions, October 2023.  URL https://cdn.openai.com/papers/dall-e-3.pdf.
  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, et al.  Scaling instruction-finetuned language models.  _arXiv preprint arXiv: 2210.11416_ , 2022.
  * Clark et al. (2019) Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova.  BoolQ: Exploring the surprising difficulty of natural yes/no questions.  In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 2924–2936, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1300.  URL https://aclanthology.org/N19-1300.
  * Clark et al. (2018) Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord.  Think you have solved question answering? try arc, the ai2 reasoning challenge.  _arXiv preprint arXiv: 1803.05457_ , 2018.
  * Computer (2023) Together Computer.  Redpajama: an open dataset for training large language models, October 2023.  URL https://github.com/togethercomputer/RedPajama-Data.
  * Conover et al. (2023) Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin.  Free dolly: Introducing the world’s first truly open instruction-tuned llm, 2023.  URL https://www.databricks.com/blog/2023/04/12/dolly-first-open-commercially-viable-instruction-tuned-llm.
  * Ding et al. (2023) Ning Ding, Yulin Chen, Bokai Xu, Yujia Qin, Zhi Zheng, Shengding Hu, Zhiyuan Liu, Maosong Sun, and Bowen Zhou.  Enhancing chat language models by scaling high-quality instructional conversations.  _arXiv preprint arXiv:2305.14233_ , 2023.
  * Doddapaneni et al. (2022) Sumanth Doddapaneni, Rahul Aralikatte, Gowtham Ramesh, Shreyansh Goyal, Mitesh M. Khapra, Anoop Kunchukuttan, and Pratyush Kumar.  Towards leaving no indic language behind: Building monolingual corpora, benchmark and models for indic languages.  _Annual Meeting of the Association for Computational Linguistics_ , 2022.  doi: 10.18653/v1/2023.acl-long.693.
  * Dubois et al. (2023) Yann Dubois, Xuechen Li, Rohan Taori, Tianyi Zhang, Ishaan Gulrajani, Jimmy Ba, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Alpacafarm: A simulation framework for methods that learn from human feedback, 2023.
  * Gala et al. (2023) Jay Gala, Pranjal A Chitale, A K Raghavan, Varun Gumma, Sumanth Doddapaneni, Aswanth Kumar M, Janki Atul Nawale, Anupama Sujatha, Ratish Puduppully, Vivek Raghavan, Pratyush Kumar, Mitesh M Khapra, Raj Dabre, and Anoop Kunchukuttan.  Indictrans2: Towards high-quality and accessible machine translation models for all 22 scheduled indian languages.  _Transactions on Machine Learning Research_ , 2023.  ISSN 2835-8856.  URL https://openreview.net/forum?id=vfT4YuzAYA.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt.  Measuring massive multitask language understanding.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=d7KBjmI3GmQ.
  * Hu et al. (2022) Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen.  LoRA: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=nZeVKeeFYf9.
  * Iyer et al. (2022) Srinivasan Iyer, Xi Victoria Lin, Ramakanth Pasunuru, Todor Mihaylov, Daniel Simig, Ping Yu, Kurt Shuster, Tianlu Wang, Qing Liu, Punit Singh Koura, Xian Li, Brian O’Horo, Gabriel Pereyra, Jeff Wang, Christopher Dewan, Asli Celikyilmaz, Luke Zettlemoyer, and Ves Stoyanov.  Opt-iml: Scaling language model instruction meta learning through the lens of generalization.  _arXiv preprint arXiv: 2212.12017_ , 2022.
  * Jiang et al. (2023) Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, et al.  Mistral 7b.  _arXiv preprint arXiv: 2310.06825_ , 2023.
  * Krell et al. (2023) Mario Michael Krell, Matej Kosec, Sergio P. Perez, and Andrew William Fitzgibbon.  Efficient sequence packing without cross-contamination: Accelerating large language models without impacting performance, 2023.  URL https://openreview.net/forum?id=ZAzSf9pzCm.
  * Kumar et al. (2022) Aman Kumar, Himani Shrotriya, Prachi Sahu, Amogh Mishra, Raj Dabre, Ratish Puduppully, Anoop Kunchukuttan, Mitesh M. Khapra, and Pratyush Kumar.  IndicNLG benchmark: Multilingual datasets for diverse NLG tasks in Indic languages.  In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pp. 5363–5394, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.emnlp-main.360.  URL https://aclanthology.org/2022.emnlp-main.360.
  * Köpf et al. (2023) Andreas Köpf, Yannic Kilcher, Dimitri von Rütte, Sotiris Anagnostidis, Zhi-Rui Tam, Keith Stevens, Abdullah Barhoum, Nguyen Minh Duc, Oliver Stanley, Richárd Nagyfi, Shahul ES, Sameer Suri, David Glushkov, Arnav Dantuluri, Andrew Maguire, Christoph Schuhmann, Huu Nguyen, and Alexander Mattick.  Openassistant conversations - democratizing large language model alignment.  _arXiv preprint arXiv: 2304.07327_ , 2023.
  * Li et al. (2023) Haonan Li, Fajri Koto, Minghao Wu, Alham Fikri Aji, and Timothy Baldwin.  Bactrian-x: Multilingual replicable instruction-following models with low-rank adaptation.  _arXiv preprint arXiv: 2305.15011_ , 2023.
  * Longpre et al. (2023) S. Longpre, Le Hou, Tu Vu, Albert Webson, Hyung Won Chung, Yi Tay, Denny Zhou, Quoc V. Le, Barret Zoph, Jason Wei, and Adam Roberts.  The flan collection: Designing data and methods for effective instruction tuning.  _International Conference on Machine Learning_ , 2023.  doi: 10.48550/arXiv.2301.13688.
  * OpenAI (2022) OpenAI.  Gpt3.5, November 2022.  URL https://platform.openai.com/docs/models/gpt-3-5.
  * Popović (2017) Maja Popović.  chrF++: words helping character n-grams.  In _Proceedings of the Second Conference on Machine Translation_ , pp. 612–618, Copenhagen, Denmark, September 2017. Association for Computational Linguistics.  doi: 10.18653/v1/W17-4770.  URL https://aclanthology.org/W17-4770.
  * Sakaguchi et al. (2020) Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Winogrande: An adversarial winograd schema challenge at scale.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pp. 8732–8740. AAAI Press, 2020.  doi: 10.1609/AAAI.V34I05.6399.  URL https://doi.org/10.1609/aaai.v34i05.6399.
  * SarvamAI (2023) SarvamAI.  Openhathi series: An approach to build bilingual llms frugally, December 2023.  URL https://www.sarvam.ai/blog/announcing-openhathi-series.
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto.  Stanford alpaca: An instruction-following llama model.  https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, et al.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv: 2307.09288_ , 2023.
  * Tunstall et al. (2023) Lewis Tunstall, Edward Beeching, Nathan Lambert, Nazneen Rajani, Kashif Rasul, Younes Belkada, Shengyi Huang, Leandro von Werra, Clémentine Fourrier, Nathan Habib, Nathan Sarrazin, Omar Sanseviero, Alexander M. Rush, and Thomas Wolf.  Zephyr: Direct distillation of lm alignment.  _arXiv preprint arXiv: 2310.16944_ , 2023.
  * Wei et al. (2023) Xiangpeng Wei, Haoran Wei, Huan Lin, Tianhao Li, Pei Zhang, Xingzhang Ren, Mei Li, Yu Wan, Zhiwei Cao, Binbin Xie, Tianxiang Hu, Shangjie Li, Binyuan Hui, Bowen Yu, Dayiheng Liu, Baosong Yang, Fei Huang, and Jun Xie.  Polylm: An open source polyglot large language model.  _arXiv preprint arXiv: 2307.06018_ , 2023.
  * Zellers et al. (2019) Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi.  HellaSwag: Can a machine really finish your sentence?  In Anna Korhonen, David Traum, and Lluís Màrquez (eds.), _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 4791–4800, Florence, Italy, jul 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1472.  URL https://aclanthology.org/P19-1472.
  * Zheng et al. (2023a) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Tianle Li, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zhuohan Li, Zi Lin, Eric. P Xing, Joseph E. Gonzalez, Ion Stoica, and Hao Zhang.  Lmsys-chat-1m: A large-scale real-world llm conversation dataset, 2023a.
  * Zheng et al. (2023b) Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and Ion Stoica.  Judging llm-as-a-judge with mt-bench and chatbot arena.  _arXiv preprint arXiv: 2306.05685_ , 2023b.

##  Appendix A Examples

In this section, we show example generations from Airavata. Note that the
model’s outputs in examples #A3 and #A6 did not contain newlines between
bullet points. They have been added here for readability.

###  A.1 Examples where the Airavata model generates good output

Airavata excels in specific content generation tasks, such as soliciting mail
drafts (#A1) and addressing general how-to inquiries (#A5, #A6). Furthermore,
it demonstrates proficiency in adhering to instructions related to output
structure (#A3 and #A4).

###  A.2 Examples where Airavata output has errors

The model is prone to hallucinations and can present distorted facts as
against the plot of the novel in #B1 or may fail to follow the instructions
provided (#B2).