# On large externally definable sets in NIP

Martin Bays  Institut für Mathematische Logik und Grundlagenforschung,
Fachbereich Mathematik und Informatik, Universität Münster, Einsteinstrasse
62, 48149 Münster, Germany<EMAIL_ADDRESS>,  Omer Ben-Neria  Einstein
Institute of Mathematics, Hebrew University of Jerusalem, 91904, Jerusalem
Israel<EMAIL_ADDRESS>,  Itay Kaplan  Einstein Institute of
Mathematics, Hebrew University of Jerusalem, 91904, Jerusalem Israel.
<EMAIL_ADDRESS>and  Pierre Simon  Dept. of Mathematics, University of
California, Berkeley, 970 Evans Hall #3840, Berkeley, CA 94720-3840 USA
<EMAIL_ADDRESS>
###### Abstract.

We study cofinal systems of finite subsets of $\omega_{1}$. We show that while
such systems can be NIP, they cannot be defined in an NIP structure. We deduce
a positive answer to a question of Chernikov and Simon from 2013: in an NIP
theory, any uncountable externally definable set contains an infinite
definable subset. A similar result holds for larger cardinals.

Bays was partially supported by DFG EXC 2044–390685587 and ANR-DFG AAPG2019
(Geomod). Ben-Neria was partially supported by the Israel Science Foundation,
Grant 1832/19. Kaplan would like to thank the Israel Science Foundation (ISF)
for their support of this research (grants no. 1254/18 and 804/22). Simon was
partially supported by the NSF (grants no. 1665491 and 1848562).

##  1\. Introduction

Suppose that $M$ is a structure and $x$ a tuple of variables. Recall that a
set $X\subseteq M^{x}$ is $M$-definable if there is some formula $\phi(x)$
over $M$ such that $\phi(M)=X$. The set $X$ is externally definable if there
is some elementary extension $N\succ M$ and a formula $\psi(x)$ over $N$ such
that $X=\psi(M)=\\{a\in M^{x}\mid N\vDash\psi(a)\\}$.

When $\operatorname{Th}(M)$ is stable, all externally definable subsets are in
fact $M$-definable (this is a characterization of stability: all types over
any model are definable).

Let $T$ be a theory. We consider the following natural question:

######  Question 1.1.

Is there some (infinite) cardinal $\lambda$ such that for any $M\vDash T$ and
any externally definable set $X\subseteq M^{k}$, if $|X|\geq\lambda$ then $X$
contains an infinite $M$-definable subset?

We cannot hope to say much about externally definable sets in arbitrary
theories. In particular, supposing that $T$ has a strong form of IP, the
answer to 1.1 is negative (see Remark 5.5). On the other hand:

######  Fact 1.2.

[2, Corollary 1.12] Suppose $T$ is NIP. Then the answer to 1.1 is positive:
one can take $\lambda=\beth_{\omega}$.

For a complete theory $T$, let $\text{ext}(T)$ be the minimal $\lambda$ as in
1.1 if such exists, and $\text{ext}(T)=\infty$ otherwise. If $T$ is NIP, Fact
1.2 shows that $\text{ext}(T)\leq\beth_{\omega}$. We first observe that we
cannot hope to improve this to $\text{ext}(T)=\aleph_{0}$.

######  Example 1.3.

[2, just above Question 1.13] Let $M$ be the linear order
$(\omega+\mathbb{Z},<)$, whose theory is NIP (and even dp-minimal, see [7,
Proposition A.2]). Then, $\omega$ is externally definable (as is any cut), but
no infinite subset of $\omega$ is $M$-definable, since $\operatorname{Th}(M)$
has quantifier elimination after adding the successor and predecessor
functions. Thus, $\text{ext}(\operatorname{Th}(M))\geq\aleph_{1}$.

In their paper [2, Question 1.13], Chernikov and Simon posed the following
question:

> Is it true that $\text{ext}(T)\leq\aleph_{1}$ whenever $T$ is NIP?

In this paper we positively answer this question (see 1.1). We use the
existence of honest definitions (see Definitions 2.3 and 2.4). Let
$X=\phi(M,c)$ be externally definable and uncountable and let $\psi(x,z)$ be
an honest definition for $\operatorname{tp}_{\phi^{\operatorname{opp}}}(c/M)$.
This means that for every finite set $X_{0}\subseteq X$, there is some $d\in
M^{z}$ such that

(*) $X_{0}=\phi(X_{0},c)\subseteq\psi(M,d)\subseteq\phi(M,c)=X.$

If one of these sets $Y_{d}:=\psi(M,d)$ is infinite we are done, so assume for
all $d$ as in Eq. *, $Y_{d}$ is finite. We get a family of finite subsets of
$X$ which is cofinal as a subset of the partial order $\SS^{<\omega}(X)$ of
finite subsets of $X$. This raises the question:

######  Question 1.4.

Suppose $\mathcal{F}$ is a cofinal family of finite subsets of $\aleph_{1}$.
Can $\mathcal{F}$ have finite VC-dimension?

In other words, can the relation
$\mathord{\in}|_{(\aleph_{1}\times\mathcal{F})}$ be NIP?

In Theorem 3.8 we give a positive answer to 1.4. This means that the fact that
the honest definition is NIP is not in itself a guarantee that $X$ has an
infinite $M$-definable subset (see Remark 5.2).

On the other hand, we prove that if $\mathcal{F}$ is a cofinal family of
finite subsets of $\aleph_{1}$, then the two-sorted structure
$(\aleph_{1},\mathcal{F};\mathord{\in})$ has IP. We conclude (in Theorem 5.1):

######  Main Theorem 1.1.

For $T$ NIP, $\text{ext}(T)\leq\aleph_{1}$.

###  1.1. A generalisation to arbitrary cardinals

We also consider the following generalisation of 1.1.

######  Question 1.5.

Let $T$ be a theory and $\kappa$ an infinite cardinal. Is there some cardinal
$\lambda$ such that for any $M\vDash T$ and any externally definable set
$X\subseteq M^{k}$, if $|X|\geq\lambda$ then $X$ contains an $M$-definable
subset of size $\geq\kappa$?

For a complete theory $T$, let $\text{ext}(T,\kappa)$ be the minimal $\lambda$
as in 1.5 (if it does not exist, let $\text{ext}(T,\kappa)=\infty$). So
$\text{ext}(T)=\text{ext}(T,\aleph_{0})$. The proof of [2, Corollary 1.12] can
easily be adapted to show that if $T$ is NIP then
$\text{ext}(T,\kappa)\leq\beth_{\omega}(\kappa)$.

The following slight adaptation of Example 1.3 gives us an NIP theory $T$
(namely DLO) with $\text{ext}(T,\kappa)\geq\kappa^{+}$ for
$\kappa\geq\aleph_{1}$. Let $I$ be an extension of the linear order
$(\kappa,<)$ where between any two ordinals we put a copy of $\mathbb{Q}$. Let
$M=\mathbb{Q}+I+\mathbb{Q}$. Then $\mathcal{M}$ is a dense linear order and
thus $\operatorname{Th}(\mathcal{M})$ has quantifier elimination. The set $I$
is externally definable but contains no $M$-definable subset of size $\kappa$.

In fact we prove the main theorem, Theorem 5.1, in this generality: if $T$ is
NIP then $\text{ext}(T,\kappa)\leq\kappa^{+}$.

###  1.2. Structure of the paper

In Section 2, we give the necessary preliminaries on NIP and honest
definitions. In Section 3 we discuss 1.4. In Section 4 we prove the technical
lemmas needed to prove Theorem 5.1, which is proven in Section 5 and
supplemented by some open questions.

In a previous version of this paper there was a mistake in the proof of
Theorem 3.8 (pointed out to us by George Peterzil). The old proof involved the
construction of well orders of order type $\omega$ on countable ordinals which
agree up to finite sets. Since this result may be of independent interest, we
put it in Appendix A.

###  1.3. Acknowledgements

The work on this project started while the third author was a visiting
researcher at the 2021 Thematic Program on Trends in Pure and Applied Model
Theory at the Fields Institute, and he would like to thank the Fields
Institute for their hospitality.

We would like to thank George Peterzil for pointing out an error in the proof
of Theorem 3.8 that appeared in a previous version. We would also like to
thank the anonymous referee for their meticulous reading and useful comments.

##  2\. Preliminaries

###  2.1. Notations

Our notation is standard. We use $\mathcal{L}$ to denote a first order
language and $\phi(x,y)$ to denote a formula $\phi$ with a partition of
(perhaps a superset of) its free variables. Let ${\phi^{\operatorname{opp}}}$
be the partitioned formula $\phi(y,x)$ (it is the same formula with the
partition reversed).

$T$ will denote a complete theory in $\mathcal{L}$, and $\mathcal{U}\vDash T$
will be a monster model (a sufficiently large saturated model).

When $x$ is a tuple of variables and $A$ is a set contained in some structure
(perhaps in a collection of sorts), we write $A^{x}$ to denote the tuples of
the sort of $x$ (and of length $|x|$) of elements from $A$; alternatively, one
may think of $A^{x}$ as the set of assignments of the variables $x$ to $A$. If
$M$ is a structure and $A\subseteq M^{x}$, $b\in M^{y}$, then
$\phi(A,b)=\\{a\in A\mid M\vDash\phi(a,b)\\}$.

When $B\subseteq\mathcal{U}$, $\mathcal{L}(B)$ is the language $\mathcal{L}$
augmented with constants for elements from $B$ so that a set is $B$-definable
if it is definable in $\mathcal{L}(B)$.

For an $\mathcal{L}$-formula $\phi(x,y)$, an instance of $\phi$ over
$B\subseteq\mathcal{U}$ is a formula $\phi(x,b)$ where $b\in B^{y}$, and a
(complete) $\phi$-type over $B$ is a maximal partial type consisting of
instances and negations of instances of $\phi$ over $B$. We write
$S_{\phi}(B)$ for the space of $\phi$-types over $B$ in $x$ (in this notation
we keep in mind the partition $(x,y)$, and $x$ is the first tuple there). We
also use the notation $\phi^{1}=\phi$ and $\phi^{0}=\neg\phi$. For
$a\in\mathcal{U}^{x}$, we write $\operatorname{tp}_{\phi}(a/B)\in S_{\phi}(B)$
for its $\phi$-type over $B$.

###  2.2. VC-dimension and NIP

######  Definition 2.1 (VC-dimension).

Let $X$ be a set and $\mathcal{F}\subseteq\SS(X)$. The pair $(X,\mathcal{F})$
is called a set system. We say that $A\subseteq X$ is shattered by
$\mathcal{F}$ if for every $S\subseteq A$ there is $F\in\mathcal{F}$ such that
$F\cap A=S$. A family $\mathcal{F}$ is said to be a VC-class on $X$ if there
is some $n<\omega$ such that no subset of $X$ of size $n$ is shattered by
$\mathcal{F}$. In this case the VC-dimension of $\mathcal{F}$, denoted by
$\operatorname{VC}(\mathcal{F})$, is the smallest integer $n$ such that no
subset of $X$ of size $n+1$ is shattered by $\mathcal{F}$.

If no such $n$ exists, we write $\operatorname{VC}(\mathcal{F})=\infty$.

######  Definition 2.2.

Suppose $T$ is an $\mathcal{L}$-theory and $\phi(x,y)$ is a formula. Say
$\phi(x,y)$ is NIP if for some/every $M\vDash T$, the family
$\\{\phi(M^{x},a)\mid a\in M^{y}\\}$ is a VC-class. Otherwise, $\phi$ is IP
(IP stands for “Independence Property” while NIP stands for “Not IP”).

The theory $T$ is NIP if all formulas are NIP. A structure $M$ is NIP if
$\operatorname{Th}(M)$ is NIP.

######  Definition 2.3.

[7, Definition 3.16 and Remark 3.14] Suppose $T$ is an $\mathcal{L}$-theory
and $M\vDash T$. Suppose that $\phi(x,y)$ is a formula, $A\subseteq M^{x}$ is
some set and $b\in\mathcal{U}^{y}$. Say that an $\mathcal{L}$-formula
$\psi(x,z)$ (with $z$ a tuple of variables each of the same sort as $x$) is an
honest definition of $\operatorname{tp}_{\phi^{\operatorname{opp}}}(b/A)$ if
for every finite $A_{0}\subseteq A$ there is some $c\in A^{z}$ such

$\phi(A_{0},b)\subseteq\psi(A,c)\subseteq\phi(A,b).$

In other words, for all $a\in A$, if $\psi(a,c)$ holds then so does
$\phi(a,b)$ and for all $a\in A_{0}$ the other direction holds: if $\phi(a,b)$
holds then $\psi(a,c)$ holds.

The existence of honest definitions for NIP theories was first proved in [2].
This was improved in [3] to get _uniformity_ of the honest definitions
assuming that $T$ is NIP. This was subsequently improved to:

######  Fact 2.4.

[1, Corollary 5.23] If $\phi(x,y)$ is NIP then there is a formula $\psi(x,z)$
that serves as an honest definition for any ${\phi^{\operatorname{opp}}}$-type
over any set $A$ of size $\geq 2$.

We also recall the Shelah expansion.

######  Definition 2.5.

For a structure $M$, the Shelah expansion $M^{\text{Sh}}$ of $M$ is given by:
for any formula $\phi(x,y)$ and any $b\in\mathcal{U}^{y}$, add a new relation
$R_{\phi(x,b)}(x)$ interpreted as $\phi(M,b)$.

