# Modeling and Analysis for Cache-enabled Cognitive D2D Communications in
Cellular Networks

Chenchen Yang∗, Xingya Zhao∗, Yao Yao‡, Bin Xia∗
∗ Department of Electronic Engineering, Shanghai Jiao Tong University,
Shanghai, P. R. China
‡ Huawei Technologies Co., Ltd
Email: {zhanchifeixiang, claret.zhao<EMAIL_ADDRESS><EMAIL_ADDRESS>This
work is supported in part by the National High Technology Research and
Development Program of China under 863 5G (Grant NO. 2014AA01A702), and the
Shenzhen-Hong Kong Innovative Technology Cooperation Funding (Grant No.
SGLH20131009154139588).

###### Abstract

Exploiting cognition to the cache-enabled device-to-device (D2D) communication
underlaying the multi-channel cellular network is the main focus of this
paper. D2D pairs perform direct communications via sensing the available
cellular channels, bypassing the base station (BS). Dynamic service is
considered and the network performance is evaluated with the stochastic
geometry. Node locations are first modeled as mutually independent Poisson
Point Processes, and the service queueing process is formulated. Then the
corresponding tier association and cognitive access protocol are developed.
The delay and the length for the queue at the BS and D2D transmitter are
further elaborated, with modeling the traffic dynamics of request arrivals and
departures as the _discrete-time multiserver queue with priorities_. Moreover,
impacts of the physical layer and content-centric features on the system
performance are jointly investigated to provide a valuable insight.

##  I INTRODUCTION

As an essential candidate feature of the fifth generation (5G) network,
device-to-device (D2D) communications is an excellent technology for enhancing
the cellular coverage and capacity [1]. Employing D2D communication in
cellular networks with the concepts of cognitive radio networks is one of the
schemes that are being intensively studied for future networks [2, 3]. On the
other hand, despite the totally huge amount of data traffic suffering by the
network, only a small portion $(5-10\%)$ of “popular” data are frequently
accessed by the majority of the users [4]. Caching popular contents at
terminal devices allows frequency local sharing via D2D, yielding the traffic
offloading from the cellular network and the reduction of duplicated data
transmissions [5].

D2D communications in cellular networks are either network-assisted or
assistance-free [1]. In the former, the base stations (BS) takes centralized
control to allocate the resources for both cellular and D2D communications,
which may incur dramatically high computational and signaling overhead,
especially in the high-density network with large numbers of BSs, cellular and
D2D users [1, 6]. On the other hand, the assistance-free D2D advocates to
manage the communication with distributed D2D terminals bypassing BSs.
Compared with centralized approaches, distributed resource allocation schemes
incorporating the concept of cognitive networks for autonomous resource
allocation will be more scalable [1, 3].

Cognition is exploited for the assistance-free communication in [7]. The D2D
transmitter (TX) and receiver set up direct communication without the
supervision from the BS via the PC5 interface, which is defined by the Long
Term Evolution (LTE) standard. [1] focus on mixed overlay-underlay cognitive
D2D communications where devices sense the spectrum based on the energy
detection. In [8], the cognitive D2D TXs can communicate with the harvest
energy from the ambient interference via the cellular channel. Both the random
spectrum access and prioritized spectrum access policies are investigated.
Authors in [9] introduce cognition to femto access points to exploit the idle
channels of the macro BSs via spectrum sensing, avoiding severe interference.
[10] introduces the spectrum trading scheme to the cognitive D2D and cellular
network coexisting system based on game theory and learning method.

Cache-enabled D2D transmission implies that data can be cached at the terminal
devices for content sharing via D2D [11]. [12] identifies the connection
between the collaboration distance and the interference in a cache-enabled D2D
network with considering the video content popularity statistics. [13] divides
the cell into virtual square grids to make use of the caching capacity of
terminal devices, exploiting the redundancy of user requests. The performance
of different cluster centric content placement policies in a cache-enabled D2D
network is analyzed in [14], where the location of devices are modeled as a
Poisson cluster process. In [15], disjoint circular clusters are set based on
hard-core point process. Requesting users access contents from cache-enabled
users in the same cluster via out-of-band D2D in the cellular network.

Nevertheless, compared to the network-assisted D2D, assistance-free D2D
underlaying cellular networks has not been investigated enough. Moreover, few
studies exploit cognition to the cache-enabled D2D communications. Modeling
and exploring the performance of the cellular network embedded with the
cognitive and cache-enabled D2D communication is the focus of this paper. The
main contributions of this paper are summarized as follows:

  * •

_Introducing cognition to the cache-enabled D2D underlaying cellular
networks:_ Cache-enabled users (active as D2D TXs) and BSs are cooperative to
transmit contents. Assistance-free D2D communication is considered and D2D
pairs perform direct communications via spectrum sensing in the multi-channel
cellular environment.

  * •

_Dynamic service analysis with the stochastic geometry:_ We use tools of the
stochastic geometry to model the node locations. Different from the
traditional assumption in the stochastic geometric analysis that service nodes
are active at the full-load state, we consider the dynamic service and the
request queueing process is formulated.

  * •

_Evaluating the performance and facilitating the straightforward network
configuration:_ The probability mass function (PMF) of the delay and the
length for the queue at the BS and the D2D TX are derived, modeling the
traffic dynamics of request arrivals and departures at the BS and D2D TX as
the _discrete-time multiserver queue with priorities_.

  * •

_Highlighting the joint impacts of the physical layer and content-centric
features:_ Impacts of the content-centric features (e.g., content popularity,
the request intensity and the limited caching storage) and physical layer
parameters (e.g., node densities, channel fading and transmission powers) on
the network performance are investigated.

##  II System model and Protocol description

In this section, the network architecture is first elaborated. Then the tier
association protocol and the cognitive channel access are further developed.

###  II-A Network Architecture

We consider a network as illustrated in Fig. 1, where BSs and users are
spatially distributed according to two mutually independent homogeneous PPPs
$\Phi_{i}=\\{b_{i,j},j=0,1,2,...\\}$ with intensity ${\lambda}_{i}$ ($i=0,2$
for users and BSs, respectively) [16], and $\lambda_{0}\gg\lambda_{2}$. A
proportion ($0<\alpha<1$) of users are cache-enabled and they can be active as
D2D TXs, yielding a thinning homogeneous PPP
$\Phi_{1}=\\{b_{1,j},j=0,1,2,...\\}$ with intensity
${\lambda}_{1}=\alpha{\lambda}_{0}$.

Users request contents from a given library $\\{1,2,...,N\\}$ and all contents
are of equal length $L$ $[$bits$]$. Every cache-enabled user has cache of the
same size $M\times L$ $[$bits$]$, where $M\ll N$. The request interarrival
times of a user are exponentially distributed random variables with mean
$\frac{1}{\lambda_{u}}$ seconds [17], i.e., requests of a single user is a
Poisson process with parameter $\lambda_{u}$ $[$requests/s$]$. The requested
probability of the $i$-th content is triggered according to the Zipf
distribution [4, 12] as follow

$f_{i}={\frac{1/i^{\nu}}{\sum_{j=1}^{N}1/j^{\nu}}},$ (1)

where $\nu\geq 0$ reflects the difference of the access frequency to different
contents. Large $\nu$ implies that the access to a few of popular contents
accounts for the majority of the total access traffic. The content with lower
ranking (larger $i$) is more rarely accessed by users.

Figure 1: The cognitive and cache-enabled D2D transmission.

###  II-B Tier Association Protocol

When the networks is off-peak, e.g., in the nighttime, BSs proactively
broadcast the most popular contents to the cache-enabled users. All the cache-
enabled users pre-cached the same copy of the pushed contents, i.e. the $M$
most popular contents. The tier association protocol is jointly decided by the
following physical layer and the content-centric features.

####  II-B1 Physical layer features

We consider the node providing the highest long-term average received signal
strength to a requesting user as the “closest” node of the user. And the
received signal strength is [16],

$T_{i}=\kappa B_{i}P_{i}r_{i}^{-\beta},~{}\text{for}~{}i=1,2,$ (2)

Where $\beta\geq 2$ is the path-loss exponent and $r_{i}$ denotes the distance
between the requesting user and its nearest node in the $i$-th tier. $P_{i}$
for $i=1,2$ are the transmit power of a D2D TX and a BS, respectively. For
clarity, both the association bias factor $B_{i}$ and the propagation constant
$\kappa$ are normalized as $1$ in this paper. So the “closest” node is
$\arg\max_{i}T_{i}$.

####  II-B2 Content-centric features

If a request is triggered by a user who is not cache-enabled, the user
associates to its “closest” node111Note that when its “closest” node is a D2D
TX, if the D2D TX has cached the requested content, then a _cache-hit_ event
happens and the user obtains the content via the D2D TX; otherwise, the
_cache-loss_ event happens because all the other D2D TXs have not cached the
requested content either, and the user has to skip over D2D TXs to associate
to the BS tier.. If the requesting user is cache-enabled but has not cached
the requested content, the user accesses to its “closest” BS. If the
requesting user is cache-enabled and the requested content has been cached in
its local caching storage, the user obtains the content immediately.

Therefore, in a snapshot of the network, requesting users can be clarified
into the following three non-overlapping Subsets according to where (its local
caching, the D2D TX or the BS) it obtains the requested content.

Subset 0: The user who can obtain the requested content from its local caching
immediately.

Subset 1: The user who can obtain the requested content from the D2D TXs. It
implies that the requested content has been cached in the user’s “closest” D2D
TXs.

Subset 2: The user who can obtain the requested content from the BS. It
includes two possible cases, the first case is that the BS is the “closest”
server of the user. The other case is that the user is not cache-enabled, and
its “closest” server is a D2D TX who yet has not cached the requested content
(which means the requested content has not cached in the D2D tier). Then the
user has to access the “closest” BS.

The cellular network without caching is considered as a baseline in this
paper. In the baseline, users do not have caching ability and they could not
pre-cache the popular contents. The local sharing links via D2D communications
among users can not work at this time. All the users need to access the BS for
the content.

###  II-C Priority Based Cognitive Channel Access

A set of orthogonal channels $C=\\{c_{i},i=1,2,...,|C|\\}$ are available in
the downlink. Different BSs can reuse all the channels and no channel is
reused within the same cell. Time is divided into slots with fixed-length
interval $\tau$ for the BS and D2D TXs to sent contents, we consider $\tau=1$
second for analytical tractability. A BS assigns one channel to every received
request at the beginning of each time slot. The requests that arrive to the BS
in the middle of a time slot will be assigned channels until the next time
slot. Each BS assigns channels to received requests from $c_{1}$ to $c_{|C|}$
in sequence, i.e., channel $c_{i+1}$ will not be assigned before channel
$c_{i}$.

Figure 2: Time allocation of a slot for the D2D sensing and transmission.

The cache-enabled users take the free channels which are not used by the
nearby BSs and the nearby cache-enabled users, to share the local cached
contents to the requesting users via D2D. Cache-enabled users are cognitive
and access the available channels around them opportunistically [1, 3, 6, 7].
A channel is available to a cache-enabled user if and only if its received
power on this channel, whether provided by a BS node or a cache-enabled user,
is less than the spectrum sensing threshold $\gamma$. For a specific cache-
enabled user, the spectrum sensing threshold determines its SSR, in which the
received power from any other transmit node is larger than $\gamma$, yielding
the non-reusable of the corresponding channel. The larger the value of the
spectrum sensing threshold $\gamma$, the smaller the SSR area, and vice versa.
Because the transmit power of the BS is larger than that of the D2D TX, the
average radius of the SSR for BSs are larger than that for D2D TXs as in Fig.
1 (we shall note that the instantaneous SSRs are random shapes because of the
channel fading). Then each cache-enabled user serves its received requests
according to the following Steps in a slot as illustrated in Fig. 2 [9]:

Step 1: The cache-enabled user senses the spectrum during the sensing time
${\tau}_{s}\ll\tau$ and determines the free channels not used by the BSs
within its SSR with regard to BSs (called BS SSR in the following);

Step 2: Select a number of channels from the available channels sensed in Step
1. Persistently sense each of them for a random duration $t$ uniformly
distributed in the region $[0,\tau_{c}]$, where $\tau_{c}\ll\tau$. If there is
still any channel available after the sensing duration (i.e., no nearby cache-
enabled user accesses the channel during $t\in[0,\tau_{c}]$ ), go to Step 3;
otherwise, delay the content transmission to the next time slot.

Step 3: During the interval $\tau_{l}$, D2D TXs access the available channels
for D2D transmission to the firstly unresponded requests. Note that the D2D TX
and receiver can perform direct communications over the PC5 interface defined
by the LTE standard, bypassing the supervision of the BS [1, 7].

We consider perfect spectrum sensing and the same spectrum access procedure is
repeated in each time slot [9]. For a cache-enabled user, how many channels it
tries to occupy depends on the number of received requests it has to respond
in this time slot. These requests include the newly received ones in the
duration of the last time slot, and the ones which are received in more
previous slots but have not been responded due to the shortage of available
channels.

##  III PROBLEM FORMULATION AND ANALYSIS

In this section, we will derive the tier association probabilities for a
typical user. Then the number of users associated to each BS are analyzed. The
delay and the queue length at the BS and the D2D TX are further evaluated with
the modeling of the _discrete-time multiserver queue with priorities_.

###  III-A Tier association probability

We have modeled a two-tier network above, where the cellular network is
overlaid with D2D tier. The probability that the average received signal
strength from the $i$-th tier of a user is higher than that from the $j$-th
tier is [16, 18]

$\displaystyle\mathrm{\mathbb{P}(T_{i}>T_{j})}=\left[{\sum\limits_{k=1}^{2}\frac{\lambda_{k}}{\lambda_{i}}\left(\frac{P_{k}}{P_{i}}\right)^{\frac{2}{\beta}}}\right]^{-1},i\neq
j\in\\{1,2\\}.$ (3)

For a randomly selected requesting user, which Subset it belongs to is jointly
decided by the physical layer and content-centric features. In a specific time
slot, the portions $\mathbb{P}_{ui}$ for the requesting users in the
corresponding Subsets are [18]

$\left\\{\begin{array}[]{ll}\mathbb{P}_{u0}=\alpha\mathbb{P}_{h}\\\
\mathbb{P}_{u1}=(1-\alpha)\mathbb{P}_{h}\mathbb{P}(T_{1}>T_{2})\\\
\mathbb{P}_{u2}=(1-\mathbb{P}_{h})+(1-\alpha)\mathbb{P}_{h}[1-\mathbb{P}(T_{1}>T_{2})],\end{array}\right.$
(4)

where $\mathbb{P}_{h}=\sum_{i=1}^{M}f_{i}$ is the probability that the _cache-
hit_ event happens, i.e., the requested content has been cached in the caching
storage. $\mathbb{P}_{ui}$ for $i=0,1,2$ also can be viewed as the probability
that a randomly selected requesting user can obtain its requested content from
its local caching, the D2D TX and the BS, respectively.

###  III-B The Number of Users Associated to each BS

As explained above, we have divided users into three non-overlapping Subsets
in each time slot. With marking users based on which Subset they belong to, we
approximately get three independently thinning PPPs $\Phi_{ui}$ with intensity
$\lambda_{ui}=\mathbb{P}_{ui}\lambda_{0}$ for $i=0,1,2$ in the
$\mathbb{R}^{2}$ plane [9]. That is, the locations of users who obtain their
requested contents from local caching, D2D TXs and BSs in each slot are
spatially distributed according to mutually independent PPPs with intensity
$\lambda_{ui}$ for $i=0,1,2,$ respectively.

Therefore, the number of users associated to a BS can be formulated within the
homogeneous BS tier, where the BS cells are polygonal and form the Voronoi
tessellation in $\mathbb{R}^{2}$. The size of the Voronoi cell area is a
random variable, and its probability density function (PDF) can be accurately
predicted by the gamma distribution [9]

$f_{S}(s)=\frac{(\lambda_{2}K)^{K}s^{K-1}e^{-\lambda_{2}Ks}}{\Gamma(K)},0\leq
s<\infty,$ (5)

where $s$ denotes the cell size and $\Gamma(\cdot)$ is the gamma function. And
$K=3.575$ is a constant factor. Then with the property of the PPP, the number
of users $N_{2}$ in a BS cell conditioning on the cell size is a Poisson
random variable, which can be generated with the conditioned PMF

$\mathbb{P}\left(\begin{array}[]{c|}\\!\\!\\!N_{2}=n\\!\end{array}~{}S=s\right)\\!=\\!\frac{(\lambda_{u2}s)^{n}\text{exp}\\{\\!-\\!\lambda_{u2}s\\}}{n!},n=1,2,...,$
(6)

we then have the following lemma [9].

###### Lemma 1

The PMF of the number of users associated to a BS is

$\displaystyle\mathbb{P}(N_{2}=n)=\frac{\lambda_{u2}^{n}(K\lambda_{2})^{K}}{(\lambda_{u2}+K\lambda_{2})^{K+n}}\frac{\Gamma(K+n)}{\Gamma(n+1)\Gamma(K)}.$
(7)

###### Proof:

By considering (5) and (6), we have
$\mathbb{P}(N_{2}=n)=\int_{0}^{\infty}\mathbb{P}\left(\begin{array}[]{c|}N_{2}=n\end{array}~{}S=s\right)f_{S}(s)\mathrm{d}{s}$,
we obtain the lemma. ∎

###  III-C Number of BSs and D2D TXs in the SSR

The spectrum sensing threshold $\gamma$ defines the SSR around a reference D2D
TX in the two-tier heterogeneous network (the D2D tier and the BS tier). In
the SSR of a reference D2D TX, the number of D2D TXs (the reference TX is not
included) and BSs $N_{\gamma i},i=1,2$ can be described as

$N_{{\gamma}i}=\sum_{b_{i,j}\in\Phi_{i}}\mathbf{1}\left\\{P_{i}h_{i,j}r_{i,j}^{-\beta}>\gamma\right\\},$
(8)

where $r_{i,j}$ is the distance from the node $b_{i,j}\in\Phi_{i}$ for $i=1,2$
to the reference D2D TX. We consider Rayleigh fading channels. The channel
gains from the $j$-th node in the $i$-th tier to the reference D2D TX are
$h_{i,j}\sim\text{Exp}(\mu)$, and they are independent with each other. We
then have the following lemma [9].

###### Lemma 2

The number of D2D TXs and BSs $N_{\gamma i}$ ($i=1,2$) in the SSR of the
reference D2D TX follow the Poisson distribution with intensity
$\lambda_{\gamma
i}=\pi\lambda_{i}(\frac{P_{i}}{\gamma\mu})^{\frac{2}{\beta}}\Gamma(1+\frac{2}{\beta})$,
respectively.

###### Proof:

The moment generation function (MGF) of $N_{\gamma i}$ is

$\displaystyle\mathbb{E}(e^{tN_{{\gamma}i}})$
$\displaystyle=\mathbb{E}\Big{(}e^{t\sum_{b_{i,j}\in\Phi_{i}}\mathbf{1}\left\\{P_{i}h_{i,j}r_{j}^{-\beta}>\gamma\right\\}}\Big{)}$
$\displaystyle=\mathbb{E}_{\Phi_{i}}\Big{[}\prod\nolimits_{b_{i,j}\in\Phi_{i}}\mathbb{E}_{h_{i,j}}e^{t\mathbf{1}\left\\{P_{i}h_{i,j}r_{j}^{-\beta}>\gamma\right\\}}\Big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\text{exp}\Big{\\{}-\mathbb{E}_{h_{i,j}}\\!\Big{[}\\!\int_{0}^{2\pi}\\!\\!\\!\\!\int_{0}^{\left(\frac{P_{i}h_{i,j}}{\gamma}\right)^{\frac{1}{\beta}}}\\!\\!\\!\\!\\!(1-e^{t})\lambda_{i}r\mathrm{d}{r}\mathrm{d}{\theta}\Big{]}\\!\Big{\\}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\text{exp}\Big{\\{}-\pi(1-e^{t})\lambda_{i}\mathbb{E}_{h_{i,j}}\Big{[}{\Big{(}\frac{P_{i}h_{i,j}}{\gamma}\Big{)}^{\frac{2}{\beta}}}\Big{]}\Big{\\}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\text{exp}\Big{\\{}-\pi(1-e^{t})\lambda_{i}\Big{(}\frac{P_{i}}{\gamma\mu}\Big{)}^{\frac{2}{\beta}}\Gamma(1+\frac{2}{\beta})\Big{\\}},$
(9)

where Step (a) has been proven in [19, 9]. Step (b) is obtained by noting that
$h_{i,j}\sim\text{Exp}(\mu)$. Step (c) is obtained based on

$\displaystyle\mathbb{E}_{h_{i,j}}\Big{[}{\Big{(}\frac{P_{i}h_{i,j}}{\gamma}\Big{)}^{\frac{2}{\beta}}}\Big{]}$
$\displaystyle=\int_{0}^{+\infty}\mu e^{-\mu
x}\Big{(}\frac{P_{i}x}{\gamma}\Big{)}^{\frac{2}{\beta}}\mathrm{d}{x}$
$\displaystyle=\Big{(}\frac{P_{i}}{\gamma\mu}\Big{)}^{\frac{2}{\beta}}\Gamma\Big{(}1+\frac{2}{\beta}\Big{)}.$
(10)

Compared (III-C) with the MGF of the Poisson distribution, we can find that
$N_{\gamma i}$ is distributed according to Poisson process with intensity
$\lambda_{\gamma
i}=\pi\lambda_{i}(\frac{P_{i}}{\gamma\mu})^{\frac{2}{\beta}}\Gamma(1+\frac{2}{\beta})$.
∎

###  III-D The Delay and the Queue Length

In this part, we analyze the queue length of requests at the BS and the D2D
TX, as well as the delay of users in different Subsets. Requests that arrive
at the same node (a BS or a D2D TX) are queued in a infinite buffer until they
can be served, and they are served on a FIFO-basis (first-in, first-out).
Consider the strategy that a request will be deleted from the buffer no matter
whether the corresponding content has been transmitted completely in a slot
scheduled to it (at the cost of increasing the content loss rate), i.e.,
without repeat transmission.

####  III-D1 The delay and the queue length at the BS

As to any given BS node, the arrival of received requests follows a Poisson
process with intensity $n_{2}\lambda_{u}$, conditioned on the number
$N_{2}=n_{2}$ of associated users. Note that the BS have the priority to
assigning channels to its received requests at the beginning of each time
slot, which is not affected by the state of any D2D TX. The queueing behavior
of BSs with high priority is not affected by the presence of D2D TXs with low
priority. Then traffic dynamics of request arrivals and departures at a BS is
a _discrete-time multiserver queue_ (with $|C|$ servers). Substituting the
Poisson arriving process into the result of the reference [20], we get the
conditional probability generating function (PGF) of the queue length at the
BS (note that the conditional PGF here is for the BS such that the queue at
the BS is steady, i.e., $n_{2}\lambda_{u}<|C|$),

$\displaystyle\mathcal{L}_{b}(z|N_{2}=n_{2})$
$\displaystyle=\frac{e^{n_{2}\lambda_{u}(z-1)}(|C|-n_{2}\lambda_{u})(z-1)}{z^{|C|}-e^{n_{2}\lambda_{u}(z-1)}}$
$\displaystyle\times\prod_{i=1}^{|C|-1}\frac{z-\beta_{i}}{1-\beta_{i}},$ (11)

where the $\beta_{i}$ ($i=1,2,...,|C|-1)$ are the $|C|-1$ solutions of
$z^{|C|}=e^{n_{2}\lambda_{u}(z-1)}$ inside the complex unit disk minus the
point $z=1$. We refer readers to [20] for detail derivations. Then the
conditional PMF of the queue length $L_{b}$ at the BS can be given with
different methods, e.g., the inverse discrete Fourier transform (IDFT) method
[20],
$\mathbb{P}\left(L_{b}=n|N_{2}=n_{2}\right)\approx\frac{1}{W}\sum\limits_{w=0}^{W-1}\frac{\mathcal{L}_{b}\left(e^{j2\pi
w/W}|N_{2}=n_{2}\right)}{e^{j2\pi wn/W}}.$ This method will yield more
accurate approximations for the PMF when choosing larger $W$. Therefore, the
PMF of the queue length $L_{b}$ at the BS is

$\displaystyle\mathbb{P}(L_{b}=n)=\sum\limits_{n_{2}=0}^{\lceil{\frac{|C|}{\lambda_{u}}}\rceil-1}\mathbb{P}(L_{b}=n|N_{2}=n_{2})\mathbb{P}(N_{2}=n_{2}),$
(12)

where $\lceil x\rceil$ is the the ceiling function. Similarly, the conditional
PGF of the delay in the queue at a BS is given by
$\mathcal{D}_{b}(z|N_{2}=n_{2})=\sum_{k=0}^{|C|-1}\frac{(v_{k}^{|C|}(z)-1)v_{k}(z)}{|C|\cdot(v_{k}(z)-1)}\times\frac{(|C|-n_{2}\lambda_{u})(e^{n_{2}\lambda_{u}(v_{k}(z)-1)}-1)}{n_{2}\lambda_{u}(v_{k}^{|C|}(z)-e^{n_{2}\lambda_{u}(v_{k}(z)-1)})}\prod_{i=1}^{|C|-1}\frac{v_{k}(z)-\beta_{i}}{1-\beta_{i}},$
whereby $v_{k}(z)$ are the $|C|$ different solutions of $v^{|C|}=z$. Then the
PMF of the delay $\mathbb{P}(D_{b}=n)$ can be further obtained.

####  III-D2 The delay and the queue length at the D2D TX

Due to the large gap between the transmit power of BSs and D2D TXs, the area
of the D2D SSR is much smaller than that of the BS SSR. It is reasonable to
assume that all D2D TXs coexisting within one D2D SSR share the same BS SSR
and the same free channels for tractable analysis [9]. Regard a D2D TX and the
other D2D TXs in its D2D SSR as a group, the free channels in the D2D SSR are
shared by the group orthogonally. According to the analysis in Sec. III-C, we
can get the number of users associated to the group of D2D TXs follows the
Poisson distribution with intensity $\lambda_{\gamma
u}=\pi\mathbb{P}_{u1}\lambda_{0}(\frac{P_{1}}{\gamma\mu})^{\frac{2}{\beta}}\Gamma(1+\frac{2}{\beta})$.
Then the PMF $\mathbb{P}(N_{\gamma u}=n)$ of the number of users associated to
the group of D2D TXs can be obtained.

For the priority of the BSs, the number of free channels available for the D2D
group is the number of channels that are not used by the BS with most received
requests to be responded to in the D2D SSR. As to each BS, the requests it
received during each time slot follows a Poisson process as aforementioned. We
consider the BS with most users associated with it to be the one that occupies
most channels. Denote $N_{2}^{j}$ as the number of users associated with the
$j$-th BS. The conditional CDF of the number of users under the BS with the
heaviest load is $N_{K}$

$\displaystyle\mathbb{P}({N_{K}\leq k|N_{\gamma 2}=n})$
$\displaystyle=\mathbb{P}\Big{(}{\max_{j=1,2,...,n}N_{2}^{j}\leq k}\Big{)}$
$\displaystyle=\Big{[}\sum_{i=0}^{k}\mathbb{P}(N_{2}=i)\Big{]}^{n}.$ (13)

Then the CDF of the number of users under the BS with the heaviest load is

$\displaystyle\mathbb{P}({N_{K}\leq k})$
$\displaystyle=\sum_{n=0}^{+\infty}\mathbb{P}({N_{\gamma
2}=n})\mathbb{P}({N_{K}\leq k|N_{\gamma 2}=n}).$ (14)

Then the system can be regarded as a two-priority queuing system with $|C|$
servers, i.e., a _discrete-time multiserver queue with priorities_ [21]. The
requests with high-priority (associated to the BS with the heaviest load)
arrive according to a Poisson process with intensity
$\lambda_{H}=N_{K}\lambda_{u}$. The arrival of requests with low-priority
(associated to the group of D2D TXs) follows a Poisson process with intensity
$\lambda_{L}=N_{\gamma_{u}}\lambda_{u}$. The two processes are independent to
each other, but the high-priority requests may lead to server interruptions to
the queueing of the low-priority requests.

We provide an insight into the performance of the D2D tier with the state of
the low-priority queueing. Substituting the Poisson process into results of
[21] which is with regard to a general arriving process, we get the
conditional PGF for the queue length of requests with low priority

$\displaystyle\mathcal{L}_{d}(z|N_{K},N_{\gamma u})$
$\displaystyle=\frac{e^{\lambda_{L}(z-1)}(|C|-\lambda_{T})(z-1)}{1-e^{\lambda_{L}(z-1)}}$
$\displaystyle\times\prod_{i=0}^{|C|-1}\frac{1-x_{i}(z)}{z-x_{i}(z)}\prod_{i=1}^{|C|-1}\frac{z-\alpha_{i}}{1-\alpha_{i}}.$
(15)

whereby the $\alpha_{i}$ ($i=1,2,...,|C|-1$) are the $|C|-1$ solutions of
$z^{|C|}=e^{\lambda_{T}(z-1)}$ inside the complex unit disk minus the point
$z=1$, and we have $\lambda_{T}=\lambda_{H}+\lambda_{L}$. The functions
$x_{i}(z)$ are the $|C|$ solutions for equation
$x_{i}^{|C|}(z)=e^{\lambda_{H}(x_{i}(z)-1)+\lambda_{L}(z-1)}$ for any given
$z$. Moreover, the conditional PGF of the delay for low-priority requests is
given by $\mathcal{D}_{d}(z|N_{K},N_{\gamma
u})=\sum_{i=0}^{|C|-1}r_{i}(z)Q_{T}(\omega_{i}(z)),$ where
$r_{i}(z|N_{K},N_{\gamma u})=z\prod_{j=0,j\neq
i}^{|C|-1}\frac{1-\omega_{j}(z)}{\omega_{i}(z)-\omega_{j}(z)},0\leq i<|C|,$
and $Q_{T}(z|N_{K},N_{\gamma
u})=\frac{(|C|-\lambda_{T})\left(e^{\lambda_{T}(z-1)}-e^{\lambda_{H}(z-1)}\right)}{\lambda_{L}\left(z^{|C|}-e^{\lambda_{T}(z-1)}\right)}\times\prod_{i=1}^{|C|-1}\frac{z-\alpha_{i}}{1-\alpha_{i}},$
and $\omega_{i}(z)$ are the solutions of
$\omega^{|C|}=ze^{\lambda_{H}(\omega-1)}$. Similarly, the PMF of the queue
length and the delay can be obtained with the IDFT method described above.

##  IV Numerical Results

We verify the performance of the proposed system with simulating the cache-
enabled network. The results are obtained with Monte Carlo methods in a square
area of $2000m\times 2000m$, where the locations of users and BSs are
independent homogeneous PPPs with intensities of
$\\{\lambda_{0},\lambda_{2}\\}=\\{\frac{100}{\pi 500^{2}},\frac{1}{\pi
500^{2}}\\}$ nodes/m2. We set the path-loss $\beta=4$, the transmit powers are
$\\{P_{0},P_{2}\\}=\\{23,43\\}$ dBm, the request intensity $\lambda_{u}=0.09$
[requests/s], the number of channels $|C|=10$, total number of contents
$N=200$, the caching ability $M=10$, and the content popularity $\gamma=1$.
These typical parameters will not change unless specific statements are
clarified.

Figure 3: Fig. 3: The fraction of the steady-state service nodes; Fig. 3: The
PMF of the request delay at the steady service nodes.

Fig. 3 shows the fraction of the steady-state service nodes (BSs or D2D TXs)
for the cognitive and cache-enabled network, in comparison with that of the
baseline. For a service node, the arrival rate of requests is decided by the
number of users in its cell. Due to the stochastic locations of both users and
service nodes, there is possibility that a service node has large number of
requests in its cell, yielding congestion. As shown in Fig. 3, nearly all
service nodes stay at the steady state with lower request intensity. As to the
heavy load situation, the fraction of the steady-state service nodes decreases
sharply for both the baseline and the proposed network. Moreover, in the
proposed network, D2D TXs are more likely to suffer from local unsteady state
because of the lower priority. However, both kinds of service nodes (BSs or
D2D TXs) in the proposed system can bear heavier traffic load than BSs in the
baseline. When the request rate is $0.1$ $[$requests/s$]$, the fraction of the
steady BSs and D2D TXs are, respectively, $33.3\%$ and $9\%$ higher than that
of the steady BSs in the baseline, which illustrates the appealing advantage
of the proposed network.

The PMF of the request delay at the steady service nodes (requests at the
steady BSs and the steady D2D TXs are considered as two kinds) are illustrated
in Fig. 3. The user under the coverage of steady BSs in the proposed network
has smaller delay compared with the D2D users and the users in the baseline.
Furthermore, the delay of users under steady D2D has the distribution with
longer tail and larger average than that under the steady BS due to the low
priority. However, both kinds of users under steady service nodes (BSs or D2D
TXs) in the proposed network have better performance than that under the
steady BSs in the baseline.

##  V Conclusion

The paper aims to formulate and evaluate the performance of the multi-channel
network where the D2D and cellular coexist. We advocate to pre-cache the most
popular contents to cache-enabled user via broadcasting when the network is
off-peak, for the future frequent access. A cognitive D2D TX senses the idle
cellular spectrum within its spectrum sensing region. Firstly, we model the
node locations as mutually independent PPPs. Users dynamically connect to the
cellular and the D2D according to the jointly physical layer and content-
centric features. Users are classified into three Subsets according to where
the user can obtain the requested content. Then the request arrivals and
departures at the BS and D2D TX are modeled as the _discrete-time multiserver
queue with priorities_. We further provide the PMF of the delay and the queue
length. Numerical results reveal that the fraction of the steady BSs in the
proposed system is $33.3\%$ higher than that in the baseline.

## References

  * [1] M. Khoshkholgh, Y. Zhang, K.-C. Chen, K. Shin, and S. Gjessing, “Connectivity of Cognitive Device-to-Device Communications Underlying Cellular Networks,” _IEEE J. Sel. Areas Commun._ , vol. 33, no. 1, pp. 81–99, Jan. 2015.
  * [2] A. H. Sakr, H. Tabassum, E. Hossain, and D. I. Kim, “Cognitive Spectrum Access in Device-to-Device-Enabled Cellular Networks,” _IEEE Commun. Mag._ , vol. 53, no. 7, pp. 126–133, July 2015.
  * [3] P. Phunchongharn, E. Hossain, and D. I. Kim, “Resource Allocation for Device-to-Device Communications Underlaying LTE-Advanced Networks,” _IEEE Wireless Commun._ , vol. 20, no. 4, pp. 91–100, Aug. 2013.
  * [4] M. Cha, H. Kwak, P. Rodriguez, Y. Ahn, and S. Moon, “I Tube, You Tube, Everybody Tubes: Analyzing The World’s Largest User Generated Content Video System,” in _Proc. ACM SIGCOMM Internet Measurement_ , Oct. 2007.
  * [5] H. Liu, Z. Chen, X. Tian, X. Wang, and M. Tao, “On content-centric wireless delivery networks,” _IEEE Wireless Commun._ , vol. 21, no. 6, pp. 118–125, Dec. 2014.
  * [6] H. Min, J. Lee, S. Park, and D. Hong, “Capacity Enhancement Using an Interference Limited Area for Device-to-Device Uplink Underlaying Cellular Networks,” _IEEE Trans. Wireless Commun._ , vol. 10, no. 12, pp. 3995–4000, Dec. 2011.
  * [7] A. H. Sakr, H. Tabassum, E. Hossain, and D. I. Kim, “Cognitive Spectrum Access in Device-to-Device-Enabled Cellular Networks,” _IEEE Commun. Mag._ , vol. 53, no. 7, pp. 126–133, July 2015.
  * [8] A. Sakr and E. Hossain, “Cognitive and Energy Harvesting-Based D2D Communication in Cellular Networks: Stochastic Geometry Modeling and Analysis,” _IEEE Trans. Commun._ , vol. 63, no. 5, pp. 1867–1880, May 2015\.
  * [9] H. ElSawy and E. Hossain, “Two-Tier HetNets with Cognitive Femtocells: Downlink Performance Modeling and Analysis in a Multichannel Environment,” _IEEE Trans. Mobile Computing_ , vol. 13, no. 3, pp. 649–663, Mar. 2014.
  * [10] H. Kebriaei, B. Maham, and D. Niyato, “Double sided bandwidth-auction game for cognitive device-to-device communication in cellular networks,” _IEEE Trans. Veh. Technol._ , vol. PP, no. 99, pp. 1–1, 2015.
  * [11] E. Baştuğ, M. Bennis, and M. Debbah, “Living on the Edge: The Role of Proactive Caching in 5G Wireless Networks,” _IEEE Commun. Mag._ , vol. 52, no. 8, pp. 82–89, Aug. 2014.
  * [12] N. Golrezaei, A. Dimakis, and A. Molisch, “Scaling Behavior for Device-to-Device Communications With Distributed Caching,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 7, pp. 4286–4298, July 2014.
  * [13] N. Golrezaei, P. Mansourifard, A. Molisch, and A. Dimakis, “Base-Station Assisted Device-to-Device Communications for High-Throughput Wireless Video Networks,” _IEEE Trans. Wireless Commun._ , vol. 13, no. 7, July 2014.
  * [14] M. Afshang, H. S. Dhillon, and P. H. J. Chong, “Fundamentals of Cluster-Centric Content Placement in Cache-Enabled Device-to-Device Networks,” _[online] http://arxiv.org/abs/1509.04747_ , Sept. 2015.
  * [15] A. Altieri, P. Piantanida, L. R. Vega, and C. Galarza, “On Fundamental Trade-offs of Device-to-Device Communications in Large Wireless Networks,” _IEEE Trans. Wireless Commun._ , vol. PP, no. 99, pp. 1–1, May 2015.
  * [16] J. Andrews, F. Baccelli, and R. Ganti, “A Tractable Approach to Coverage and Rate in Cellular Networks,” _IEEE Trans. Commun._ , vol. 59, no. 11, pp. 3122–3134, Nov. 2011.
  * [17] M. Karray and M. Jovanovic, “A Queueing Theoretic Approach to the Dimensioning of Wireless Cellular Networks Serving Variable-Bit-Rate Calls,” _IEEE Trans. Veh. Technol._ , vol. 62, no. 6, pp. 2713–2723, July 2013.
  * [18] C. Yang, Y. Yao, Z. Chen, and B. Xia, “Analysis on Cache-enabled Wireless Heterogeneous Networks,” _IEEE Trans. Wireless Commun._ , vol. 15, no. 1, pp. 131–145, Jan. 2016.
  * [19] M. Haenggi and R. K. Ganti, _Interference in Large Wireless Networks_. Now Publishers Inc, 2009.
  * [20] H. Bruneel and B. G. Kim, _Discrete-time Models for Communication Systems Including ATM_. Springer Science & Business Media, 2012, vol. 205.
  * [21] K. Laevens and H. Bruneel, “Discrete-time Multiserver Queues with Priorities,” _Performance Evaluation_ , vol. 33, no. 4, pp. 249–275, 1998\.


# Studying links via plats: split and composite links

William W. Menasco and Deepisha Solanki

###### Abstract

Our main results concern changing an arbitrary plat presentation of a split or
composite link to one which is obviously recognizable as being split or
composite. Pocket moves, first described in [5], are utilized—a pocket move
alters a plat presentation without changing its link type, its bridge index or
the double coset. A plat presentation of a split link is split if the planar
projection of the plat presentation is not connected. We prove that pocket
moves are the only obstruction to representing split links by split plat
presentations. Since any pocket move corresponds to a sequence of double coset
moves, we have the corollary that the double coset of every plat presentation
of a split link has a split plat presentation. We obtain an analogous result
for composite links by utilizing flip moves, which were also first described
in [5].

##  1 Introduction

This paper builds on the ideas and singular foliation technology first
introduced in [5]. In that paper, non-oriented links in $\mathbb{R}^{3}$ were
studied using plat presentations. Specifically, the pocket move and the flip
move on plat presentations of non-oriented links were introduced. Both moves
are isotopies that preserve the bridge index of the presentations. For pocket
moves it was shown that they correspond to a sequence of moves in the double
coset. Flip moves were shown to be equivalent to a precisely depicted sequence
of stabilizations, double coset moves, destabilizations.

We established the following notation. $\mathcal{L}$ will be a non-oriented
link type in $\mathbb{R}^{3}$ and $L\subset\mathbb{R}^{3}$ will be an
arbitrary representative of $\mathcal{L}$.

Let $L\subset\mathbb{R}^{3}$ be a representation of $\mathcal{L}$.
$\mathcal{L}$ is split if there exists a $2$-sphere,
$S\subset\mathbb{R}^{3}\setminus L$, such that $S$ does not bound either a
$3$-ball or $\mathbb{R}^{3}$ minus an open $3$-ball in
$\mathbb{R}^{3}\setminus L$. $\mathcal{L}$ is composite if there exists a
$2$-sphere, $S_{p}\subset\mathbb{R}^{3}$, twice punctured by $L$ such that
neither component of $\mathbb{R}^{3}\setminus S_{p}$ intersects $L$ in a
single unknotted arc.

As in [5], we will be focusing on representatives $L$ of $\mathcal{L}$ that
are $n$-bridge plat presentations. (The reader should see [2] for an
introduction to plat presentations.) Although our arguments will be mostly
geometric it is convenient to utilize the algebra coming from braids to
describe the associated $2n$-braid (on $2n$ strands) in terms of the classical
Artin generators, $\\{\sigma_{i}\ |\ 1\leq i\leq 2n-1\\}$. For a plat
presentation, $L$, we will use the notation, $W(L)$, for the associated braid
word, written in terms of the $\sigma_{i}\text{'s}$.

A plat presentation, $L$, is split if $W(L)$ is missing a $\sigma_{2i}$ for
$1\leq i<n$. For such a braid word one can readily see the associated
splitting $2$-sphere in a regular planar diagram of the plat, $L$—such a
sphere will intersect the plane containing the diagram in a circle that splits
the diagram.

A plat presentation, $L$, is composite if $W(L)$ is missing a $\sigma_{2i+1}$,
$1\leq i<n-1$. For such a braid word one can readily see a composing sphere
that intersects the regular planar diagram of $L$ in a circle that intersects
the diagram twice, once at a “top” and once at a “bottom” bridge.

The generic situation is that the $2$-sphere illustrating that a link type is
split or composite is “obscured” for an arbitrary plat presentation. It is
through the uses of pocket and flip moves that we can take such an obscured
$2$-sphere and make it readily observable as it would be if the plat
presentation was split or composite. Specifically, we have the following main
theorems:

######  Theorem 1.

Let $\mathcal{L}$ be a split link type. Let $L$ be an $n$-bridge plat
presentation of $\mathcal{L}$. Then, there exists a finite sequence of plat
presentations of $\mathcal{L}$:

$L=L_{0}\longrightarrow L_{1}\longrightarrow
L_{2}\longrightarrow\cdots\longrightarrow L_{k}$

such that $L_{k}$ is split and $L_{i+1}$ is obtained from $L_{i}$ via the
following constant bridge index moves:

  * (i)

a braid isotopy on the 2n strands;

  * (ii)

the pocket move.

  * (iii)

double coset moves.

######  Theorem 2.

Let $\mathcal{L}$ be a composite link. Let $L$ be an $n$-bridge plat
presentation of $\mathcal{L}$. Then, there exists a finite sequence of plat
presentations of $\mathcal{L}$:

$L=L_{0}\longrightarrow L_{1}\longrightarrow
L_{2}\longrightarrow\cdots\longrightarrow L_{k}$

such that $L_{k}$ is a composite plat and $L_{i+1}$ is obtained from $L_{i}$
via the following constant bridge index moves:

  * (i)

a braid isotopy on the 2n strands;

  * (ii)

the pocket move;

  * (iii)

the flip move;

  * (iv)

double coset moves

For an $n$-bridge plat presentation $L$ of the non-oriented link type
$\mathcal{L}$ we use $\mathbf{DC}(L)$ to denote the collection of all
$n$-bridge plat presentations in the same double coset as $L$. We then have
the following corollary to Theorem 1:

######  Corollary 3.

For every plat presentation $L$ of a split link, there exists a plat
presentation $L^{\prime}\subset\mathbf{DC}(L)$ such that $L^{\prime}$ is a
split plat presentation.

The corollary follows from Theorem 1 and Lemma 3 of [5] that pocket moves can
be realized as a sequence of double coset moves.

###  1.1 Idea of proof

Our strategy for establishing Theorems 1 and 2 is inspired by the singular
foliation technology coming from the Birman-Menasco papers. There they
considered an appropriate essential surface in the complement of the closed
braid and studied the singular foliation induced by the braid fibration.

In our setting we start with pairs ${(S,L)}$-splitting sphere and plat
presentations of the split link and ${(S_{p},K)}$-twice punctured sphere and
plat presentations of the composite knot. We then consider the singular
foliation induced on $S$, $S_{p}$ coming from the plat height function. The
singular foliation technology used for proving Theorems 1 and 2 will have the
following salient components:

(i) A system of level curves corresponding to the regular values of the height
function (See §2.1)
(ii) Generic singular leaves corresponding to the critical values of the
height function. The foliated neighborhood of each singular leaf will form a
singular tile. These tiles will give a decomposition of $S$ and $S_{p}$. (See
§2.4)
(iii) The tiling decomposition of $S$ or $S_{p}$ will imply an Euler
characteristic equation (See Lemma 6), this equation is used to obtain a
combinatorial relation between different types of tiles. (See Lemmas 7 and 8)
(iv) The tiling of $S$ or $S_{p}$ will be “dual” to a finite graph that allows
us to define a complexity measure on the tiling. (See §2.5)
(v) The local geometric realization of certain tiling patterns will imply the
plat admits a pocket move or a flip move. Applying a pocket move, flip move or
destabilisation will strictly reduce the complexity measure.

In §2.4, we describe the tiles associated with the foliation, each tile type
will contain a single singularity, or in the case of $S_{p}$, a single
singularity or puncture.

This gives an obvious complexity measure on the pairs ${(S,L)}$,
${(S_{p},K)}$, counting the number of singularities of certain types. This is
rigorously defined in §2.5.

In §2.4, we explain how the “configuration” in the singular foliation
corresponds to the plat moves and results in §3 detail how plat moves remove
these singularities, thus reducing the complexity measure on $S$ or $S_{p}$.

###  1.2 Contrasting Plats with Closed Braids

Plats and closed braids are both objects relating braids to links, and, at
first glance, appear very similar. But there are indeed considerable
differences between these two, which we elucidate below:

  * •

Non-oriented vs Oriented Links: The definition of closed braids refers to the
winding around of the link around the braid axis, thus inherently lending the
link an orientation. Therefore, closed braids are a tool to study oriented
link types. On the other hand, plats have no natural axis, and thus no
restriction to being oriented. Thus, plats are a tool to study non-oriented
link types.

  * •

Bridge number vs Braid index: Plats and closed braids offer us two different
complexity measures on links: bridge number and braid index. The bridge number
of a link type $\mathcal{L}$ is the smallest integer $n$ such that
$\mathcal{L}$ can be represented as a $2n$\- plat and, the braid index of a
link type $\mathcal{L}$ is the least number of strings required to express
$\mathcal{L}$ as a closed $n$\- braid. These two measures of complexity
inherently capture different types of information about a link. This can be
seen from the fact that the braid index of a link type $\mathcal{L}$ is equal
to the minimum number of Seifert circles of $\mathcal{L}$ and the bridge
number of $\mathcal{L}$ can alternatively defined to be the minimum numbers of
points of minima (or maxima) in any diagram of $\mathcal{L}$.

  * •

Double Coset Classes vs Conjugacy Classes: Every link can be expressed as both
a closed braid and a plat in infinitely many different ways, which leads to an
immediate question: How are any two braids representing the same link type as
closed braids (respectively plats) algebraically related to each other?
Markov’s theorem ([1], [3]) answers this question in the case of closed braids
and Birman’s result about Stable Equivalence of Plats ([2]) answers this in
the case of plats. Consider the partition of $\mathcal{B}_{n}$ into conjugacy
classes: $\mathcal{B}_{n}=\bigcup\limits_{\alpha}\mathcal{C}_{\alpha}$. Then,
each conjugacy class $\mathcal{C}_{\alpha}$ corresponds to the same knot type,
but this correspondence is not one-to-one. To delve into the case of plats, we
need to introduce the Hilden subgroup $\mathcal{K}_{2n}$ ([4]) of
$\mathcal{B}_{2n}$. $\mathcal{K}_{2n}$ consists of all those braids which can
be concatenated before or after a braid without changing its link type as a
plat i.e. the plat given by the braids $b_{1}bb_{2}$ and $b$ correspond to the
same knot type where $b_{1},b_{2}\in\mathcal{K}_{2n}$. Thus,
$\mathcal{B}_{2n}$ is partitioned into double cosets modulo $\mathcal{K}_{2n}$
on both sides
($\mathcal{B}_{2n}=\bigcup_{b\in\mathcal{B}_{2n}}\mathcal{K}_{2n}b\mathcal{K}_{2n}$)
such that each double coset corresponds to the same knot type, and again, this
correspondence is not one-to-one.

###  1.3 Outline of the paper

In §2, we introduce the basic terminology and set up the required machinery.
§2 begins with a description of the system of level curves in §2.1. This is
followed by an explanation of moves on plats in §2.2. Then, we have a detailed
description of the different types of singularities that occur on $S$ and
$S_{p}$ (with respect to the plat height function), and how that set up is
used to foliate the sphere and construct a tiling of it, in §2.4. §2 concludes
with an introduction to the graph corresponding to a sphere foliation and how
that is used to define a complexity function on the sphere, in §2.5.

Moving on to the next section, §3 consists of seven lemmas leading up to the
proof of Theorems 1 and 2. Lemma 6 gives the relation between the Euler
characteristics of a surface $X$ and subsurfaces $X_{i}$’s such that the
$X_{i}$’s are glued together to give $X$. We use this formula to obtain a
combinatorial relation between different types of tiles in Lemma 7, pertaining
to $S$ and Lemma 8, which pertains to $S_{p}$. Lemma 7 is crucial in helping
us understand the constraints on how different singularities on $S$ and
$S_{p}$ can grow with respect to each other. It also helps us identify some
key characteristics of the graph associated with the foliation of the spheres.
This leads us to Lemma 9 which tells us how to start eliminating singularities
from the spheres, using the language of graph theory. In particular, in Lemma
9, we give conditions that a vertex in the graph needs to satisfy so that the
singularity it represents can be removed using one of the moves in Theorems 1
or 2, depending on the context, giving us a plat with a strictly smaller value
of the complexity function. In Lemma 10, we prove that a vertex satisfying
conditions of Lemma 9 always exists, if there are any singularities of a
certain type on the sphere.

The rest of §3 is dedicated to proving the statement of Theorem 1. §3
concludes with Lemma 11, which pertains only to $S_{p}$. It describes how to
deal with the special tile $T_{p}$ (containing a puncture) in different
scenarios.

## Acknowledgements

The authors would like to thank Seth Hovland, Greg Vinal and Hong Chang for
their many discussions on plat presentations.

2pt $n$-bridges at 208 460 $n$-bridges at 205 22 B at 204 235 $2n$-strands at
450 298

Figure 1: A generic 2n-plat

##  2 Preliminaries

Starting with plat presentations for non-oriented links, we give a brief
description of what they are. Consider the classical braid group on $2n$
strands, $\mathcal{B}_{2n}$. Then, for an element of $\mathcal{B}_{2n}$ i.e. a
braid $B$ on $2n$ strands, we cap-off the $i$ and $i+1$ strands, for odd $i$
between $1$ and $2n-1$, at the top (bottom) of the braid with $n$ northern
(southern) circle hemispheres, refer Figure 1. This gives us a link, and this
presentation of the link is called a plat presentation. Call this the plat
defined by $B$. Then $n$ is the bridge index of the presentation. We thus have
a height function on the presentation that has $n$ maxima (minima) points all
at the same level above (below) the braid. (We will employ this height
function extensively in the arguments of this note). One can jump/isotope from
one plat presentation to another through braid isotopies, which again are
Reidemeister type-II & -III moves placed in this setting. Braid isotopies do
not change the bridge index. An isotopy by a stabilization (destabilization)
adds (removes) two strands in the braid along with a maxima and minima, which
is the Reidemeister type-I move placed in the plat setting. These isotopies
are shown in Figures 2, 3 and 4.

Birman showed in [2] that any link type can be represented as a plat. It turns
out that this representation is highly non unique and every link type has
infinitely many distinct plat presentations. By “distinct plat presentations”,
we mean that the braids corresponding to these plat presentations correspond
to different elements in the braid group. In the same paper, Birman proved the
following result, which tells us how any two braids, whose plats represent the
same knot type, are algebraically related to one another:

######  Birman’s Result.

Let $\mathbf{L_{i}}$, i =1, 2, be tame knots. Choose elements
$\phi_{i}\in\mathcal{B}_{2n_{i}}$ in such a way that the plat defined by
$\phi_{i}$ corresponds to the same knot type as $\mathbf{L_{i}}$. Then,
$\mathbf{L_{1}}\approx\mathbf{L_{2}}$ if and only if there exists an integer
$t\geq$ max$(n_{1},n_{2})$ such that, for each $n\geq t$, the elements

$\phi_{i}^{{}^{\prime}}=\phi_{i}\sigma_{2n_{i}}\sigma_{2n_{i}+2}...\sigma_{2n-2}\in\mathcal{B}_{2n},i=1,2$

are in the same double coset of $\mathcal{B}_{2n}$ modulo the subgroup
$\mathcal{K}_{2n}$.

Birman’s Result can be restated as follows:

######  Stable equivalence of plat presentations.

Let $K$ be a $2n$-plat presentation of $\mathbf{K}$, and $K^{\prime}$ be a
$2n^{\prime}$-plat presentation of $\mathbf{K}$. Then, there is a finite
sequence of plat presentations of $\mathbf{K}$:

$K=K_{0}\longrightarrow K_{1}\longrightarrow
K_{2}\longrightarrow...\longrightarrow K_{m}=K^{\prime}$

such that $K_{i+1}$ is obtained from $K_{i}$ via the following moves:

  * (i)

braid isotopies;

  * (ii)

double coset moves;

  * (iii)

stabilization or destabilization.

2pt R II at 59 108 R II at 307 108

Figure 2: Braid isotopy corresponding to Reidemeister II move

2pt R III at 125 110

Figure 3: Braid isotopy corresponding to Reidemeister III move

2pt $\mathbf{B}$ at 120 127 $\mathbf{B}$ at 428 127 $\sigma_{2n}$ at 529 26
STABILIZATION at 282 146 DESTABILIZATION at 282 100

Figure 4: Stabilizing and Destabilizing a Plat

Let $L_{i}$ be a plat presentation of $\mathcal{L}$, from the sequences in
Theorems 1 and 2, and let $S_{i}$ be a geometric realisation of $S$ or $S_{p}$
corresponding to $L_{i}$, depending on whether $L_{i}$ is split or composite.
We assign a height function $h$ to $S_{i}$ such that $h$ is a Morse function,
regarded as the projection function from $S_{i}$ onto $\mathbb{R}$ (think of
this as the natural height function
$h:\mathbb{R}^{3}\longrightarrow\mathbb{R}$. We position $S_{i}$ in
$\mathbb{R}^{3}$ so that $h$ takes values on $S_{i}$ varying between $-0.25$
and $1.25$ such that, the points of maxima of the top bridges are at height
$h=1$ and the points of minima of the bottom bridges are at height $h=0$. With
this setup, thinking of $\mathbb{R}^{3}$ as $\mathbb{R}^{2}\times\mathbb{R}$,
then $\mathbb{R}^{2}\times\\{*\\}$ are the level planes for $h$, say
$P_{t}=h^{-1}(t)=\mathbb{R}^{2}\times\\{t\\}$, for $t\in[-0.25,1.25]$.

###  2.1 System of Level Curves

Define $C_{t}^{i}:=S_{i}\cap P_{t}$. Then, $C_{t}^{i}$ is the set of level
curves of $S_{i}$ at level $t$, which is basically a cross section of $S$ or
$S_{p}$ at height $t$. Note that, if $L_{i}$ is a plat of index $n$, then, for
$t\in(0,1)$, $C_{t}^{i}$ consists of $m_{t}^{i}$ closed curves, say. Call
these closed curves $s_{i,t}^{j}$, for $j\in\\{1,2,...,m_{t}^{i}\\}$. We
position $S_{i}$ so that any points of local maxima or minima occur for
$t$-values not in $(0,1)$. Also notice that, for $t\in(0,1)$, the link/knot
intersects $P_{t}$ in exactly $2n$ points. If, for any $i,j,t$, $s_{i,t}^{j}$
does not contain a part of the link/knot or another curve inside of it (i.e.
$s_{i,t}^{j}$ is empty, which means that it does not contain points or other
curves), we surger it off. This means that, for any $i$ and any
$t\in[-0.25,1.25]$, the only closed curves that remain on $S_{i}$ are the ones
that contain a part of the link/knot or another simple closed curve. Further,
notice that, for all but finitely many values of $t$, the closed curves
$s_{i,t}^{j}$ are all simple closed curves. The values of $t$ for which we get
intersection (which includes self-intersection) between closed curves are the
values where the sphere $S_{i}$ has a saddle. We position the sphere so that
no value of $t$ has more than one saddle.

###  2.2 Moves on plats

####  2.2.1 Braid isotopies

Braid isotopies are moves on plats where the top and bottom bridges (i.e. the
local max’s and min’s) are fixed. Algebraically, this is equivalent to
changing the braid word corresponding to the plat using the relators in the
braid group. So the end points of the strings are all fixed and with that
constraint, any manipulation of strings is allowed as long as the resulting
object is still a plat. This is shown in Figure 2 and Figure 3.

####  2.2.2 Double coset moves and the Pocket move

Double coset moves on plats permute the bridges in different ways, thus giving
freedom of movement to the bridges. For the braid group $\mathcal{B}_{2n}$, a
double coset move on the plat defined by $\sigma\in\mathcal{B}_{2n}$ is one
which takes this plat to the plat defined by $\alpha\sigma\beta$ where
$\alpha$ and $\beta$ are elements in $\mathcal{K}_{2n}$, the Hilden subgroup
([4]) of the braid group, which has the following generating set:
$\\{\sigma_{1},\sigma_{2}{\sigma_{1}}^{2}\sigma_{2},\sigma_{2i}\sigma_{2i-1}\sigma_{2i+1}\sigma_{2i},1\leq
i\leq n-1\\}$. The relators for $\mathcal{K}_{2n}$ were computed by Stephen
Tawn, in [6].

For $n=2$, the generators of the Hilden subgroup are:
$\\{\sigma_{1},\sigma_{2}{\sigma_{1}}^{2}\sigma_{2},\sigma_{2}\sigma_{1}\sigma_{3}\sigma_{2}\\}$.
The plat moves on the bottom bridges coming from these generators are shown in
Figure 5.

Note that the double coset moves essentially try to capture all those moves,
not covered by the scope of braid isotopies and stabilization/destabilization,
which take plats to plats while preserving the link type. Figure 5 is a good
motivating example to observe this phenomenon. Notice that all the moves in
Figure 5, change the braid word but not the knot type.

Birman, in [2], does not use the nomenclature, “double coset moves”. We are
using it here, because, without this class of moves, given two plat
presentations $K_{1}$ and $K_{2}$ of a knot, using only braid isotopies and
stabilization/destabilization, the best we can do is get $K_{1}$ and $K_{2}$
to be in the same double coset of $\mathcal{B}_{2n}$ modulo
$\mathcal{K}_{2n}$.

2pt

Figure 5: Generators of $\mathcal{K}_{4}$

2pt A at 224 402 B at 224 118 A at 585 402 B at 585 118

Figure 6: Pocket move on an 8-plat

2pt A at 153 361 B at 143 85 A at 444 361 B at 458 85 C at 118 313 C at 423 39

Figure 7: Generalised pocket move on a higher index plat

Figures 6 and 7 depict a generic pocket move. Consider a plat presentation $L$
where a top or a bottom bridge which is truncated at a level strictly between
the top and the bottom levels of the plat (as shown in the Figures), say
$t=t_{0}$, where $0<t_{0}<1$. Now, define a smooth path $\gamma$,
$\gamma:[0,1]\longrightarrow\mathbb{R}^{3}\ L$, such that the plat height
function is monotonic on $\gamma$ and we have that $h^{-1}(\gamma(0))=t_{0}$
and $h^{-1}(\gamma(1))=1$, in case we are doing a pocket move with a bottom
bridge, or $h^{-1}(\gamma(1))=0$, if we are doing a pocket move with a top
bridge. Now, we take the local max or min corresponding to the bridge that we
picked and drag it along the path $\gamma$. This results in the bridge weaving
around the rest of the plat, as shown in Figure 6. Further, we can also twist
the bridge as it follows the path $\gamma$, and we can do this process for any
top or bottom bridge that can be truncated prematurely, with each bridge
following a potentially different path. In [5], we prove the following Lemma:

######  Lemma 4.

Pocket moves can be realised as a combination of braid isotopies and a
sequence of double coset moves.

This lemma shows us the geometric scope of the pocket move.

####  2.2.3 The flip move

Consider the unknot positioned in 3-space given by the following equation:
$K=\\{(x,y,z):x^{2}+\frac{y^{2}}{4}=1,z=0\\}$. Figure 8 shows the flip move on
the index one unknot diagram, which is the following isotopy (or its inverse):
take point B ($(0,-2,0)$) and move it along the following path:

$x=0,y=\cos(\theta)-1,z=\sin(\theta)$

where $\pi\leq\theta\leq 3\pi$.

This path traces out the circle of radius one centered at $(0,-1,0)$, in the
$y-z$ plane, moving clockwise if viewed from the region $x\geq 0$. The effect
of this isotopy on the disc is shown in Figure 8.

2pt $A$ at 132 368 $A$ at 221 385 $A$ at 388 376 $A$ at 531 391 $B$ at 136 124
$B$ at 225 149 $B$ at 402 184 $B$ at 519 212 saddle at 538 279 pt of minima at
386 127 pt of minima at 524 162

Figure 8: The flip move on the 1-bridge 0-crossing diagram

2pt $A$ at 154 311 $A$ at 472 311 $B$ at 157 102 $B$ at 474 102

Figure 9: The flip move on an 8 plat

On a generic $2n$-plat with braid word $\mathbf{AB}$, here’s how the flip move
changes the braid word:
Case (i): Flipping $\mathbf{B}$ into the plane of the paper between the $k$-th
and $(k+1)$-st strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{(\sigma_{1}\sigma_{2}...\sigma_{k-1})}^{k}{((\sigma_{2n-1})^{-1}...(\sigma_{k+2})^{-1}(\sigma_{k+1})^{-1})}^{2n-k}\mathbf{B}$

Case (ii): Flipping $\mathbf{B}$ out of the plane of the paper between the
$k$-th and $(k+1)$-st strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{((\sigma_{k-1})^{-1}(\sigma_{k-2})^{-1}...(\sigma_{1})^{-1})}^{k}{(\sigma_{k+1}\sigma_{k+2}...\sigma_{2n-1})}^{2n-k}\mathbf{B}$

Case (iii): Flipping $\mathbf{B}$ into the plane of the paper between the
first two strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{((\sigma_{2n-1})^{-1}(\sigma_{2n-2})^{-1}...(\sigma_{3})^{-1}(\sigma_{2})^{-1})}^{2n-1}\mathbf{B}$

Case (iv): Flipping $\mathbf{B}$ out of the plane of the paper between the
first two strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{(\sigma_{2}\sigma_{3}...\sigma_{2n-2}\sigma_{2n-1})}^{2n-1}\mathbf{B}$

Case (v): Flipping $\mathbf{B}$ into the plane of the paper between the last
two strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{(\sigma_{1}\sigma_{2}...\sigma_{2n-3}\sigma_{2n-2})}^{2n-1}\mathbf{B}$

Case (vi): Flipping $\mathbf{B}$ out of the plane of the paper between the
last two strands:

$\mathbf{AB}\longrightarrow\mathbf{A}{((\sigma_{2n-2})^{-1}(\sigma_{2n-3})^{-1}...(\sigma_{2})^{-1}(\sigma_{1})^{-1})}^{2n-1}\mathbf{B}$

Further, we define the micro flip move, wherein only $k$ (where $k$ is even)
out of the $n$ strands are flipped. A pictorial representation is given in
Figure 10.

2pt $A$ at 134 283 $A$ at 475 282 $B$ at 82 85 $B$ at 429 84

Figure 10: An example of a Microflip move

Corresponding to the aforementioned cases, we also have six more cases where
we do the flip with the top bridges. The change in braid word can be computed
as shown above. Figure 11 shows the corresponding sequence of moves using only
braid isotopies, double coset moves and stabilization/destabilization, to go
from the plat on the right to the plat on the left in Figure 9. Repeating the
same sequence of moves on the first strand (from the left) in the last plat in
Figure 11, we get the left plat in the first row in Figure 12. This plat is
now defined by the braid $A\delta B$, where $\delta$ is the full twist in the
braid group $\mathcal{B}_{2n}$, which generates the center of the braid group.
Therefore, via braid isotopies, we can slide the braid word $B$ across the
full twist to get the second plat, defined by $AB\delta$, in Figure 12. Now,
we can see that this plat can be resolved via double coset moves to give us
the plat defined by $AB$, that we wanted to get to.

The flip move allows us to turn different strands of the braid both ways
simultaneously, which we can not achieve with just the double coset moves.

2pt $A$ at 120 513 $A$ at 361 515 $A$ at 603 515 $A$ at 106 233 $A$ at 357 233
$A$ at 624 233 $B$ at 120 358 $B$ at 361 356 $B$ at 603 357 $B$ at 106 74 $B$
at 357 75 $B$ at 624 73

Figure 11: Stabilization sequence for the flip move

2pt $A$ at 139 683 $A$ at 296 292 $B$ at 140 457 $B$ at 293 95 $AB$ at 436 683

Figure 12: Using double coset moves to undo the ‘turning’ of a braid

###  2.3 A special configuration of plats

Figure 13 depicts a special configuration that plats can always be put into.
The aim of employing this particular configuration of plats is to have either
the rightmost or the leftmost string of the plat devoid of any crossings. We
want that so that we can remove singularities from min or max tiles which are
attached to a punctured tile. This is explained in detail in Lemma 11.

2pt

Figure 13: A special configuration that every plat can be put into

###  2.4 Sphere Foliation and Tiling

As we remarked in §2.1, since the level curves $C_{t}^{i}$ are cross sections
of $S_{i}$, taking a union of $C_{t}^{i}$’s over all $t$’s gives us the
surface $S_{i}$. Therefore, ${S_{i}}=\bigsqcup_{t\in[-0.25,1.25]}C_{t}^{i}$.
This gives a singular foliation of the surface $S_{i}$, where the leaves of
the foliation are the simple closed curves $s_{i,t}^{j}$’s. The singular
leaves are exactly the intersecting (which includes self intersections)
curves, of which there are only finitely many. The singular leaves correspond
to saddles on the surface. Further, self intersecting closed curves give rise
to curves which either self intersect again or degenerate to a single point in
the foliation, which corresponds to a local maxima or local minima on $S_{i}$.
As mentioned earlier, these points of maxima are at height $t>1$ and the
minima are at height $t<0$.

Using this singular foliation, we will now describe a way to tile $S_{i}$. We
thicken up the singular leaves such that the union of the ‘neighborhoods’ of
the singular leaves then determines a tiling of $S_{i}$. So, a tile $T$ on the
sphere $S_{i}$ is either a thickened up neighborhood of a singular leaf $s$,
i.e. a tile $T$ is the surface $s\times I$, where $I$ is the unit interval, or
a tile $T$ is a neighborhood of a point of minima or maxima on the sphere.
Thus, each tile on the sphere contains exactly one singularity (saddle or
local min/max). Abusing notation, for the remainder of the paper, we might
refer to a tile and the singularity it contains interchangeably. It will be
clear from context what we are referring to. Any tile $T$ has a boundary
comprising of circles. A tile with $c$ boundary circles will be denoted as:
$T_{c}$.

Below we give a detailed description of all the possible singularities (and
hence, tiles) which show up in the foliation (and tiling) of $S$ and $S_{p}$.
Also, note that each tile is foliated by the level curves $C_{t}^{i}$, in a
manner so that each tile which is not a neighborhood of a point of minima or
maxima, contains exactly one self intersecting singular leaf. With that in
mind, we have the following tiles:

(i) Circle intersects circle: Figure 14 depicts the singularity (and the tile
generated from it) $T_{3}$. The top row corresponds to the 3-D embedding on
the left and the bottom row corresponds to the 3-D embedding on the right. The
tile $T_{3}$ is a pair of pants with three boundary circles (hence the
subscript ‘3’ in the notation), lying on the sphere. The green shaded portion
shown in Figure 14 is NOT a part of the tile.

We classify the saddles corresponding to $T_{3}$ into two categories:

######  Definition 5.

a) Up saddle: A saddle such that two curves pass through the saddle to join
and become one curve, going in the direction of decreasing ‘$t$’.
In Figure 14, in the last row, the 3-D embedding on the left depicts an up
saddle.

b) Down saddle: A saddle such that one curve passes through the saddle to
split into two, going in the direction of decreasing ‘$t$’.
In Figures 14, in the last row, the 3-D embedding of the tile, on the right,
depicts a down saddle.

2pt before saddle at 134 208 at level of saddle at 368 208 after saddle at 607
210 tile $T_{3}$ at 136 32 3-D embeddings of $T_{3}$ at 492 32

Figure 14: Circle intersecting itself - $T_{3}$

(ii) Points of extrema: The other type of singularity that occurs on the
sphere is points of minima and maxima. Name the tile corresponding to these
singularities, $T_{1}$, shown in Figure 15. $T_{1}$ is a disc, with one
boundary circle (hence the subscript ‘1’ in the notation), lying on the
sphere. We call a tile of type $T_{1}$, a min tile (respectively, max tile),
if the singularity in the tile is a local min (respectively local max).

(iii) Punctured disc: This tile type occurs only on $S_{p}$. Call this tile
$T_{p}$. This will essentially be a very small neighborhood of a puncture on
$S_{p}$. By ‘very small neighborhood’, we mean that $T_{p}$ is a punctured
disc containing no other singularities.

2pt tile $T_{1}$ at 114 49 3-D embeddings of $T_{1}$ at 385 44

Figure 15: Points of extrema - $T_{1}$

Figures 16 and 17 show the standard positions of the splitting sphere and the
twice punctured sphere, respectively. The splitting sphere $S$, in its
standard position has two tiles, one max tile and one min tile. On the other
hand, the twice punctured sphere $S_{p}$, in its standard position has a total
of six tiles: one each of a max and a min tile, two $T_{3}$ tiles and two
$T_{p}$ tiles.

2pt $K_{2}$ at 303 157 $K_{1}$ at 165 160 max $T_{1}$ tile at 292 281 min
$T_{1}$ tile at 300 50

Figure 16: Standard configuration of the splitting sphere

2pt $T_{3}$ tile at 332 222 $T_{3}$ tile at 329 69 $T_{p}$ tile at 241 188
$T_{p}$ tile at 238 104 max $T_{1}$ tile at 284 294 min $T_{1}$ tile at 278 5

Figure 17: Standard configuration of the twice punctured sphere

###  2.5 Graph and complexity function

Given the tiling of a sphere embedding ${S_{i}}$, we will now define a
directed graph $G_{S_{i}}$ associated with it in the following way:

The set of vertices of the graph is the set of singularities on $S_{i}$ or,
equivalently, the tiles in the foliation of ${S_{i}}$. There is an edge going
from vertex $a$ to vertex $b$ if the tiles corresponding to the singularities
are glued via a circle boundary component in the tiling of the disc and the
singularity in the tile $a$ is at a larger $t$-value than the singularity in
the tile $b$. Therefore, the valence of a tile $T_{c}$ is $c$. For the
remainder of this paper, abusing notation, when we talk about a vertex of the
graph $G_{S_{i}}$, we might mean either the vertex or the tile represented by
it. It should be clear from context, what we mean.

Notice that every edge in the graph corresponds to a simple closed curve,
which is a separating curve on the sphere. Now, if we had a cycle in the
graph, that would give us a way to build a non-separating curve on the sphere
(because the boundary components of each tile $\mathbf{\alpha}$ separate the
sphere into connected components and each vertex which shares an edge with
$\mathbf{\alpha}$ has to be in a different connected component of
$S_{i}-\alpha$), which is impossible. Therefore, $G_{S_{i}}$ is a tree for any
embedding $S_{i}$.

We are now in a position to define the complexity function. Let $|T_{c}|$ be
the number of type $T_{c}$ tiles in the tiling of $S_{i}$. Then, define the
complexity function on $S_{i}$ as follows:

$c(\mathbf{S_{i}})=|T_{3}|$

Lemmas 7 and 8 in §3 tells us why it makes sense to define the complexity
function this way.

##  3 Main Result

We prove the following Lemmas which we will later use to prove Theorems 1 and
2:

######  Lemma 6.

Let $X_{i},i=1,2,...,n$ be $n$ simplicial complexes of degree 2 which are
glued together along boundary circles, to make a surface $X$. Let there be
$|X_{i}|$ many $X_{i}$’s such that each such piece is glued in the same
manner. Let $\chi(X_{i})$ be the Euler characteristic of $X_{i}$. Then, we
have:

$\chi(X)=\sum_{i=1}^{n}|X_{i}|\chi(X_{i})$

###### Proof.

For any simplicial complex $C$, let $n_{i}(C)$ be the number of $i$-cells in
$C$.
Consider the case where $X$ is obtained from $X_{1}$, $X_{2}$ by gluing
$X_{1}$ with $X_{2}$ via circles. Let $\tau$ be the gluing simple closed
curve.
Now, let $X$ have a cell decomposition in which the circle $\tau$ is a
subcomplex, and so $\tau$ consists of $k$ 0-dimensional cells and $k$
1-dimensional cells for some $k\geq 1$.
Cutting $X$ along $\tau$ to get $X_{1}\bigcup X_{2}$ and counting cells, we
get:

$n_{0}(X)=n_{0}(X_{1})+n_{0}(X_{2})-k$ (1)

$n_{1}(X)=n_{1}(X_{1})+n_{1}(X_{2})-k$ (2)

$n_{2}(X)=n_{2}(X_{1})+n_{2}(X_{2})$ (3)

(1) - (2) + (3) gives us:

$\chi(X)=\chi(X_{1})+\chi(X_{2})$

Induction completes the proof.

∎

######  Lemma 7.

Given any geometric realisation and tiling of the splitting sphere $S$, the
following combinatorial relation holds:
$|T_{1}|-|T_{3}|=2$,
where $|T_{i}|$ is the number of tiles of type $T_{i}$ in the foliation of
$S$.

###### Proof.

From Lemma 6, we have the following equation:

$\displaystyle\chi(X)$ $\displaystyle=\sum_{i=1}^{n}|X_{i}|\chi(X_{i})$

Reconstructing $S$, gluing together tiles of type $T_{1}$ and $T_{3}$, and
using the equation above, we get the following relationship:

$\displaystyle 2$ $\displaystyle=|T_{3}|\chi(T_{3})+|T_{1}|\chi(T_{1})$
$\displaystyle=|T_{3}|(-1)+|T_{1}|(1)$ $\displaystyle=|T_{1}|-|T_{3}|$

∎

We have a similar result for $S_{p}$, with slight modifications. We consider
the compact subsurface of $S_{p}$ which consists of only tiles of type $T_{1}$
and $T_{3}$. It is enough to consider this because the number of tiles of type
$T_{p}$ on any geometric realisation of $S_{p}$ is fixed, and is equal to two.
This sub-surface is an annulus, say $\mathbf{A_{p}}$, because this is
essentially a compact sub-surface of a twice punctured sphere, with two
boundary components. Therefore, for $S_{p}$, we get the following result:

######  Lemma 8.

Given any geometric realisation and tiling of the twice punctured sphere
$S_{p}$, the following combinatorial relation holds:
$|T_{1}|=|T_{3}|$,
where $|T_{i}|$ is the number of tiles of type $T_{i}$ in the foliation of
$S_{p}$.

###### Proof.

From Lemma 6, we have the following equation:

$\displaystyle\chi(X)$ $\displaystyle=\sum_{i=1}^{n}|X_{i}|\chi(X_{i})$

Reconstructing $A_{p}$ as a union of $T_{1}$’s and $T_{3}$’s, we get the
following relation:

$\displaystyle\chi(A_{p})=0$
$\displaystyle=|T_{3}|\chi(T_{3})+|T_{1}|\chi(T_{1})$
$\displaystyle=|T_{3}|(-1)+|T_{1}|(1)$ $\displaystyle=|T_{1}|-|T_{3}|$

Now, the observation that $S_{p}=A_{p}\bigcup T_{p}\bigcup T_{p}$ completes
the proof.

∎

We are now ready to prove Theorem 1:

###### Proof.

Lemma 7 tells us that removing one singularity of type $T_{3}$ also gets rid
of one singularity of type $T_{1}$, and vice versa. It also tells us that
there will always be more than 2 singularities of type $T_{1}$ in any
foliation of any $S_{i}$. Notice that for a plat presentation of a split link
with a split diagram, the sphere has only two tiles: a min $T_{1}$ and a max
$T_{1}$, this is shown in Figure 16. As mentioned before, this is called the
standard configuration of $S$. With this setup, to simplify a plat
presentation $L_{i}$ of a split link to an ‘obviously’ split plat
presentation, all we need to do is reduce the corresponding sphere $S_{i}$ to
its standard configuration. Towards achieving that goal, our strategy going
forward is to remove singularities on $S_{i}$ by doing plat moves on the split
link. Note that we employ the same strategy to get the sequence for Theorem 2
i.e. our aim is to reduce the geometric realisation of $S_{p}$ corresponding
to a ‘complicated’ plat presentation of a composite knot to an ‘obviously’
composite one. We start out by removing any possible crossings in the link
diagram via braid isotopies or double coset moves. Then, we proceed to
removing singularities from the sphere foliation using the pocket move in a
fashion so that $c(S_{i+1})<c(S_{i})$. We stop this process when we reach some
$L_{k}$ so that $c(S_{k})=0$. We will use the directed graph defined in the
previous section to help keep track of the process of removing singularities
from the sphere foliation. Toward that end, the next two Lemmas tell us when
can a vertex (i.e. tile or singularity) be removed from the graph using plat
moves:

######  Lemma 9.

For a given $L_{i}$ in the sequence of Theorems 1 or 2, in the directed graph
$G_{S_{i}}$, if there is a vertex $V$ which satisfies one of the following
conditions:

a) $V$ represents a min tile of type $T_{1}$ connected to a vertex $N$
representing a tile containing a down saddle, such that any level curve
corresponding to $V$ does not contain any other level curve

b) $V$ represents a max tile of type $T_{1}$ connected to a vertex $U$
representing a tile containing an up saddle such that any level curve
corresponding to $V$ does not contain any other level curve then, we can
remove the vertex $V$ using the pocket move, so that we get to $L_{i+1}$ in
the sequence given in Theorem 1, where $c(S_{i+1})<c(S_{i})$.

###### Proof.

2pt $\alpha$ at 193 90 $V$ at 121 46 $V_{1}$ at 230 46 $\mathbf{B}$ at 110 236
$S_{V_{1}}$ at 177 170 cross section of $N(\alpha)$ at 400 129 $N(\alpha)$ at
265 180

Figure 18: Path isotopy to remove saddles

2pt

Figure 19: Removing saddle attached to the tile containing the puncture

2pt

Figure 20: Removing saddle attached to the tile containing the puncture

Consider a vertex $V$ satisfying condition a). Then, we look for a closest min
tile to $V$, in the graph $G_{S_{i}}$, say $V_{1}$. Note that such a tile
always exists because $V$ is connected to a tile of type $T_{3}$, say $N$,
containing a down saddle, where $N$ is either connected to a min tile of type
$T_{1}$, or $N$ is connected to another tile of type $T_{3}$, which might
contain either an up saddle or a down saddle. In either case, this process
continues until we hit another min tile, because the graph $G_{S_{i}}$ is a
finite tree. Consider the saddle $N_{V}$ contained in tile $N$, that the
singularity in tile $V$ is induced by. Now, define a path $\alpha$ (the pink
curve in Figure 18), from $N_{V}$ to $V_{1}$, on the sphere, such that
$\alpha$ is always transverse to the foliation, other than at points
$\alpha(0)$, $\alpha(1)$. Consider a thickened up regular neighborhood of
$\alpha$, say $N(\alpha)$ which stays completely on one side of the sphere, as
shown in Figure 18. Notice that $N(\alpha)$ is a 3-ball, positioned so that
the boundary sphere is split up into the following four components: two copies
of $\alpha\times I$ (the green part in the figure which lives on the surface,
and the blue part which is completely on one side of the surface) glued along
their respective $\alpha\times\\{0\\}$ and $\alpha\times\\{1\\}$ components.
This gives us an annulus. Capping off this annulus with two discs gives us the
two sphere which is the boundary of $N(\alpha)$.

For any singularity $X$ on $S_{i}$, let $t_{X}$ denote the level at which the
singularity occurs. Now, we inspect $C^{i}_{t}$, for some
$t\in(t_{N},t_{N}+\epsilon)$. The knot strands inside the curves corresponding
to $V$, we remove via the following isotopy: we move the bridges corresponding
to these strands along the path $\alpha$, always staying inside the $3$-ball
$N(\alpha)$, starting from the point $N_{V}$ on the boundary of $N(\alpha)$
and ending at the point $V_{1}$, also on the boundary of $N(\alpha)$. Notice
that this corresponds to doing a pocket move. Once we have emptied out the
simple closed curve corresponding to $V$, we can surger off the subdisc which
is the tile represented by $V$, thus simultaneously cancelling the saddle $N$,
while removing the vertex $V$.
We can do a similar isotopy for a vertex $V$ satisfying condition b), with the
only difference being that we now need to look for the next closest max tile
to $V$.

In both the cases above, we get a new plat $L_{i+1}$ such that
$c(S_{i+1})<c(S_{i})$.

∎

######  Lemma 10.

A vertex satisfying condition a) or b) in Lemma 9 always exists, if there are
any tiles of type $T_{3}$ in the foliation of the sphere embedding $S_{i}$.