######  Fact 2.6.

[6] If $T$ is NIP then for any $M\vDash T$, $M^{\text{Sh}}$ is NIP.

##  3\. The VC-dimension of cofinal families of finite subsets of an
uncountable set

The goal of this section is to answer 1.4.

######  Definition 3.1.

We say that a set $\mathcal{F}$ of subsets of a set $X$ is $\omega$-cofinal if
every finite subset of $X$ is contained in some element of $\mathcal{F}$. (In
the case that $\mathcal{F}$ consists of finite subsets of $X$, we omit
“$\omega$-”.)

We start with an easy observation.

######  Remark 3.2.

If $\mathcal{F}$ is an $\omega$-cofinal family of subsets of an infinite set
$X$ such that if $s\in\mathcal{F}$ then $|s|<|X|$, then
$\in|_{(X\times\mathcal{F})}$ is unstable: there exist
$(x_{i},s_{i})_{i\in\omega}$ such that $x_{i}\in s_{j}$ iff $i\leq j$. Indeed,
inductively choose $x_{i}\in X$ and $s_{i}\in\mathcal{F}$ such that
$x_{i}\notin\bigcup_{j<i}s_{j}$ and $s_{i}$ contains $\\{x_{j}\mid j\leq
i\\}$.

The proof of [2, Corollary 1.12(2)] can be adapted to say that if
$|X|\geq\beth_{\omega}$ and $\mathcal{F}$ is a cofinal family of finite
subsets of $X$ then $\mathcal{F}$ is not a VC-class (i.e., it has IP). In
fact, one can also make a connection between the VC-dimension of $\mathcal{F}$
and the cardinality of $X$ (via the alternation rank of the appropriate
relation). The next proposition replaces $\beth_{\omega}$ with
$\aleph_{\omega}$, and gives a precise lower bound on the VC-dimension in
terms of the cardinality of $X$.

######  Proposition 3.3.

If $|X|\geq\aleph_{n}$, then any cofinal system $\mathcal{F}$ of finite
subsets of $X$ has VC-dimension $>n$. So any cofinal set system of finite sets
on a set of size $\geq\aleph_{\omega}$ has IP.

###### Proof.

We may assume $X=\aleph_{n}$.

For finite subsets $A,B\subseteq X$, write $A\vdash B$ to mean that if
$D\in\mathcal{F}$ contains $A$ then $D\cap B\neq\emptyset$, and write
$A\not\vdash B$ for the negation of this.

######  Observation 3.4.

We have $A\not\vdash\emptyset$ for any $A$, since $\mathcal{F}$ is cofinal.

######  Observation 3.5.

If $A\not\vdash B$, then there are only finitely many $c\in X$ such that
$A\vdash B\cup\\{c\\}$. (Indeed, if $D\in\mathcal{F}$ witnesses $A\not\vdash
B$, then we must have $c\in D$.)

######  Observation 3.6.

If $A^{\prime}\subseteq A$ and $A\not\vdash B$ then $A^{\prime}\not\vdash B$.

We find $c_{i}\in\aleph_{i}$ for $0\leq i\leq n$ by downwards induction such
that for $k=n,...,0,-1$:

(+)k $\left\\{\begin{minipage}{346.89731pt} for any partition $c_{>k}=A\cup B$
where $A,B$ are disjoint and any $b_{i}\in\aleph_{i}$ for $i\leq k$, $$b_{\leq
k}\cup A\not\vdash B.$$ \end{minipage}\right.$

(+)n holds by 3.4.

(+)-1 means that $\\{c_{i}\mid i<n+1\\}$ is shattered, from which we conclude.

Suppose (+)k holds, we choose $c_{k}\in\aleph_{k}$ such that (+)k-1 holds.

Such a $c_{k}$ exists because for each of the $\aleph_{k-1}$ choices for
$b_{<k}$ and $A$, there are only finitely many choices to rule out. More
explicitly, for every choice of $b_{<k}$ as above, and any $A\subseteq c_{>k}$
such that $b_{<k}\cup A\not\vdash c_{>k}\setminus A$, let
$s_{b_{<k},A}=\\{c\in\aleph_{k}\mid b_{<k}\cup A\vdash c_{>k}\setminus
A\cup\\{c\\}\\}$. By 3.5, $s_{b_{<k},A}$ is finite for each such $b_{<k},A$,
and let $c_{k}\in\aleph_{k}\setminus(\bigcup\\{s_{b_{<k},A}\mid b_{<k}\cup
A\not\vdash c_{>k}\setminus A\\}\cup c_{>k})$.

(+)k-1 holds: if $c_{k}\in A$ then we are done by induction, and otherwise
$c_{k}\in B$ and this follows from 3.6 and the choice of $c_{k}$. ∎

######  Remark 3.7.

With the same proof _mutatis mutandis_ one can see that if $\mathcal{F}$ is an
$\omega$-cofinal family of subsets of $X$, each of size $<\aleph_{\alpha}$,
and if $|X|\geq\aleph_{\alpha+n}$, then $\mathcal{F}$ has VC-dimension $>n$.

######  Theorem 3.8.

There is a cofinal family $\mathcal{F}$ of finite subsets of $\aleph_{1}$ of
VC-dimension 2.

###### Proof.

Let $\delta\leq\omega_{1}$. Suppose that
$\mathcal{C}=(\mathord{<^{\alpha}})_{\alpha<\delta}$ is a sequence of linear
orders, where $<^{\alpha}$ is a linear order on $\alpha$. We define the
following relation on triples $\alpha,\beta,\gamma<\delta$:
$\alpha,\beta\vdash_{\mathcal{C}}\gamma$ iff $\beta,\gamma<\alpha$ and
$\gamma<^{\alpha}\beta$. Say $B\subseteq\delta$ is
$\vdash_{\mathcal{C}}$-closed if for any $\alpha,\beta\in B$, if
$\alpha,\beta\vdash_{\mathcal{C}}\gamma$ then $\gamma\in B$.

We inductively define well-orders $<^{\alpha}$ on $\alpha<\omega_{1}$ such
that
$(*)_{\alpha}$ any finite subset $A\subseteq\alpha$ extends to a finite subset
$A\subseteq B\subseteq\alpha$ such that $B\cup\\{\alpha\\}$ is
$\vdash_{\mathcal{C}_{\alpha}}$-closed for
$\mathcal{C}_{\alpha}:=(<^{\beta})_{\beta\leq\alpha}$.

$(*)_{0}$ holds with $<^{0}$ the empty order.

Suppose $(*)_{\alpha}$ holds. Let $<^{\alpha+1}$ be the order obtained from
$<^{\alpha}$ by putting $\alpha$ at the start:
$\mathord{<^{\alpha+1}}=\mathord{<^{\alpha}}\cup{\\{(\alpha,\beta)\mid\beta<\alpha\\}}$.
Let $A\subseteq\alpha+1$. By $(*)_{\alpha}$, let $B\subseteq\alpha$ be a
finite set containing $A\setminus\\{\alpha\\}\subseteq\alpha$ such that
$B^{\prime}:=B\cup\\{\alpha\\}$ is $\vdash_{\mathcal{C}_{\alpha}}$-closed.
Then it follows from the definition of $<^{\alpha+1}$ that also
$B^{\prime}\cup\\{\alpha+1\\}$ is $\vdash_{\mathcal{C}_{\alpha+1}}$-closed.
Since $B^{\prime}$ is finite and contains $A$, we conclude that
$(*)_{\alpha+1}$ holds.

Suppose that $\eta<\omega_{1}$ is a limit ordinal and $(*)_{\alpha}$ holds for
all $\alpha<\eta$. Note that for $\alpha<\beta<\eta$ and any
$B\subseteq\alpha$, $B$ is $\vdash_{\mathcal{C}_{\alpha}}$-closed iff $B$ is
$\vdash_{\mathcal{C}_{\beta}}$-closed.

Since $\eta$ is countable, it follows that $\eta=\bigcup_{n\in\omega}S_{n}$
where for each $n<\omega$, $S_{n}$ is finite, $S_{n}\subseteq S_{n+1}$ and
$S_{n}$ is $\vdash_{\mathcal{C}_{\alpha}}$-closed for any (some) $\alpha<\eta$
such that $S_{n}\subseteq\alpha$. (In the construction, given $S_{n}$, let
$S_{n}^{\prime}=S_{n}\cup\\{\beta_{n}\\}$ where $(\beta_{n})_{n<\omega}$
enumerates $\eta$ and let $S_{n+1}$ be finite and
$\vdash_{\mathcal{C}_{\alpha}}$-closed containing $S_{n}^{\prime}$ for
$\alpha<\eta$ such that $S_{n}^{\prime}\subseteq\alpha$.) We define $<^{\eta}$
to be of order type $\omega$ in such a way that each $S_{n}$ is an initial
segment. Then $(*)_{\eta}$ holds: if $A$ is a finite subset of $\eta$, then
$A$ is contained in some $S_{n}$ which is finite and
$\vdash_{\mathcal{C}_{\alpha}}$-closed for any $\alpha$ large enough, and
since $S_{n}$ is an initial segment of $<^{\eta}$, $S_{n}\cup\\{\eta\\}$ is
$\vdash_{\mathcal{C}_{\eta}}$-closed.

Finally, let $\mathcal{C}=(\mathord{<^{\alpha}})_{\alpha<\omega_{1}}$ and
$\mathord{\vdash}=\mathord{\vdash}_{\mathcal{C}}$. Let $\mathcal{F}$ be the
family of finite subsets of $\omega_{1}$ which are $\vdash$-closed. By the
above construction, $\mathcal{F}$ is cofinal. As for any triple
$\alpha_{0},\alpha_{1},\alpha_{2}<\omega_{1}$ of distinct ordinals there is
some permutation $\sigma$ of 3 such that
$\alpha_{\sigma(0)},\alpha_{\sigma(1)}\vdash\alpha_{\sigma(2)}$, $\mathcal{F}$
does not shatter any set of size 3. ∎

######  Corollary 3.9.

The following statement is independent of ZFC: there is an NIP cofinal family
of finite subsets of $2^{\aleph_{0}}$.

###### Proof.

On the one hand CH is consistent with ZFC (by Gödel’s theorem, see e.g., [5,
Theorem 13.20]), and on the other hand it is consistent with ZFC that
$\aleph_{\omega}<2^{\aleph_{0}}$ (using Cohen forcing, see e.g., [5, Chapter
15, “Cohen Reals”]). Thus, the statement follows from Propositions 3.3 and
3.8. ∎

######  Question 3.10.

Is there a cofinal family of finite subsets of $\aleph_{2}$ of VC-dimension 3?
More generally: is the bound in Proposition 3.3 tight, or can we improve
$\aleph_{\omega}$ to a smaller cardinal?

##  4\. NIP and cofinal families of finite subsets of an uncountable set

This section is devoted to proving the following theorem.

######  Theorem 4.1.

Suppose that $\kappa$ is an infinite cardinal, $|X|\geq\kappa^{+}$, and
$\mathcal{F}$ is an $\omega$-cofinal family of subsets of $X$, each of size
$<\kappa$. Then $(X,\mathcal{F};\mathord{\in})$ has IP (as a two-sorted
structure whose only relation is $\mathord{\in}\subseteq X\times\mathcal{F}$).

The proof relies upon the following lemma.

######  Lemma 4.2.

Let $\kappa$ be any infinite cardinal. Assume that:

  1. (1)

$|X|\geq\kappa^{+}$.

  2. (2)

$R\subseteq X^{n}$ and $1\leq n$.

  3. (3)

For every $a_{1},\dots,a_{n-1}\in X$, $|\\{a_{0}\in X\mid
R(a_{0},a_{1},\dots,a_{n-1})\\}|<\kappa$.

  4. (4)

For every set $A\subseteq X$ of size $|A|=n$, for some $a\in A$ and some tuple
$\bar{a}\in(A\setminus{a})^{n-1}$, $R(a,\bar{a})$ holds.

Then, there is some partition of $\\{1,\dots,n-1\\}$ into nonempty disjoint
sets $u,v$ such that, letting $x:=(x_{i})_{i\in u\cup\\{0\\}}$ and
$y:=(x_{i})_{i\in v}$, the partitioned formula
$\phi(x,y):=R(x_{0},x_{1},\dots,x_{n-1})$ has IP.

######  Remark 4.3.

Lemma 4.2 does not hold if we replace $\kappa^{+}$ by $\kappa$ in (1). Indeed,
let $X=\omega$ and let $R(x,y)=(x<y)$. Then (2)–(4) hold for
$\kappa=\aleph_{0}$ and $n=2$ but $R$ is NIP (by e.g., [7, Proposition A.2]).

######  Remark 4.4.

Note that conditions (1)–(4) imply that $n>2$. If $n=1$ then by (3), $R$
defines a set of size $<\kappa$, but by (4), $R$ contains $X$, contradicting
(1). Suppose that $n=2$ and for $a\in X$ let $s_{a}=\\{b\in X\mid R(b,a)\\}$.
Let $X_{0},X_{1}\subseteq X$ be such that $X_{0}\cap X_{1}=\emptyset$,
$|X_{0}|=\kappa$ and $|X_{1}|=\kappa^{+}$. Let $S=\bigcup\\{s_{a}\mid a\in
X_{0}\\}$. As $|S|\leq\kappa$, there must be some $b\in X_{1}\setminus S$. As
$|s_{b}|<\kappa$, there must be some $a\in X_{0}\setminus s_{b}$. Then
$a\notin s_{b}$ and $b\notin s_{a}$, contradicting (4).

The following example shows that the conditions of Lemma 4.2 can hold when
$n=3$.

######  Example 4.5.

Suppose that for each $\alpha<\omega_{1}$, $<^{\alpha}$ is a well order on
$\alpha$ of order type $\omega$. For $\alpha,\beta,\gamma<\omega_{1}$, let
$R(\gamma,\beta,\alpha)$ hold iff $\gamma,\beta<\alpha$ and
$\gamma<^{\alpha}\beta$. Then $R$ satisfies the conditions of Lemma 4.2 with
$\kappa=\aleph_{0}$.

######  Remark 4.6.

In essence, the proof of Lemma 4.2 is an induction on $n$, with Remark 4.4 as
the base case. However, we need to keep track of sets witnessing IP
($D^{k,j,\bar{c}}_{\bar{A}}$ in the proof below), which substantially
complicates the proof.

###### Proof of Lemma 4.2.

Assume not, i.e., that

  1. (5)

for any partition of $\\{1,\dots,n-1\\}$ into nonempty disjoint sets $u,v$,
letting $x:=(x_{i})_{i\in u\cup\\{0\\}}$ and $y:=(x_{i})_{i\in v}$ the
partitioned formula $\phi(x,y):=R(x_{0},x_{1},\dots,x_{n-1})$ is NIP.

Define $R^{\prime}\subseteq X^{n}$ by $R^{\prime}(a_{0},\dots,a_{n-1})$ iff
for some tuple $\bar{a}\in\\{a_{1},\dots,a_{n-1}\\}^{n-1}$, $R(a_{0},\bar{a})$
holds. Note that $R^{\prime}$ satisfies (2)–(5) above (it satisfies (5) as a
finite disjunction of NIP relations; in fact (5) can now be simplified by
saying that $R^{\prime}(x_{0},\dots,x_{k-1};x_{k},\dots,x_{n-1})$ is NIP for
any $1<k<n$). Thus, we can replace $R$ with $R^{\prime}$ and assume in
addition that

  1. (6)

For any tuple $\bar{a}\in X^{n-1}$ and for any permutation $\bar{a}^{\prime}$
of $\bar{a}$, $R(X,\bar{a})=R(X,\bar{a}^{\prime})$.

For any nonempty set $t\subseteq X$ of size $\leq n-1$, let
$s_{t}=R(X,\bar{a})$ where $\bar{a}$ is any enumeration of $t$ of length
$n-1$; this is well-defined by (6). We can then restate (4) as:

For every $t$ of size $n$, for some $a\in t$, $a\in s_{t\setminus\\{a\\}}$.

We may assume that $|X|=\kappa^{+}$, and even that $X=\kappa^{+}$. When we say
that a subset of $X$ is “cofinal” or “contains an end segment of some cofinal
set”, we mean with respect to the canonical order on $\kappa^{+}$. For a
cofinal set $D\subseteq X$ and some property $P\subseteq X$, write
$\forall^{*}x\in D\ P(x)$ to mean that $P$ contains an end segment of $D$. By
downwards induction on $k\in[2,n]$ (note that by Remark 4.4, $n>2$, so this
range for $k$ makes sense), we will find:

  1. (A)

$m_{k}<\omega$, and

  2. (B)

a cofinal set $D^{k,j,\bar{c}}_{\bar{A}}\subseteq X$ for every $j\in[k,n)$ and
$\bar{c}\in X^{j-k}$ and ${\bar{A}}\in\prod_{i\in[k,j]}{\SS(m_{i})}$,

such that $\boxplus_{k}$ and $\boxtimes_{k}$ below hold. To state these
conditions, we first introduce some additional notation:

  * •

For $l,j$ with $k\leq l\leq j\leq n$, let
$M_{l}^{j}:=\prod_{i\in[l,j]}{\SS(m_{i})}$. We denote elements of $M_{l}^{j}$
by $(j+1-l)$-tuples ${\bar{A}}$. For $j<l$, set $M_{l}^{j}:=\\{\emptyset\\}$.

  * •

For $j\in[k,n]$, $t\subseteq X$ of size $k-1$, $\bar{c}\in X^{j-k}$, and
${\bar{A}}\in M_{k}^{j-1}$, define sets $s^{k,j,\bar{c},{\bar{A}}}_{t}$ as
follows. We set $s^{k,n,\bar{c},{\bar{A}}}_{t}=s_{t\cup\bar{c}}$, and then
define recursively for $j\in[k,n)$:

$s^{k,j,\bar{c},{\bar{A}}}_{t}=\\{a\in X\mid\exists A\subseteq m_{j}\
\forall^{*}c\in D^{k,j,\bar{c}}_{{\bar{A}}A}\ a\in
s^{k,j+1,\bar{c}c,{\bar{A}}A}_{t}\\}.$

  * •

For $t\subseteq X$ of size $k-1$, let
$s^{k}_{t}=s^{k,k,\emptyset,\emptyset}_{t}$.

Now we can state the conditions to be satisfied by our inductive construction:

  * $\boxplus_{k}$

For every $j\in(k,n)$ and every $c\bar{c}\in X^{j-k}$ and $A{\bar{A}}\in
M_{k}^{j}$, $D^{k,j,c\bar{c}}_{A{\bar{A}}}\subseteq
D^{k+1,j,\bar{c}}_{{\bar{A}}}$ (for $k\geq n-1$, this condition holds
trivially).

  * $\boxtimes_{k}$

For all $t\subseteq X$ of size $|t|=k$, for some $a\in t$, $a\in
s^{k}_{t\setminus\\{a\\}}$.

Note that each $|s^{k,j,\bar{c},{\bar{A}}}_{t}|<\kappa$ by downwards induction
on $j$: for $j=n$ this is clear, and suppose that
$|s^{k,j+1,\bar{c}c,{\bar{A}}A}_{t}|<\kappa$ for all $c\in X$ and $A\subseteq
m_{j}$. Towards a contradiction, assume that $s^{k,j,\bar{c},{\bar{A}}}_{t}$
contains a set $F$ of size $\kappa$. We may assume that for some $A\subseteq
m_{j}$ and all $a\in F$, $\forall^{*}c\in D^{k,j,\bar{c}}_{{\bar{A}}A}\ a\in
s^{k,j+1,\bar{c}c,{\bar{A}}A}_{t}$. For any $a\in F$ there is an end segment
$F_{a}$ of $D^{k,j,\bar{c}}_{{\bar{A}}A}$ such that for any $c\in F_{a}$,
$a\in s^{k,j+1,\bar{c}c,{\bar{A}}A}_{t}$. Since $D^{k,j,\bar{c}}_{{\bar{A}}A}$
is cofinal in $\kappa^{+}$ (which is a regular cardinal), $\bigcap_{a\in
F}F_{a}$ contains an end segment of $D^{k,j,\bar{c}}_{{\bar{A}}A}$, and in
particular is nonempty. Let $c\in\bigcap_{a\in F}F_{a}$. Then $F\subseteq
s^{k,j+1,\bar{c}c,{\bar{A}}A}_{t}$, contradicting the induction hypothesis.

Note also that for $t\subseteq X$ of size $n-1$, $s_{t}=s^{n}_{t}$.

We now proceed with the inductive construction of the $m_{k}$ and
$D^{k,j,\bar{c}}_{\bar{A}}$.

For $k=n$, let $m_{n}=0$. Then $\boxplus_{n}$ holds trivially and
$\boxtimes_{n}$ holds by $\boxtimes$ above.

Assume that $2\leq k<n$ and we found $m_{k^{\prime}}$ and cofinal sets
$D^{k^{\prime},j,\bar{c}}_{\bar{A}}$ such that $\boxplus_{k^{\prime}}$ and
$\boxtimes_{k^{\prime}}$ hold for all $k^{\prime}>k$. We want to find $m_{k}$
and sets $D^{k,j,\bar{c}}_{\bar{A}}$ such that $\boxplus_{k}$ and
$\boxtimes_{k}$ hold.

For $m<\omega$ we let $\otimes_{m}$ be the following statement: there are

  * •

cofinal sets $D^{k,j,\bar{c}}_{\bar{A}}$ for $j\in[k,n)$ and $\bar{c}\in
X^{j-k}$ and ${\bar{A}}\in(\SS(m)\times M_{k+1}^{j})$, and

  * •

subsets $t_{i}\subseteq X$ of size $k$ for $i<m$,

such that:

  1. (I)

$\boxplus_{k}$ holds with $m$ playing the role of $m_{k}$;

  2. (II)

if $B\neq A$ are subsets of $m$, and $i:=\min(B\mathrel{\triangle}A)\in B$,
then for some enumeration $\bar{a}$ of $t_{i}$, the following hold:

     * $\oplus$

for all $c_{k}\in D^{k,k,\emptyset}_{(B)}$, for some $A_{k+1}\subseteq
m_{k+1}$ and all $c_{k+1}\in D^{k,k+1,(c_{k})}_{(B,A_{k+1})}$, …, for some
$A_{n-1}\subseteq m_{n-1}$ and all $c_{n-1}$ in
$D^{k,n-1,(c_{k},\dots,c_{n-2})}_{(B,\dots,A_{n-1})}$,

$R(\bar{a},c_{k},\dots,c_{n-1});$

     * $\ominus$

for all $c_{k}\in D^{k,k,\emptyset}_{(A)}$, for all $A_{k+1}\subseteq m_{k+1}$
and all $c_{k+1}\in D_{(A,A_{k+1})}^{k,k+1,(c_{k})}$, …, for all
$A_{n-1}\subseteq m_{n-1}$ and all $c_{n-1}$ in
$D_{(A,\dots,A_{n-1})}^{k,n-1,(c_{k},\dots,c_{n-2})}$,

$\neg R(\bar{a},c_{k},\dots,c_{n-1}).$

If $\otimes_{m}$ holds for all $m<\omega$, we get IP as we now explain.
Consider the formula

$\phi(\bar{x},\bar{y})=\bigvee_{{\bar{A}}\in
M_{k+1}^{n-1}}R(x_{0},\dots,x_{k-1};y_{k},y_{k+1}^{\bar{A}},y_{k+2}^{\bar{A}},\dots,y_{n-1}^{\bar{A}}).$

Fix some $m<\omega$. For $A\subseteq m$, we define a $\bar{y}$-tuple
$\bar{c}^{A}$ as follows. Let $c^{A}_{k}\in D^{k,k,\emptyset}_{(A)}$ and for
$j\in[k+1,n)$ and $(A_{k+1},...,A_{n-1})\in M_{k+1}^{n-1}$, inductively let
$c^{A,{\bar{A}}}_{j}\in
D^{k,j,(c^{A}_{k},c^{A,{\bar{A}}}_{k+1},\dots,c^{A,{\bar{A}}}_{j-1})}_{(A,A_{k+1},...,A_{j})}$.
Then, by (II) we get that if $B\neq A$ and $i=\min(B\mathrel{\triangle}A)\in
B$, then for some tuple $\bar{a}$ enumerating $t_{i}$,
$\phi(\bar{a},\bar{c}^{B})$ holds, while $\phi(\bar{a},\bar{c}^{A})$ does not.
Let $E$ be the set of all $\bar{x}$-tuples $\bar{a}$ enumerating $t_{i}$ for
all $i<m$. We get that the number of $\phi$-types in $\bar{y}$ over $E$ is
exponential in $m$ (at least $2^{m}$). However, $|E|\leq mk!$. By Sauer-Shelah
([7, Lemma 6.4]), we get that $\phi(\bar{x},\bar{y})$ has IP. As NIP formulas
are closed under Boolean combinations, we get that
$R(x_{0},\dots,x_{k-1};y_{k},\dots,y_{n-1})$ has IP, contradicting (5).

We first show that $\otimes_{0}$ holds. Let
$D_{(\emptyset)}^{k,k,\emptyset}=X$ and for $j>k$, ${\bar{A}}\in M_{k+1}^{j}$,
$\bar{c}\in X^{j-(k+1)}$ and $c\in X$, let
$D_{\emptyset{\bar{A}}}^{k,j,c\bar{c}}=D_{\bar{A}}^{k+1,j,\bar{c}}$. Then (I)
is immediate, and (II) is trivially satisfied.

Let $m_{k}$ be maximal such that $\otimes_{m_{k}}$ holds, witnessed by
$D^{k,j,\bar{c}}_{\bar{A}}$ and $t_{i}$. We claim that this $m_{k}$ and
$D^{k,j,\bar{c}}_{\bar{A}}$ satisfy $\boxplus_{k}$ and $\boxtimes_{k}$.
$\boxplus_{k}$ is satisfied by (I), so we are left to check $\boxtimes_{k}$.

Assume that $\boxtimes_{k}$ does not hold. Then there is some $t\subseteq X$
of size $k$ witnessing this: for all $a\in t$, $a\notin
s^{k}_{t\setminus\\{a\\}}$. We will show that letting $t_{m_{k}}:=t$, we can
find new $D^{k,j,\bar{c}}_{\bar{A}}$ for ${\bar{A}}\in\SS(m_{k}+1)\times
M_{k+1}^{j}$ and $\bar{c}\in X^{j-k}$ witnessing $\otimes_{m_{k}+1}$. We will
construct two sequences of cofinal sets, $E_{\bar{A}}^{k,j,\bar{c}}$ and
${F_{\bar{A}}^{k,j,\bar{c}}}$, that will then be used to find suitable $D$’s.

Let $A_{k}\subseteq m_{k}$. Let
$E_{(A_{k})}^{k,k,\emptyset}=D_{(A_{k})}^{k,k,\emptyset}\setminus(s^{k+1}_{t}\cup
t)$. Since $s^{k+1}_{t}$ has size $<\kappa$, $E_{(A_{k})}^{k,k,\emptyset}$ is
still cofinal. Let $c_{k}\in E_{(A_{k})}^{k,k,\emptyset}$. By
$\boxtimes_{k+1}$ applied to $t\cup\\{c_{k}\\}$, and as $c_{k}\notin
s^{k+1}_{t}$, for some $a_{c_{k},A_{k}}\in t$, we have $a_{c_{k},A_{k}}\in
s^{k+1}_{\\{c_{k}\\}\cup t\setminus\\{a_{c_{k},A_{k}}\\}}$. As $t$ is finite,
by reducing $E_{(A_{k})}^{k,k,\emptyset}$, we may assume that there is some
$a_{A_{k}}\in t$ such that $a_{A_{k}}\in s^{k+1}_{\\{c_{k}\\}\cup
t\setminus\\{a_{A_{k}}\\}}$ for any $c_{k}\in E_{(A_{k})}^{k,k,\emptyset}$.

Let $j\in(k,n)$, ${\bar{A}}\in M_{k}^{j}$, and $\bar{c}\in X^{j-k}$. Write
$\bar{c}=c_{k}\bar{c}^{\prime}$ and ${\bar{A}}=A_{k}{\bar{A}}^{\prime}$, so
${\bar{A}}^{\prime}\in M_{k+1}^{j}$. We define cofinal sets
$E_{{\bar{A}}}^{k,j,\bar{c}}$ as follows

  * •

If $\forall^{*}c\in D_{{\bar{A}}^{\prime}}^{k+1,j,\bar{c}^{\prime}}\
a_{A_{k}}\in s_{\\{c_{k}\\}\cup
t\setminus\\{a_{A_{k}}\\}}^{k+1,j+1,\bar{c}^{\prime}c,{\bar{A}}^{\prime}}$
then let $S\subseteq D_{{\bar{A}}^{\prime}}^{k+1,j,\bar{c}^{\prime}}$ be an
end segment witnessing this, and set $E_{{\bar{A}}}^{k,j,\bar{c}}=S\cap
D_{{\bar{A}}}^{k,j,\bar{c}}$. Note that $E_{{\bar{A}}}^{k,j,\bar{c}}$ is
cofinal as $D_{{\bar{A}}}^{k,j,\bar{c}}\subseteq
D_{{\bar{A}}^{\prime}}^{k+1,j,\bar{c}^{\prime}}$ by $\boxplus_{k}$.

  * •

Otherwise, let $E_{{\bar{A}}}^{k,j,\bar{c}}=D_{{\bar{A}}}^{k,j,\bar{c}}$.

By (upwards) induction on $j\in[k,n)$ one proves that:

  * ($\dagger_{j}$)

For any $A_{k}\subseteq m_{k}$ and any $c_{k}\in E_{(A_{k})}^{k,k,\emptyset}$
there is some $A_{k+1}\subseteq m_{k+1}$ such that for any $c_{k+1}\in
E_{(A_{k},A_{k+1})}^{k,k+1,(c_{k})}$ there is some $A_{k+2}\subseteq m_{k+2}$
such that …for any $c_{j}\in
E_{(A_{k},\dots,A_{j})}^{k,j,(c_{k},\dots,c_{j-1})}$, $a_{A_{k}}\in
s_{\\{c_{k}\\}\cup
t\setminus\\{a_{A_{k}}\\}}^{k+1,j+1,(c_{k+1},\dots,c_{j}),(A_{k+1},\dots,A_{j})}$.

Now for $A_{k}\subseteq m_{k}$, let $F_{(A_{k})}^{k,k,\emptyset}\subseteq
D_{(A_{k})}^{k,k,\emptyset}$ be a cofinal set such that $a_{A_{k}}\notin
s^{k,k+1,(c),(A_{k})}_{t\setminus\\{a_{A_{k}}\\}}$ for any $c\in
F_{(A_{k})}^{k,k,\emptyset}$; such a set exists since $a_{A_{k}}\notin
s^{k}_{t\setminus\\{a_{A_{k}}\\}}=s^{k,k,\emptyset,\emptyset}_{t\setminus\\{a_{A_{k}}\\}}$.

Then for any $j\in(k,n)$, any $\bar{c}\in X^{j-k}$ and any
${\bar{A}}=(A_{k},...,A_{j})\in M_{k}^{j}$, we similarly define cofinal sets
$F_{{\bar{A}}}^{k,j,\bar{c}}$ as follows.

  * •

If $a_{A_{k}}\in
s^{k,j,\bar{c},(A_{k},...,A_{j-1})}_{t\setminus\\{a_{A_{k}}\\}}$, let
$F_{\bar{A}}^{k,j,\bar{c}}=D_{\bar{A}}^{k,j,\bar{c}}$, and

  * •

if $a_{A_{k}}\notin
s^{k,j,\bar{c},(A_{k},...,A_{j-1})}_{t\setminus\\{a_{A_{k}}\\}}$, let
$F_{\bar{A}}^{k,j,\bar{c}}\subseteq D_{\bar{A}}^{k,j,\bar{c}}$ be cofinal such
that $a_{A_{k}}\notin
s^{k,j+1,\bar{c}c,{\bar{A}}}_{t\setminus\\{a_{A_{k}}\\}}$ for any $c\in
F_{\bar{A}}^{k,j,\bar{c}}$.

Recall that by choice of $t$, $a\notin s^{k}_{t\setminus\\{a\\}}$ for all
$a\in t$. By (upwards) induction on $j\in[k,n]$ one proves that:

  * ($\$_{j}$)

If $(A_{k},...,A_{j-1})\in M_{k}^{j-1}$ and $(c_{k},\dots,c_{j-1})\in X^{j-k}$
are such that $c_{i}\in F_{(A_{k},\dots,A_{i})}^{k,i,(c_{k},\dots,c_{i-1})}$
for every $i\in[k,j)$, then for every $i\in[k,j]$,

$a_{A_{k}}\notin
s^{k,i,(c_{k},\dots,c_{i-1}),(A_{k},\dots,A_{i-1})}_{t\setminus\\{a_{A_{k}}\\}}.$

Now, for any $A{\bar{A}}\in\SS(m_{k}+1)\times M_{k+1}^{j}$, let
$G_{A{\bar{A}}}^{k,j,\bar{c}}:=F_{A{\bar{A}}}^{k,j,\bar{c}}$ if $m_{k}\notin
A$, else let $G_{A{\bar{A}}}^{k,j,\bar{c}}:=E_{(A\cap
m_{k}){\bar{A}}}^{k,j,\bar{c}}$. Now we show that $(t_{i})_{i\leq m_{k}}$ and
these $G_{A{\bar{A}}}^{k,j,\bar{c}}$ witness $\otimes_{m_{k}+1}$. Note that
$G_{A{\bar{A}}}^{k,j,\bar{c}}$ is a cofinal subset of $D_{(A\cap
m_{k}){\bar{A}}}^{k,j,\bar{c}}$. Hence $\boxplus_{k}$ still holds,
establishing (I). For (II), let $B\neq A$ be subsets of $m_{k}+1$. If
$i=\min(B\mathrel{\triangle}A)\in B$ and $i<m_{k}$, then $i=\min({(B\cap
m_{k})\mathrel{\triangle}(A\cap m_{k})})$ and so $\oplus$ and $\ominus$ still
hold (using $G_{A{\bar{A}}}^{k,j,\bar{c}}\subseteq D_{(A\cap
m_{k}){\bar{A}}}^{k,j,\bar{c}}$). If not, then $B=A\cup\\{m_{k}\\}$. Let
$\bar{a}$ be an enumeration of $t_{m_{k}}$ starting with $a_{A}$. Then
$\oplus$ follows from $(\dagger_{n-1})$ and $\ominus$ follows from $(\$_{n})$,
as required.

This completes the construction of $m_{k}$ and $D_{\bar{A}}^{k,j,\bar{c}}$ as
in (A), (B) above for all $k\in[2,n]$.

Finally, $\boxtimes_{2}$ yields a contradiction by the argument of Remark 4.4.
Indeed, by $\boxtimes_{2}$ we get that for any distinct $a,b\in X$, either
$a\in s^{2}_{\\{b\\}}$ or $b\in s^{2}_{\\{a\\}}$. Let $X_{0},X_{1}\subseteq X$
be such that $X_{0}\cap X_{1}=\emptyset$, $|X_{0}|=\kappa$ and
$|X_{1}|=\kappa^{+}$. Let $S=\bigcup\\{s^{2}_{\\{a\\}}\mid a\in X_{0}\\}$. As
$|S|\leq\kappa$, there must be some $b\in X_{1}\setminus S$. As
$|s^{2}_{\\{b\\}}|<\kappa$, there must be some $a\in X_{0}\setminus
s^{2}_{\\{b\\}}$. But then $a\notin s^{2}_{\\{b\\}}$ and $b\notin
s^{2}_{\\{a\\}}$ — contradiction. ∎

###### Proof of Theorem 4.1.

Suppose that $|X|\geq\kappa^{+}$ and that $\mathcal{F}$ is a cofinal family of
subsets of $X$, each of size $<\kappa$. Suppose that
$\operatorname{VC}(\mathcal{F})=n$.

For any $0\leq k\leq n$ and any $m\leq k$, let $R_{m,k}(x_{0},\dots,x_{k})$ be
the relation defined by:

$[\exists t\in\mathcal{F}\;\bigwedge_{1\leq i\leq k}(x_{i}\in t)^{(i\leq
m)}]\land[\forall t\in\mathcal{F}\;((\bigwedge_{1\leq i\leq k}(x_{i}\in
t)^{(i\leq m)})\to x_{0}\in t)].$

(If $k=0$ the conjunction is empty and thus holds trivially, meaning that
$R_{0,0}(x_{0})=\forall t\in\mathcal{F}\;x_{0}\in t$.)

Let $R(x_{0},x_{1},\dots,x_{n})=\bigvee_{m\leq k\leq
n}R_{m,k}(x_{0},\dots,x_{k})$. We claim that $R$ satisfies the conditions of
Lemma 4.2 on $X$. Conditions (1) and (2) are trivial, condition (3) follows
from the fact that it is true for each $m,k$ separately and that each
$t\in\mathcal{F}$ has size $<\kappa$ (using the existential clause of the
definition of $R_{m,k}$).

We show condition (4). Suppose that $A\subseteq X$ has size $n+1$. Since
$\operatorname{VC}(\mathcal{F})=n$, $\mathcal{F}$ does not shatter $A$. Let
$B\subseteq A$ be of minimal size such that $\mathcal{F}$ does not shatter
$B$. Note that $B$ is nonempty and let $k=|B|-1$. Since $B$ is not shattered,
there is some $B_{0}\subseteq B$ such that for no $t\in\mathcal{F}$, $t\cap
B=B_{0}$. Note that $B_{0}\neq B$ since $\mathcal{F}$ is $\omega$-cofinal (and
$B$ is finite). Let $m=|B_{0}|$. Let $a_{0}\in B\setminus B_{0}$ and let
$a_{1},\dots,a_{k}$ enumerate $B\setminus\\{a_{0}\\}$ such that $a_{i}\in
B_{0}$ iff $i\leq m$. It follows that $R_{m,k}(a_{0},a_{1},\dots,a_{k})$
holds: the first clause holds by the minimality of $B$ (any proper subset is
shattered), and the second clause follows by the choice of $B_{0}$.

By Lemma 4.2, for some permutation $\sigma$ of $\\{1,\dots,n\\}$ and some
$1<k<n$ the partitioned formula
$R(x_{0},x_{\sigma(1)},\dots,x_{\sigma(k-1)};x_{\sigma(k)},\dots,x_{\sigma(n-1)})$
has IP and we are done. ∎

######  Question 4.7.

Let $R(x,y,z)$ be the relation from Example 4.5. The proof of Lemma 4.2 yields
that $R(x,y;z)$ has IP. Could the relation $R(x;y,z)$ be NIP? Note that
$\\{R(\omega_{1};\beta,\alpha)\mid\beta,\alpha\\}$ is a cofinal family of
finite subsets of $\omega_{1}$ (see Theorem 3.8).

Similarly, we do not know whether the formula $\phi(x,z;y)=R(x,y,z)$ has IP.

##  5\. Conclusion and final thoughts

We conclude with the final theorem, i.e., the generalisation of 1.1 discussed
in Section 1.1.

######  Theorem 5.1.

Let $\kappa$ be an infinite cardinal. If $T=\operatorname{Th}(M)$ is NIP and
$X\subseteq M^{k}$ is externally definable of size $\geq\kappa^{+}$, then $X$
contains an $M$-definable subset of size $\geq\kappa$. In other words,
$\text{ext}(T,\kappa)\leq\kappa^{+}$.

###### Proof.

Suppose that $X$ is defined by $\phi(x,c)$ for some formula $\phi(x,y)$. Let
$\psi(x,z)$ be an honest definition for
$\operatorname{tp}_{\phi^{\operatorname{opp}}}(c/M)$. This means that for
every finite set $X_{0}\subseteq X$, there is some $d\in M^{z}$ such that

$X_{0}=\phi(X_{0},c)\subseteq\psi(M,d)\subseteq\phi(M,c)=X.$

Let $Y=\\{d\in M^{z}\mid\psi(M,d)\subseteq X\\}$. Note that $Y$ is definable
in $M^{Sh}$. If for some $d\in Y$, $\psi(M,d)$ has size $\geq\kappa$, we are
done, so assume for all $d\in Y$, $|\psi(M,d)|<\kappa$. Let
$\mathcal{F}=\\{\psi(M,d)\mid d\in Y\\}$. Then $N:=(X,\mathcal{F};\in)$ is
interpretable in $M^{Sh}$. By Fact 2.6 it follows that $N$ is NIP,
contradicting Theorem 4.1 as required. ∎

######  Remark 5.2.

Note that the above proof implies that in an NIP theory, if $X=\phi(M,c)$ is
externally definable of size $\kappa^{+}$, then an instance of the honest
definition of $\operatorname{tp}_{\phi^{\operatorname{opp}}}(c/M)$ has size
$\geq\kappa$. By Fact 2.4, we know that the existence of an honest definition
$\psi(x,z)$ only requires $\phi$ to be NIP. We do not know if $\psi$ itself
can be chosen to be NIP (this is open even for the finite case, see [4,
Question 22]). However, even if it were NIP, we cannot get a contradiction as
in the proof above due to Theorem 3.8.

######  Question 5.3.

Suppose that $M$ is a structure and $X=\phi(M,c)$ is externally definable of
size $\geq\aleph_{1}$. Suppose that $\phi$ is NIP. Does it follow that $X$
contains an infinite definable subset?

Note that when $T$ eliminates the quantifier $\exists^{\infty}$, the answer is
“yes” (even just assuming that $X$ is infinite), as in [2, Corollary 1.12(1)]:
by Fact 2.4 (or [7, Theorem 3.13]),
$\operatorname{tp}_{{\phi^{\operatorname{opp}}}}(c/M)$ has an honest
definition $\psi$, and so as above some instance $\psi(M,d)\subseteq X$
contains a finite subset $X_{0}$ large enough that, by elimination of
$\exists^{\infty}$, the instance must be infinite.

Refining 5.3, we can define $\text{ext}(T,\phi,\kappa)$ as the minimal
$\lambda$ (if exists) such that whenever $M\vDash T$ and $X\subseteq M^{k}$ is
externally definable by $\phi(x,c)$ for some $c\in\mathcal{U}$, then $X$
contains an $M$-definable subset of size $\geq\kappa$. By Theorem 5.1, if $T$
is NIP then $\text{ext}(T,\phi,\kappa)\leq\kappa^{+}$. If the honest
definition of $\phi$ is NIP then by Remark 3.7, if $\kappa=\aleph_{\alpha}$,
$\text{ext}(T,\phi,\kappa)\leq\aleph_{\alpha+\omega}$. If we assume only that
$\phi$ is NIP, it is not even clear that $\text{ext}(T,\phi,\aleph_{0})$
exists.

######  Question 5.4.

What is $\text{ext}(T,\phi,\kappa)$ when $\phi$ is NIP?

######  Remark 5.5.

Let $T$ be a complete theory. Suppose that there is some infinite
$\emptyset$-definable set $Z$ of $x$-tuples such that $\phi(x,y)$ is random on
$Z$: for any finite disjoint sets $A,B\subseteq Z$ there is some $y$-tuple $d$
such that $A=\phi(A\cup B,d)$ (for the notations, see Section 2.1). This is a
strong negation of NIP and happens e.g., in the case of the random graph. Then
every subset of $Z$ is externally definable by compactness. Let
$T^{\operatorname{Sk}}$ be a Skolemization of $T$. Let $\lambda$ be any
infinite cardinal and let $I=(a_{i})_{i<\lambda}$ be an indiscernible sequence
(in the sense of $T^{\operatorname{Sk}}$) contained in $Z$ (in some model of
$T$), and let $N=\operatorname{Sk}(I)$ (the Skolem hull of $I$). Then
$X:=\\{a_{i}\mid i\text{ even}\\}$ is a subset of $N$ which is externally
definable by an instance of $\phi$, but which does not contain an infinite
$N$-definable subset (even in $\mathcal{L}^{\operatorname{Sk}}$). Hence
$\text{ext}(T,\phi,\aleph_{0})=\infty$, and in particular
$\text{ext}(T,\aleph_{0})=\infty$.

######  Question 5.6.

Does $\text{ext}(T,\aleph_{0})=\infty$ hold whenever $T$ is IP? That is, does
every IP theory have a model containing an uncountable externally definable
set which contains no infinite definable set?

##  Appendix A Almost agreeing orders on the countable ordinals

In this appendix, we show how to construct on each countable ordinal an order
of order type $\omega$, in such a way that any two of the orders agree up to a
finite set. This result is not used in the paper. It formed part of our first
attempt to prove Theorem 3.8, but in the end turned out not to provide a route
to proving that theorem. We nonetheless present the result in this appendix,
in the hope that it may be of interest in its own right.

######  Definition A.1.

Let $X$ be a set. Say two orders $<^{1}$ and $<^{2}$ on $X$ almost agree, and
write $\mathord{<^{1}}\sim\mathord{<^{2}}$, if there is a finite subset
$X_{0}\subseteq X$ such that $\mathord{<^{1}}|_{(X\setminus
X_{0})}=\mathord{<^{2}}|_{(X\setminus X_{0})}$.

Note that $\sim$ is an equivalence relation.

If $(X,<)$ has order type $\omega$, we call $<$ an $\omega$-order on $X$.

######  Theorem A.2.

There are $\omega$-orders $<^{\alpha}$ on each $\alpha$ for
$\omega\leq\alpha<\omega_{1}$ such that
$\mathord{<^{\beta}}\sim\mathord{<^{\alpha}}|_{\beta}$ whenever
$\omega\leq\beta<\alpha$.

Before proving Theorem A.2, we establish a pair of lemmas.

######  Lemma A.3.

Suppose that $(X,<^{X})$ and $(Y,<^{Y})$ are both $\omega$-orders, $X\subseteq
Y$, and $\mathord{<^{X}}\sim\mathord{<^{Y}}|_{X}$. Then there is some
$\omega$-order $\lessdot^{Y}$ on $Y$ such that
$\mathord{\lessdot^{Y}}\sim\mathord{<^{Y}}$ and
$\mathord{\lessdot^{Y}}|_{X}=\mathord{<^{X}}$.

###### Proof.

Let $X_{0}\subseteq X$ be finite such that $<^{X}$ and $\mathord{<^{Y}}|_{X}$
agree on $X\setminus X_{0}$. We define an order on $Y$ which agrees with
$<^{Y}$ on $Y\setminus X_{0}$ and places $X_{0}$ in a way which agrees with
$<^{X}$ on $X$. Formally, we prove the lemma by induction on $|X_{0}|$. If
$X_{0}$ is empty there is nothing to do. Let $x\in X_{0}$,
$Z=X\setminus\\{x\\}$, $W=Y\setminus\\{x\\}$,
$\mathord{<^{Z}}=\mathord{<^{X}}|_{Z}$ and
$\mathord{<^{W}}=\mathord{<^{Y}}|_{W}$. Note that $<^{Z}$ and $<^{W}$ are
still $\omega$-orders. By the induction hypothesis, there is some order
$\lessdot^{W}$ on $W$ such that $\mathord{\lessdot^{W}}\sim\mathord{<^{W}}$
and $\mathord{<^{Z}}\subseteq\mathord{\lessdot^{W}}$.

Let $F=\\{y\in W\mid\exists z\in X\;(z<^{X}x\land
y\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{W}z)\\}$;
this is the cut on $(W,\lessdot^{W})$ induced by the cut of $x$ on
$(Z,<^{Z})$. Note that $F$ is downwards closed in $\lessdot^{W}$ and that $F$
is finite: let $x^{\prime}\in X$ be such that $x<^{X}x^{\prime}$. Then if
$y\in F$ and $z$ witnesses this, then $z<^{X}x<^{X}x^{\prime}$ so that
$z<^{Z}x^{\prime}$ and hence
$y\mathrel{\ensurestackMath{\stackengine{-.5ex}{\lessdot}{-}{U}{c}{F}{F}{S}}}^{W}z\lessdot^{W}x^{\prime}$.
But $(W,\lessdot^{W})$ is an $\omega$-order and hence $\\{y\in W\mid
y\lessdot^{W}x^{\prime}\\}$ is finite.

Let $\lessdot^{Y}$ extend $\lessdot^{W}$ and be such that for all $y\in Y$,
$y\lessdot^{Y}x$ iff $y\in F$. To show that $\lessdot^{Y}$ is an
$\omega$-order, it is enough to show that $\\{y\in Y\mid y<^{Y}x\\}$ is
finite, but this is precisely $F$. Since $F\cap X=\\{z\in Z\mid
z<^{Z}x\\}=\\{x^{\prime}\in X\mid x^{\prime}<^{X}x\\}$, it follows that
$\mathord{\lessdot^{Y}}\supseteq\mathord{<^{X}}$. Finally, if $\lessdot^{W}$
and $<^{W}$ agree on $W\setminus W_{0}$ where $W_{0}\subseteq W$ is finite,
then $<^{Y}$ and $\lessdot^{Y}$ agree on $Y\setminus(W_{0}\cup\\{x\\})$ so
that $\mathord{<^{Y}}\sim\mathord{\lessdot^{Y}}$ as required. ∎

######  Lemma A.4.

Suppose that $(X_{i})_{i<\omega}$ is an increasing sequence of countable sets,
$(X_{i},<^{i})$ are $\omega$-orders, and
$\mathord{<^{i+1}}|_{X_{i}}\sim\mathord{<^{i}}$ for all $i<\omega$. Then there
are $\omega$-orders $\lessdot^{i}$ on $X_{i}$ such that
$\mathord{\lessdot^{0}}=\mathord{<^{0}}$, and
$\mathord{\lessdot^{i}}\sim\mathord{<^{i}}$, and
$\mathord{\lessdot^{i+1}}|_{X_{i}}=\mathord{\lessdot^{i}}$ for all $i<\omega$.

###### Proof.

Inductively define $\lessdot^{i}$ as follows. Let
$\mathord{\lessdot^{0}}=\mathord{<^{0}}$. Suppose we defined $\lessdot^{i}$.
Since $\mathord{<^{i}}\sim\mathord{\lessdot^{i}}$ and
$\mathord{<^{i+1}}|_{X_{i}}\sim\mathord{<^{i}}$, it follows that
$\mathord{<^{i+1}}|_{X_{i}}\sim\mathord{\lessdot^{i}}$. By Lemma A.3, there is
some $\omega$-order $\lessdot^{i+1}$ on $X_{i+1}$ such that
$\mathord{\lessdot^{i+1}}\sim\mathord{<^{i+1}}$ and
$\mathord{\lessdot^{i+1}}|_{X_{i}}=\mathord{\lessdot^{i}}$, as required. ∎

###### Proof of Theorem A.2.

We define the orders $<^{\alpha}$ by induction on
$\omega\leq\alpha<\omega_{1}$. Define $<^{\omega}$ as the canonical order on
$\omega$.

Suppose that $\alpha=\beta+1$ and $<^{\beta}$ has been defined. Let
$\mathord{<^{\alpha}}=\mathord{<^{\beta}}\cup\\{(\beta,\gamma)\mid\gamma<\beta\\}$.
In other words, we put $\beta$ as the first element of $<^{\alpha}$ without
changing anything else. Now, if $\gamma\leq\beta$ then
$\mathord{<^{\alpha}}|_{\gamma}=\mathord{<^{\beta}}|_{\gamma}\sim\mathord{<^{\gamma}}$
by induction.

Now suppose that $\alpha>\omega$ is a limit ordinal. Let
$(\alpha_{i})_{i<\omega}$ be an increasing sequence of ordinals, cofinal in
$\alpha$, where $\alpha_{0}=\omega$. Apply Lemma A.4 to the sequence
$(\alpha_{i},<^{\alpha_{i}})$ (which we can by the induction hypothesis) to
get $\omega$-orders $\lessdot^{\alpha_{i}}$ on $\alpha_{i}$ such that
$\mathord{\lessdot^{\alpha_{0}}}=\mathord{<^{\alpha_{0}}}=\mathord{<^{\omega}}$,
and $\mathord{\lessdot^{\alpha_{i}}}\sim\mathord{<^{\alpha_{i}}}$, and
$\mathord{\lessdot^{\alpha_{i+1}}}\supseteq\mathord{\lessdot^{\alpha_{i}}}$.

Let $\mathord{<^{*}}=\bigcup\\{\mathord{\lessdot^{\alpha_{i}}}\mid
i<\omega\\}$. We define an $\omega$-order $<^{\alpha}$ on $\alpha$ by, roughly
speaking, concatenating the finite orders obtained by taking, for each
$i<\omega$ in turn, those elements of $\alpha_{i}$ which are
$\lessdot^{\alpha_{i}}$-less than $i$ and have not yet been taken, ordered by
$\lessdot^{\alpha_{i}}$. Formally: for $\beta<\alpha$, let $(-\infty,\beta)$
be $\\{\gamma<\alpha\mid\gamma<^{*}\beta\\}$. Define inductively sets
$b_{i}\subseteq\alpha$ for $i<\omega$ as follows:
$b_{i}=\alpha_{i}\cap(-\infty,i)\setminus\bigcup_{j<i}{b_{j}}$ (so
$b_{0}=\emptyset=(-\infty,0)\cap\alpha_{0}$, since
$\mathord{\lessdot^{\alpha_{0}}}=\mathord{<^{\omega}}$ is the canonical order
on $\omega$). Note that $b_{i}\cap b_{j}=\emptyset$ for $i\neq j$ and that
$\alpha=\bigcup_{i<\omega}b_{i}$ (if $\beta<\alpha$, then $\beta<\alpha_{i}$
for some $i<\omega$ and hence $\beta\lessdot^{\alpha_{i}}m$ for some
$m<\omega$, so that $\beta\in(-\infty,m)$ and hence $\beta\in b_{k}$ for some
$k\leq\max\\{i,m\\}$). Finally, note that each $b_{i}$ is finite since
$(\alpha_{i},\lessdot^{\alpha_{i}})$ has order type $\omega$.

Order each $b_{i}$ by $<^{*}$ and put the $b_{i}$’s in order to define
$<^{\alpha}$. More formally, let $<^{lex}$ be the lexicographical order on
$\omega\times\alpha$ (taking the canonical order on $\omega$ and $<^{*}$ on
$\alpha$). For $\beta<\alpha$ let $i(\beta)$ be such that $\beta\in
b_{i(\beta)}$, and for $\beta,\gamma<\alpha$ put $\gamma<^{\alpha}\beta$ iff
$(i(\beta),\beta)<^{lex}(i(\gamma),\gamma)$.

We check that $<^{\alpha}$ is as required. The order type of $(\alpha,<^{*})$
is $\omega$ since each $b_{i}$ is finite, so that for any $\beta<\alpha$,
$\\{\gamma<\alpha\mid\gamma<^{\alpha}\beta\\}$ is finite. Now suppose that
$\beta<\alpha$. Then $\beta<\alpha_{i}$ for some $i<\omega$. Since
$\mathord{<^{\beta}}\sim\mathord{<^{\alpha_{i}}}|_{\beta}$ and
$\mathord{<^{\alpha_{i}}}\sim\mathord{\lessdot^{\alpha_{i}}}$, to show
$\mathord{<^{\beta}}\sim\mathord{<^{\alpha}}|_{\beta}$ it suffices to check
that $\mathord{\lessdot^{\alpha_{i}}}\sim\mathord{<^{\alpha}}|_{\alpha_{i}}$.

To show this we show that if $\gamma,\beta\in\alpha_{i}\setminus\bigcup_{j\leq
i}b_{j}$ then

(*) $\gamma\lessdot^{\alpha_{i}}\beta\iff\gamma<^{\alpha}\beta.$

Indeed, if $\gamma,\beta\in b_{j}$ for some $j<\omega$ then Eq. * follows from
the fact that $<^{\alpha}$ equals $<^{*}$ on $b_{j}$, so extends
$\lessdot^{\alpha_{i}}|_{b_{j}}$. Suppose that $\gamma\in b_{j}$, $\beta\in
b_{k}$ and $j\neq k$, so without loss $i<j<k$. Then, since
$\gamma,\beta\in\alpha_{i}$, necessarily $\gamma\in(-\infty,j)$ and
$\beta\notin(-\infty,j)$. In this case,
$\gamma\lessdot^{\alpha_{i}}j\lessdot^{\alpha_{i}}\beta$ (since this is true
for $<^{*}$) and $\gamma<^{\alpha}\beta$ by definition. ∎

## References

  * BKS [21] Martin Bays, Itay Kaplan, and Pierre Simon.  Density of compressible types and some consequences, 2021.
  * CS [13] Artem Chernikov and Pierre Simon.  Externally definable sets and dependent pairs.  Israel J. Math., 194(1):409–425, 2013.
  * CS [15] Artem Chernikov and Pierre Simon.  Externally definable sets and dependent pairs II.  Trans. Amer. Math. Soc., 367(7):5217–5235, 2015.
  * EK [20] Shlomo Eshel and Itay Kaplan.  On uniform definability of types over finite sets for NIP formulas.  Journal of Mathematical Logic, 0(0):2150015, 2020.
  * Jec [03] Thomas Jech.  Set theory.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003.  The third millennium edition, revised and expanded.
  * She [09] Saharon Shelah.  Dependent first order theories, continued.  Israel J. Math., 173:1–60, 2009.
  * Sim [15] Pierre Simon.  A guide to NIP theories, volume 44 of Lecture Notes in Logic.  Association for Symbolic Logic, Chicago, IL; Cambridge Scientific Publishers, Cambridge, 2015.


# Demand-Aware Payment Channel Networks111Research in part supported by the
European Research Council (ERC), consolidator project No. 864228, Horizon
2020, 2020-2025.

Lukas Aumayr1 Esra Ceylan2 Matteo Maffei1
Pedro Moreno-Sanchez3 Iosif Salem2 Stefan Schmid2
1 TU Wien 2 University of Vienna 3 IMDEA Software Institute

###### Abstract

This paper initiates the study of demand-aware payment channel networks:
offchain cryptocurrency networks whose topology is optimized toward the demand
(i.e., financial transactions) it currently serves. In particular, we present
a model and optimization framework which allows to compute where to optimally
establish virtual payment channels: virtual payment channels allow to avoid
intermediaries when routing payments, and hence to reduce fees and latency;
however, establishing payment channels also comes at a cost.

##  1 Introduction

Offchain cryptocurrency networks (also known as payment channel networks [6])
have emerged as a promising solution to mitigate the scalability issues of
blockchain technologies. Offchain networks allow to perform payments outside
of the blockchain, and hence do not require to validate every single
transaction through the expensive consensus algorithms. To this end,
participants establish payment channels to each other, and as long as the
transferred payments do not exceed the channel capacity, they do not have to
be committed to the blockchain. In particular, popular offchain networks such
as Lightning [7] support multi-hop routing of transactions across multiple
payment channels, which reduces the number of required payment channels in a
network but comes at a higher routing costs as intermediate nodes typically
charge fee as well as a reduction on reliability as dishonest intermediate
nodes can disrupt payments.

Recently, the concept of virtual channels has been introduced: virtual
channels [3, 1] allow to avoid involving intermediaries when making individual
payments. In a nutshell, two users sharing a payment channel with a common
intermediary can use (part of) the capacity at those channels to create a
virtual channel connecting them directly. Such virtual channels can hence be
used to reduce fees from intermediaries and increase the reliability of the
payments, but in turn come at a creation cost.

This paper is motivated by the concept of demand-aware payment channel
networks: offchain networks whose topology is optimized toward the workload it
serves (i.e., the financial transactions to be performed). The concept of
demand-aware networks [2] has been studied in other contexts before, in
particular in reconfigurable optical networks [4]. In the context of payment
channel networks, demand-awareness can be realized by establishing virtual
channels between particularly active communication pairs, allowing to
significantly reduce communication fees and hence to amortize the cost of
establishing the virtual channels.

Our main contribution is a formal model and an optimization framework for
computing optimal virtual channels in a demand-aware manner.

#### Paper organization

In Section 2 we introduce our model for offchain networks and in Section 3 we
provide an Integer Linear Program (ILP) that computes an optimal solution to
the problem of how to establish virtual channels to optimize the payments
according to the demand.

##  2 Our Model

###  2.1 Virtual channels

In this section, we formalize the notion of payment-channel network extended
with virtual channels. In particular, our definition extends the definition of
a PCN [6] in order to support virtual channels, the latter as defined in [1].

######  Definition 1 (VPCN)

A VPCN is defined as a graph
$\mathcal{G}:=(\mathcal{V},\mathcal{E}_{p}\cup\mathcal{E}_{v})$ where
$\mathcal{V}$ denotes the set of nodes in the network, $\mathcal{E}_{p}$
denotes the set of payment channels and $\mathcal{E}_{v}$ denotes the set of
virtual channels. Each payment channel is defined by a tuple
$(\textit{pc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$222In [6], a
payment channel also contains a timeout parameter. In practice is no longer
required [7] and thus we omit it here., where $\textit{pc}_{\langle
v_{1},v_{2}\rangle}$ denotes a payment channel identifier,
$\beta_{i\in\\{1,2\\}}$ denotes the current balance of the node
$v_{i\in\\{1,2\\}}$, $f_{i\in\\{1,2\\}}$ is the base fee and
$p_{i\in\\{1,2\\}}$ the fee rate (proportional to the amount paid) charged to
use this channel in each direction, respectively. Analogously, a virtual
channel is defined by a tuple $(\textit{vc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$. 333As with
payment channels, for readability we omit the timeout parameter as it is not
strictly required.

A VPCN is defined with respect to a blockchain $\mathbb{B}$ that stores
publicly accessible entries of the form $(v,\beta^{{\small\textit{on-
chain}}})$ where $v$ denotes a Bitcoin address and $\beta^{{\small\textit{on-
chain}}}$ denotes its on-chain balance. For readability, we hereby use
$\mathbb{B}[v]$ to denote the on-chain balance of $v$ in $\mathbb{B}$.

A VPCN exposes the following operations:

openPayChannel $(v_{1},v_{2},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$

#### Input

Two nodes $v_{1}$, $v_{2}$ $\in\mathcal{V}$, an initial payment channel
capacity $\beta_{i\in\\{1,2\\}}$, two base routing fee values
$f_{i\in\\{1,2\\}}$ and two proportional routing fee values
$p_{i\in\\{1,2\\}}$

#### Pre-requirements

  * •

If $\mathbb{B}[v_{1}]<\beta_{1}$ or $\mathbb{B}[v_{2}]<\beta_{2}$, abort

#### Actions

  * •

Create a new payment channel $(\textit{pc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})\in\mathcal{E}_{p}$

  * •

Update the blockchain as $\mathbb{B}[v_{1}]=\mathbb{B}[v_{1}]-\beta_{1}$ and
$\mathbb{B}[v_{2}]=\mathbb{B}[v_{2}]-\beta_{2}$

closePayChannel $(\textit{pc}_{\langle v_{1},v_{2}\rangle})$

#### Input

A payment channel identifier $\textit{pc}_{\langle v_{1},v_{2}\rangle}$

#### Pre-requirements

  * •

Let $(\textit{pc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ be the
corresponding entry in $\mathcal{E}_{p}$. If such entry does not exist, abort.

#### Actions

  * •

Set $\mathbb{B}[v_{1}]=\mathbb{B}[v_{1}]+\beta_{1}$,
$\mathbb{B}[v_{2}]=\mathbb{B}[v_{2}]+\beta_{2}$

  * •

Remove the entry $(\textit{pc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ from
$\mathcal{E}_{p}$

openVirChannel $(\textit{pc}_{\langle v_{1},v_{I}\rangle},\textit{pc}_{\langle
v_{I},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2},f_{e})$444Similar
to having two fees (one per direction) in payment channels, we could have two
establishing fees here as well. For simplicity, we have only one for both
directions for now.

#### Input

Two payment channel identifiers $\textit{pc}_{\langle v_{1},v_{I}\rangle}$ and
$\textit{pc}_{\langle v_{I},v_{2}\rangle}$, an initial balance
$\beta_{i\in\\{1,2\\}}$, a base routing fee $f_{i\in\\{1,2\\}}$, a
proportional routing fee $p_{i\in\\{1,2\\}}$ and a establishing fee $f_{e}$

#### Pre-requirements

  * •

Let $(\textit{pc}_{\langle
v_{1},v_{I}\rangle},\beta^{\prime}_{1},\beta^{\prime}_{I},f^{\prime}_{1},f^{\prime}_{I},p^{\prime}_{1},p^{\prime}_{I})$
and $(\textit{pc}_{\langle
v_{I},v_{2}\rangle},\beta^{\prime\prime}_{I},\beta^{\prime\prime}_{2},f^{\prime\prime}_{I},f^{\prime\prime}_{2},p^{\prime\prime}_{I},p^{\prime\prime}_{2})$
be the entries in $\mathcal{E}_{p}$ corresponding to $\textit{pc}_{\langle
v_{1},v_{I}\rangle}$ and $\textit{pc}_{\langle v_{I},v_{2}\rangle}$. If
$(\beta_{1}+f_{e})<\beta^{\prime}_{1}$ or $\beta_{2}<\beta^{\prime}_{I}$ or
$\beta_{2}<\beta^{\prime\prime}_{2}$ or $\beta_{1}<\beta^{\prime\prime}_{I}$,
abort.

#### Actions

  * •

Update the entries in $\mathcal{E}_{p}$ as $(\textit{pc}_{\langle
v_{1},v_{I}\rangle},\beta^{\prime}_{1}-(\beta_{1}+f_{e}),\beta^{\prime}_{I}-\beta_{2}+f_{e},f^{\prime}_{1},f^{\prime}_{I},p^{\prime}_{1},p^{\prime}_{I})$
and $(\textit{pc}_{\langle
v_{I},v_{2}\rangle},\beta^{\prime\prime}_{I}-\beta_{1},\beta^{\prime\prime}_{2}-\beta_{2},f^{\prime\prime}_{I},f^{\prime\prime}_{2},p^{\prime\prime}_{I},p^{\prime\prime}_{2})$

  * •

Add the entry $(\textit{vc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ in
$\mathcal{E}_{v}$

closeVirChannel $(\textit{vc}_{\langle v_{1},v_{2}\rangle})$

#### Input

A virtual channel identifier $\textit{vc}_{\langle v_{1},v_{2}\rangle}$

#### Pre-requirements

  * •

Let $(\textit{vc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ be the
corresponding entry in $\mathcal{E}_{v}$. If such entry does not exist, abort.

#### Actions

  * •

Update the entries in $\mathcal{E}_{p}$ as $(\textit{pc}_{\langle
v_{1},v_{I}\rangle},\beta^{\prime}_{1}+\beta_{1},\beta^{\prime}_{I}+\beta_{2},f^{\prime}_{1},f^{\prime}_{I},p^{\prime}_{1},p^{\prime}_{I})$
and $(\textit{pc}_{\langle
v_{I},v_{2}\rangle},\beta^{\prime\prime}_{I}+\beta_{1},\beta^{\prime\prime}_{2}+\beta_{2},f^{\prime\prime}_{I},f^{\prime\prime}_{2},p^{\prime\prime}_{I},p^{\prime\prime}_{2})$

  * •

Remove the entry $(\textit{vc}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ from
$\mathcal{E}_{v}$

Update{Pay,Vir}Channel $(\textit{c}_{\langle v_{1},v_{2}\rangle},\beta)$

#### Input

A payment or virtual channel identifier $\textit{c}_{\langle
v_{1},v_{2}\rangle}$

#### Pre-requirements

  * •

Let $(\textit{c}_{\langle
v_{1},v_{2}\rangle},\beta_{1},\beta_{2},f_{1},f_{2},p_{1},p_{2})$ be the
corresponding entry in $\mathcal{E}_{p}\cup\mathcal{E}_{v}$. If such entry
does not exist or it exists but $\beta_{1}<\beta$, abort.

#### Actions

  * •

Update the payment or virtual channel as follows $(\textit{c}_{\langle
v_{1},v_{2}\rangle},\beta_{1}-\beta,\beta_{2}+\beta,f_{1},f_{2},p_{1},p_{2})$

Pay $((\textit{c}_{\langle s,v_{1}\rangle},\ldots,\textit{c}_{\langle
v_{n},r\rangle}),\beta)$

#### Input

A list of (payment or virtual) channel identifiers $(\textit{c}_{\langle
s,v_{1}\rangle},\ldots,\textit{c}_{\langle v_{n},r\rangle})$ and a payment
value $\beta$

#### Pre-requirements

  * •

The channels must form a path from the sender (i.e., $s$) to the receiver
(i.e., $r$). Otherwise, abort.

  * •

For each channel $(\textit{c}_{\langle
v_{i},v_{i+1}\rangle},\beta_{i},\beta_{i+1},f_{i},f_{i+1},p_{i},p_{i+1})$ in
the path, it must be the case that $\beta_{i}\geq\gamma_{i}$ where
$\gamma_{i}:=\beta-\sum_{j=0}^{i-1}(f_{j}+p_{j}\cdot\beta)$. Otherwise, abort.

#### Actions

  * •

Update each channel in the path as follows $(\textit{c}_{\langle
v_{i},v_{i+1}\rangle},\beta_{i}-\gamma_{i},\beta_{i+1}+\gamma_{i},f_{i},f_{i+1},p_{i},p_{i+1})$

##  3 Integer Linear Program for PCNs

We design an integer linear program (ILP) that computes an optimal payment
channel network, given the payment channels, the charging fees, the demand
matrix, and the total available budget. The objective function of our ILP aims
to maximize the total amount of successful transactions. The constraints
require that (1) a payment channel is used only if it exists, (2) the total
costs for creating virtual channels and routing through payment or virtual
channels does not exceed the total budget, (3 & 4) a transaction is successful
if and only if there is a path used for it from source to destination, and
Section 3.2 includes constraints related to building virtual channels.

A virtual channel can be built by two adjacent channels, payment or virtual
(all four combinations are possible). Thus it is possible that there exist
recursive virtual channels. A virtual channel over two adjacent payment
channels is a level 0 virtual channel. Moreover, a virtual channel with
(recursion) level $\ell+1$ is built over two adjacent channels, such that one
of the two is a virtual channel with recursion level $\ell$ and the other is
either a payment channel or a virtual channel of level $\ell$ or less. We
require (in the set of constraints of Section 3.2) that there exists at most
one virtual channel between two nodes, a virtual channel is used for a
transaction only if it exists, and that if a payment channel is used for
creating a virtual channel, the virtual channel’s capacity should be reduced
from the one of the payment channel. In the following we elaborate on the
design of our ILP.

#### Input

We assume that the ILP input includes (a) a graph $G=(V,E_{p})$, where $|V|=n$
and $E_{p}$ is the set of payment channels, (b) an $n\times n$ Demand-Matrix
$D$, such that for two nodes $s,r\in V$ the entry
$D_{sr}\subset(\mathbb{R}_{+})^{\mathbb{N}}$ is the set of transactions from
$s$ to $r$, and (c) the constants mentioned below.

#### Variables & Constants

We consider the following list of variables (var) and constants (const)
related to payment (pc) and virtual channels (vc).

  1. 1.

_trans sr_$>0$: a transaction $\in D_{sr}$ of certain size from $s$ to $r$
(const)

  2. 2.

$\emph{trans${}_{sr}$\textunderscore succ}\in\\{0,1\\}$: transaction _trans
sr_ is successful (var)

  3. 3.

_budget_ : maximal available budget for total costs (const)

  4. 4.

$\emph{pc${}_{ij}$}\in\\{0,1\\}$: payment channel from $i$ to $j$ exists
(const)

  5. 5.

$\emph{pc${}_{ij}($trans${}_{sr})$}\in\\{0,1\\}$: payment channel from $i$ to
$j$ is used in the path from $s$ to $r$ for transaction _trans sr_ (var)

  6. 6.

$\emph{vc${}_{ij}($trans${}_{sr})$}\in\\{0,1\\}$: virtual channel from $i$ to
$j$ is used in the path from $s$ to $r$ for transaction _trans sr_ (var)

  7. 7.

_pc ${}_{ij}^{r}$.base_fee_: base fee for using payment channel from $i$ to
$j$ in path (from $s$) to $r$ (const)

$\displaystyle\emph{pc${}_{ij}^{r}$.base\textunderscore
fee}:\begin{cases}=0,&j=r\\\ \geq 0,&j\neq r\end{cases}$

  8. 8.

_pc ${}_{ij}^{r}$.prop_fee_: proportional fee (per unit of transaction size)
for using payment channel from $i$ to $j$ in path (from $s$) to $r$ (const)

$\displaystyle\emph{pc${}_{ij}^{r}$.prop\textunderscore
fee}:\begin{cases}=0,&j=r\\\ \geq 0,&j\neq r\end{cases}$

  9. 9.

_vc ${}_{ij}^{r}$.base_fee_: base fee for using virtual channel from $i$ to
$j$ in path (from $s$) to $r$ (const)

$\displaystyle\emph{vc${}_{ij}^{r}$.base\textunderscore
fee}:\begin{cases}=0,&j=r\\\ \geq 0,&j\neq r\end{cases}$

  10. 10.

_vc ${}_{ij}^{r}$.prop_fee_: proportional fee (per unit of transaction size)
for using virtual channel from $i$ to $j$ in path (from $s$) to $r$ (const)

$\displaystyle\emph{vc${}_{ij}^{r}$.prop\textunderscore
fee}:\begin{cases}=0,&j=r\\\ \geq 0,&j\neq r\end{cases}$

  11. 11.

_vc ij.creation_cost_ $\geq 0$: creation cost of virtual channel from $i$ to
$j$ (const)

  12. 12.

_pc ij.capacity_$\geq 0$: capacity of $i$ on the payment channel from $i$ to
$j$ (const)

  13. 13.

_routing_cost sr_: minimal total routing costs from $s$ to $r$ (var)

$\displaystyle\emph{routing\textunderscore cost${}_{sr}$}=\hfill$
$\displaystyle\sum_{\emph{trans${}_{sr}$}\in
D_{sr}}\sum_{i,j=1}^{n}\emph{pc${}_{ij}($trans${}_{sr})$}\cdot\left(\emph{pc${}_{ij}^{r}$.base\textunderscore
fee}+\emph{pc${}_{ij}^{r}$.prop\textunderscore
fee}\cdot\emph{trans${}_{sr}$}\right)$
$\displaystyle+\emph{vc${}_{ij}($trans${}_{sr})$}\cdot\left(\emph{vc${}_{ij}^{r}$.base\textunderscore
fee}+\emph{vc${}_{ij}^{r}$.prop\textunderscore
fee}\cdot\emph{trans${}_{sr}$}\right)$

If pc from $i$ to $j$ is used for a transaction _trans sr_, pay _pc
${}_{ij}^{r}$.base_fee_ and _pc ${}_{ij}^{r}$.prop_fee_ (linear in transaction
size); same for vc.

#### Objective function

The objective of our ILP is to maximize the amount of successful transactions.

$\displaystyle\max\left(\sum_{D_{sr}\in D}\sum_{\emph{trans${}_{sr}$}\in
D_{sr}}\emph{trans${}_{sr}$}\cdot\emph{trans${}_{sr}$\textunderscore
succ}\right)$

###  3.1 Constraints independent from recursion

Constraints (1)–(4) are independent from the ones related to the construction
of recursive virtual channels (Section 3.2).

  1. 1.

$\emph{pc${}_{ij}($trans${}_{sr})$}\leq\emph{pc${}_{ij}$}$

A pc can only be used for a transaction if it exists.

  2. 2.

Upper bound for total costs: [Definition of _creation_cost_ , see 3.2]

$\displaystyle\emph{creation\textunderscore
cost}+\sum_{s,r=1}^{n}\emph{routing\textunderscore
cost${}_{sr}$}\leq\emph{budget}$

(Note that we aggregate individual channel routing costs in this constraint)

  3. 3.

$\emph{trans${}_{sr}$\textunderscore
succ}=0\Leftrightarrow\sum_{i,j=1}^{n}\emph{pc${}_{ij}($trans${}_{sr})$}+\emph{vc${}_{ij}($trans${}_{sr})$}=0$:

    1. (a)

$\emph{pc${}_{ij}($trans${}_{sr})$}\leq\emph{trans${}_{sr}$\textunderscore
succ}$
(use a channel for _trans sr_ only if it is successful)

    2. (b)

$\emph{vc${}_{ij}($trans${}_{sr})$}\leq\emph{trans${}_{sr}$\textunderscore
succ}$

    3. (c)

To avoid the case $\emph{trans${}_{sr}$\textunderscore succ}=1$ and
$\sum_{i,j=1}^{n}\emph{pc${}_{ij}($trans${}_{sr})$}+\emph{vc${}_{ij}($trans${}_{sr})$}=0$

$\displaystyle\emph{trans${}_{sr}$\textunderscore
succ}\leq\sum_{i,j=1}^{n}\emph{pc${}_{ij}($trans${}_{sr})$}+\emph{vc${}_{ij}($trans${}_{sr})$}$

(if $\emph{trans${}_{sr}$\textunderscore succ}=1$ then there has to be at
least one channel which is used for this transaction)

  4. 4.

Flow conservation:

$\displaystyle\sum_{j=1}^{n}\big{(}\emph{pc${}_{ij}($trans${}_{sr})$}+\emph{vc${}_{ij}($trans${}_{sr})$}\big{)}-\big{(}\emph{pc${}_{ji}($trans${}_{sr})$}+\emph{vc${}_{ji}($trans${}_{sr})$}\big{)}$
$\displaystyle=\begin{cases}-\emph{trans${}_{sr}$\textunderscore
succ},&\text{if }i=s,\\\ \emph{trans${}_{sr}$\textunderscore succ},&\text{if
}i=r,\\\ 0,&\text{otherwise.}\end{cases}$

###  3.2 Constraints for creating recursive virtual channels

We start by presenting the constraints related to constructing recursive
virtual channels and assigning their capacities, at level 0 (L0), where two
payment channels are used (pc,pc) and level 1 (L1) which can be constructed by
the combinations (pc,vc), (vc,pc), and (vc,vc), where a vc here is of level 0.
Then we generalize from level 1 to level m, in which we have the same three
options (pc,vc), (vc,pc), and (vc,vc), but each vc is now a virtual channel of
level at most $m-1$. Finally, we present constraints and variables (a)–(e),
which are pertinent to virtual channels and relate to all recursion levels.

    1. (L0)

(pc,pc):

_L 0_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level 0 virtual channel from $i$ to
$j$ exists using 2 payment channels from $i$ to $k$ and from $k$ to $j$ (_pc
ik_, _pc kj_)

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there are 2 pc connecting $i$ and
$j$:

$\displaystyle 2\cdot\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}\leq\emph{pc${}_{ik}$}+\emph{pc${}_{kj}$}$

      2. ii.

Capacity of this vc is bounded by the capacity of the used pc

$\displaystyle\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{ik}$.capacity}$
$\displaystyle\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{kj}$.capacity}$

      3. iii.

The capacity of a vc should be 0 if the existence variable is 0, i.e.
$\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

For this constraint a constant $\emph{max\textunderscore
cap}=\max\emph{pc${}_{ij}$.capacity}$ (maximal channel capacity) is needed

$\displaystyle\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

      4. iv.

At most one vc from $i$ to $j$ can be created in every level

$\displaystyle\sum_{k\in V}\emph{L${}_{0}$\textunderscore vc${}_{ij}^{k}$}\leq
1$

Note that this constraint and iii. imply
$\sum_{k}\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{max\textunderscore cap}$.

    2. (L1.pv)

(pc,vc):

_L 1pv_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level 1 vc from $i$ to $j$ exists,
first using _pc ik_ and then an existing $L_{0}$ virtual channel from $k$ to
$j$

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there is a pc and a $L_{0}$ vc
connecting $i$ and $j$:

$\displaystyle 2\cdot\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}\leq\emph{pc${}_{ik}$}+\sum_{l\in
V}\emph{L${}_{0}$\textunderscore vc${}_{kj}^{l}$}$

(because of (L0)iv. the sum on right-hand side is at most 1)

      2. ii.

Capacity of vc is bounded by capacity of the used pc and vc

$\displaystyle\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{ik}$.capacity}$
$\displaystyle\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{kj}^{l}$}.capacity$

(second inequality on right-hand side: because of (L0)iii. and (L0)iv. at most
one summand is not equal to 0)

      3. iii.

$\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

(if existence variable is 0, then the corresponding capacity should also be 0)

    3. (L1.vp)

(vc, pc): symmetric to previous case

_L 1vp_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level 1 vc from $i$ to $j$ exists,
first using an existing $L_{0}$ virtual channel from $i$ to $k$ and then _pc
kj_

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there is a $L_{0}$ vc and a pc
connecting $i$ and $j$:

$\displaystyle 2\cdot\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}+\emph{pc${}_{kj}$}$

      2. ii.

Capacity of vc is bounded by capacity of the used vc and pc

$\displaystyle\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}.capacity$ $\displaystyle\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{kj}$.capacity}$

(Because of ii. at most one summand on right-hand side in first inequality is
not equal to 0)

      3. iii.

$\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

    4. (L1.vv)

(vc, vc):

_L 1vv_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level 1 vc from $i$ to $j$ exists,
using two existing $L_{0}$ virtual channels from $i$ to $k$ and then from $k$
to $j$

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there are two $L_{0}$ vc connecting
$i$ and $j$:

$\displaystyle 2\cdot\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}+\sum_{l\in V}\emph{L${}_{0}$\textunderscore vc${}_{kj}^{l}$}$

(Because of (L0)iii. and(L0)iv. each of the sums on the right-hand side it at
most 1)

      2. ii.

Capacity of vc is bounded by the capacity of the used vc

$\displaystyle\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}.capacity$ $\displaystyle\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\sum_{l\in V}\emph{L${}_{0}$\textunderscore
vc${}_{kj}^{l}$}.capacity$

(Because if ii. at most one summand on right-hand side in both inequalities is
not equal to 0)

      3. iii.

$\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{1vv}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

At the end of this level we need a constraint for all cases:

      4. (L1)

After every level at most one vc from $i$ to $j$ should exist

$\displaystyle\sum_{k\in V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{1pv}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{1vp}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{1vv}$\textunderscore vc${}_{ij}^{k}$}\right)\leq
1$

    5. (Lm.pv)

(pc, vc) at level $m$:

_L mpv_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level m vc from $i$ to $j$ exists,
first using _pc ik_ and then an existing lower level virtual channel from $k$
to $j$

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there is a pc and a vc connecting
$i$ and $j$:

$\displaystyle 2\cdot\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}\leq\emph{pc${}_{ik}$}+$ $\displaystyle\sum_{l\in
V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{kj}^{l}$}+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{kj}^{l}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{kj}^{l}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}\right)\right)$

The used vc can be of every level from 0 to $m-1$ with an arbitrary
intermediate node $l$.

         * •

For L0 we have only one case: _L 0_vc${}_{kj}^{l}$_

         * •

For the other levels $q\in\\{1,...,m-1\\}$ we have three cases: (pc, vc), (vc,
pc) and (vc,v c)

      2. ii.

Capacity of vc is bounded by capacity of the used pc and vc

$\displaystyle\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{ik}$.capacity}$
$\displaystyle\emph{L${}_{mpv}$\textunderscore vc${}_{ij}^{k}$}.capacity$
$\displaystyle\hskip 28.45274pt\leq\sum_{l\in
V}\bigg{(}\emph{L${}_{0}$\textunderscore vc${}_{kj}^{l}$}.capacity$
$\displaystyle\hskip
28.45274pt+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{kj}^{l}$}.capacity+\emph{L${}_{qvp}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right.$ $\displaystyle\hskip
28.45274pt\left.+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right)\bigg{)}$

(Because if ii. in every recursion step at most one summand in outer sum on
right-hand side in second inequality is not equal to 0)

      3. iii.

$\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{mpv}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

    6. (Lm.vp)

(vc, pc): symmetric to previous case

_L mvp_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level $m$ vc from $i$ to $j$ exists,
first using an existing lower level virtual channel from $i$ to $k$ and then
_pc kj_

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there is a vc and a pc connecting
$i$ and $j$:

$\displaystyle 2\cdot\emph{L${}_{mvp}$\textunderscore vc${}_{ij}^{k}$}$
$\displaystyle\leq\sum_{l\in V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ik}^{l}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{ik}^{l}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{ik}^{l}$}\right)\right)+\emph{pc${}_{kj}$}$

      2. ii.

Capacity of vc is bounded by capacity of the used vc and pc

$\displaystyle\emph{L${}_{mvp}$\textunderscore vc${}_{ij}^{k}$}.capacity$
$\displaystyle\hskip 28.45274pt\leq\sum_{l\in
V}\bigg{(}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}.capacity+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ik}^{l}$}.capacity\right.$ $\displaystyle\hskip
28.45274pt\left.+\emph{L${}_{qvp}$\textunderscore
vc${}_{ik}^{l}$}.capacity+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right)\bigg{)}$
$\displaystyle\emph{L${}_{mvp}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{pc${}_{kj}$.capacity}$

      3. iii.

$\emph{L${}_{mvp}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{mvp}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{mvp}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{mvp}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

    7. (Lm.vv)

(vc, vc):

_L mvv_vc${}_{ij}^{k}$_ $\in\\{0,1\\}$: a level $m$ vc from $i$ to $j$ exists,
using two existing lower level virtual channels from $i$ to $k$ and then from
$k$ to $j$

      1. i.

_vc_ ${}_{ij}^{k}$ can only be created if there are 2 vc connecting $i$ and
$j$:

$\displaystyle 2\cdot$ Lmvv_vc${}_{ij}^{k}$ $\displaystyle\leq\sum_{l\in
V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{l}$}+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ik}^{l}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{ik}^{l}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{ik}^{l}$}\right)\right)$ $\displaystyle+\sum_{l\in
V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{kj}^{l}$}+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{kj}^{l}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{kj}^{l}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}\right)\right)$

      2. ii.