###### Proof.

6pt connecting scc at 158 156 up saddle at 453 175 down saddle at 55 225
$s_{1}$ at 205 206 $s_{2}$ at 311 170 $b$ at 155 178 $c$ at 292 187 $d$ at 385
200

Figure 21: A down saddle connected to an up saddle via a simple closed curve

We argue this by contradiction. If there were no such vertices as described in
the previous lemma, then no down saddle is connected to a min tile and no up
saddle is connected to a max tile.

Then, near any down saddle $s_{1}$, the splitting sphere locally looks like as
depicted in Figure 21, with the variation that $s_{1}$ could also have been
connected to another down saddle, as opposed to the up saddle shown in the
figure. Now, since the saddle $s_{1}$ is not connected to a min tile, neither
of the two curves $b$, $c$ are capped off by discs. Therefore, $s_{1}$ is
connected to two more saddles, say $s_{2}$ and $s_{3}$. Note that $s_{2}$ and
$s_{3}$ cannot be connected to each other because that would mean the surface
has genus, which is a contradiction. Then, if both $s_{2}$ and $s_{3}$ are
down saddles, by the same argument, as above, we get two more down saddles
each for $s_{2}$ and $s_{3}$, because they are not connected to any min tiles
either. If this process continues indefinitely, we have infinitely many tiles,
which can not happen.