Capacity of vc is bounded by the capacity of the used vc

$\displaystyle\emph{L${}_{mvv}$\textunderscore vc${}_{ij}^{k}$}.capacity$
$\displaystyle\hskip 28.45274pt\leq\sum_{l\in
V}\bigg{(}\emph{L${}_{0}$\textunderscore vc${}_{ik}^{l}$}.capacity$
$\displaystyle\hskip
28.45274pt+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ik}^{l}$}.capacity+\emph{L${}_{qvp}$\textunderscore
vc${}_{ik}^{l}$}.capacity\right.$ $\displaystyle\left.\hskip
28.45274pt+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right)\bigg{)}$
$\displaystyle\emph{L${}_{mvv}$\textunderscore vc${}_{ij}^{k}$}.capacity$
$\displaystyle\hskip 28.45274pt\leq\sum_{l\in
V}\bigg{(}\emph{L${}_{0}$\textunderscore vc${}_{kj}^{l}$}.capacity$
$\displaystyle\hskip
28.45274pt+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{kj}^{l}$}.capacity+\emph{L${}_{qvp}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right.$ $\displaystyle\left.\hskip
28.45274pt+\emph{L${}_{qvv}$\textunderscore
vc${}_{kj}^{l}$}.capacity\right)\bigg{)}$

      3. iii.