Therefore, without loss of generality, let $s_{2}$ be an up saddle. Now the
local picture is exactly as shown in Figure 21. Further, since no up saddle is
connected to a max tile, $d$ cannot be capped off by a disc, therefore $d$ is
further connected to another saddle and, as before, this process continues
indefinitely unless there is an up saddle connected to a max tile or down
saddle connected to a min tile.
If we locate a min tile $M$ connected to a down saddle $s_{1}$, such that the
level curve corresponding to $M$ contains a level curve coming from another
tile connected to $s_{1}$, then we use the pocket move to remove the inner
level curve. Doing this, we now have a vertex satisfying condition a) of the
previous lemma. The argument is exactly the same for a max tile.
∎

In light of Lemmas 9 and 10, we now have a blueprint which tells us how to
create the sequence in Theorem 1, monotonically decreasing the complexity
function on the $L_{i}$’s. We terminate the sequence when we reach a $L_{l}$
which does not have any singularities on the splitting sphere, other than a
top max tile and a bottom min tile. Then, any remaining crossings come from
twisting the bridges or doing Reidemeister II moves or moving bridges
completely over or under each other, which can be undone using the double
coset moves or braid isotopies, leading us to an ‘obviously’ split
presentation. This completes the proof of Theorem 1.

∎

The proof for Theorem 2 is very similar to that of 1. We remove tiles of type
$T_{3}$ from $S_{p}$ in the same fashion that we did for $S$, except for when
removing the saddle from a type $T_{3}$ tile which is also attached to a
$T_{p}$ tile. To deal with that case, we utilise the following result:

######  Lemma 11.

If the punctured sphere $S_{p}$ has a tile of type $T_{3}$ with a saddle such
that it is connected to both a tile of type $T_{1}$ and $T_{p}$, then we can
remove the saddle and a $T_{1}$ tile corresponding to the $T_{3}$ tile using
the moves detailed in Theorem 2.

###### Proof.

This type of situation can happen in the following different ways:

Case I: The first case is the configuration shown in Figure 19. Then, as shown
in the Figure, we can do a pocket move which empties out the specified $T_{1}$
tile. Then, we can do an isotopy on the surface to remove the saddle
corresponding to the $T_{3}$ tile and we are done.

Case II: The second case is the configuration shown in Figure 20. To remove
the singularity in this case, we utilise the set up detailed in §2.3. Using
the flip move, we first do flip moves at the appropriate spots (in the example
shown in Figure 13, we do the flip move at the pink crosses). This enables to
free up the outermost strand (this will be the left most or right most
depending on where the puncture is located). Once we have achieved that
configuration, we again do a pocket move to empty out the specified $T_{1}$
tile and then do an isotopy to remove the saddle.

Case III: This is when a saddle containing $T_{3}$ tile is attached to two
$T_{p}$ tiles. Then we consider the third boundary circle of the $T_{3}$ tile.
It is either connected to another $T_{3}$ tile or a $T_{1}$ tile. In either
event, we can find some $T_{1}$ tile and a corresponding saddle to be removed,
via the process described for the splitting sphere.

This completes the proof.

∎

## References

  * [1] Joan S. Birman  “Braids, Links, and Mapping Class Groups. (AM-82)”  Princeton University Press, 1974  URL: http://www.jstor.org/stable/j.ctt1b9rzv3.1
  * [2] Joan S. Birman  “On the Stable Equivalence of Plat Representations of Knots and Links”  In _Canadian Journal of Mathematics_ 28.2 Cambridge University Press, 1976, pp. 264–290  DOI: 10.4153/CJM-1976-030-1
  * [3] Joan S. Birman and William W. Menasco  “On Markov’s Theorem”  arXiv, 2002  DOI: 10.48550/ARXIV.MATH/0202186
  * [4] Hugh M. Hilden  “Generators for two groups related to the Braid group”  In _Pacific Journal of Mathematics_ 59, 1975, pp. 475–486  DOI: 10.2140/pjm.1975.59.475
  * [5] Deepisha Solanki  “Studying Links via Plats: The Unlink”, 2023  arXiv:2308.00732 [math.GT]
  * [6] Stephen Tawn  “A presentation for Hilden’s subgroup of the braid group”, 2007  arXiv:0706.4421 [math.GR]