$\emph{L${}_{mvv}$\textunderscore
vc${}_{ij}^{k}$}=0\Rightarrow\emph{L${}_{mvv}$\textunderscore
vc${}_{ij}^{k}$}.capacity=0$

$\displaystyle\emph{L${}_{mvv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\leq\emph{L${}_{mvv}$\textunderscore
vc${}_{ij}^{k}$}\cdot\emph{max\textunderscore cap}$

      4. (Lm)

After every level at most one vc from $i$ to $j$ should exist

$\displaystyle\sum_{k\in V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}+\sum_{q=1}^{m-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{ij}^{k}$}\right)\right)\leq 1$

Constraints for all levels of recursion

    8. (a)

$\emph{exist\textunderscore vc${}_{ij}$}\in\mathbb{N}$: number of vc from $i$
to $j$ in all levels - should be 0 (if vc does not exist) or 1 (if vc exists)

$\displaystyle\emph{exist\textunderscore vc${}_{ij}$}:=\sum_{k\in
V}\left(\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}+\sum_{q=1}^{n-1}\left(\emph{L${}_{qpv}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{qvp}$\textunderscore
vc${}_{ij}^{k}$}+\emph{L${}_{qvv}$\textunderscore
vc${}_{ij}^{k}$}\right)\right)$ $\displaystyle\emph{exist\textunderscore
vc${}_{ij}$}\leq 1$

(This constraint is also contained in the last step of the recursion)

    9. (b)

A virtual channel can be used for a transaction if it exists

$\displaystyle\emph{vc${}_{ij}($trans${}_{sr})$}\leq\emph{exist\textunderscore
vc${}_{ij}$}$

    10. (c)

_creation_cost_ : has to be payed for every existing vc

$\displaystyle\emph{creation\textunderscore
cost}=\sum_{i,j=1}^{n}\big{(}\emph{vc${}_{ij}$.creation\textunderscore
cost}\cdot\emph{exist\textunderscore vc${}_{ij}$}\big{)}$

    11. (d)

Capacity of a vc from $i$ to $j$ over intermediate node $k$

vc${}_{ij}^{k}$.capacity $\displaystyle:=\emph{L${}_{0}$\textunderscore
vc${}_{ij}^{k}$}.capacity+\sum_{q=1}^{n-1}\big{(}\emph{L${}_{qpv}$\textunderscore
vc${}_{ij}^{k}$}.capacity$ $\displaystyle+\emph{L${}_{qvp}$\textunderscore
vc${}_{ij}^{k}$}.capacity+\emph{L${}_{qvv}$\textunderscore
vc${}_{ij}^{k}$}.capacity\big{)}$

Constraint:

$\displaystyle\sum_{s,r}\big{(}\emph{vc${}_{ij}($trans${}_{sr})$}\cdot\emph{trans${}_{sr}$}\big{)}\leq\sum_{k\in
V}\emph{vc${}_{ij}^{k}$.capacity}$

    12. (e)

Constraint for capacity of a pc from $i$ to $j$

$\displaystyle\sum_{s,r}\big{(}$
$\displaystyle\emph{pc${}_{ij}($trans${}_{sr})$}\cdot\emph{trans${}_{sr}$}\big{)}$
$\displaystyle\leq\emph{pc${}_{ij}$.capacity}-\sum_{k\in
V}\Bigg{(}\emph{L${}_{0}$\textunderscore
vc${}_{ik}^{j}$}.capacity+\emph{L${}_{0}$\textunderscore
vc${}_{kj}^{i}$}.capacity+$ $\displaystyle\hskip
65.44133pt\left.\sum_{q=1}^{n-1}\big{(}\emph{L${}_{qpv}$\textunderscore
vc${}_{ik}^{j}$}.capacity+\emph{L${}_{qvp}$\textunderscore
vc${}_{kj}^{i}$}.capacity\big{)}\right)$

If _pc_ ij is used for creating a vc, then the capacity of this pc should be
reduced by the capacity of the vc; _pc_ ij can be used as the first or second
channel for creating a vc.

## Bibliographic Note

Our paper is parallel to the interesting work by Khamis and Rottenstreich [5]
who also study how to construct a network topology matching payment demands,
in a slightly different model, and where to place users in this topology.

## References

  * [1] Aumayr, L., Ersoy, O., Erwig, A., Faust, S., Hostáková, K., Maffei, M., Moreno-Sanchez, P., and Riahi, S. Bitcoin-compatible virtual channels.  Cryptology ePrint Archive, Report 2020/554, 2020.  https://eprint.iacr.org/2020/554.
  * [2] Avin, C., Mondal, K., and Schmid, S. Demand-aware network designs of bounded degree.  In Proc. International Symposium on Distributed Computing (DISC) (2017).
  * [3] Dziembowski, S., Eckey, L., Faust, S., and Malinowski, D. Perun: Virtual payment hubs over cryptocurrencies.  In IEEE Symposium on Security and Privacy (2019), pp. 106–123.
  * [4] Foerster, K.-T., and Schmid, S. Survey of reconfigurable data center networks: Enablers, algorithms, complexity.  In SIGACT News (2019).
  * [5] Khamis, J., and Rottenstreich, O. Demand-aware channel topologies for off-chain payments.  In Proc. 13th International Conference on Communication Systems and Networks (COMSNETS) (2021).
  * [6] Malavolta, G., Moreno-Sanchez, P., Kate, A., Maffei, M., and Ravi, S. Concurrency and Privacy with Payment-Channel Networks.  In ACM SIGSAC Conference on Computer and Communications Security, CCS (2017), pp. 455–471.
  * [7] Poon, J., and Dryja, T. The Bitcoin Lightning Network:.  59\.