# Survivable Probability of SDN-enabled Cloud Networking with Random Physical
Link Failure

Zhili Zhou  United Airlines
Chicago, IL USA
Email<EMAIL_ADDRESS>Tachun Lin  Department of Computer Science and
Information Systems
Bradley University, Peoria, IL USA
Email<EMAIL_ADDRESS>
###### Abstract

Software-driven cloud networking is a new paradigm in orchestrating physical
resources (CPU, network bandwidth, energy, storage) allocated to network
functions, services, and applications, which is commonly modeled as a cross-
layer network. This model carries a physical network representing the physical
infrastructure, a logical network showing demands, and logical-to-physical
node/link mappings. In such networks, a single failure in the physical network
may trigger cascading failures in the logical network and disable network
services and connectivity. In this paper, we propose an evaluation metric,
survivable probability, to evaluate the reliability of such networks under
random physical link failure(s). We propose the concept of base protecting
spanning tree and prove the necessary and sufficient conditions for its
existence and relation to survivability. We then develop mathematical
programming formulations for reliable cross-layer network routing design with
the maximal reliable probability. Computation results demonstrate the
viability of our approach.

###### Index Terms:

Survivable probability, protecting spanning tree, cross-layer network design,
network reliability, cloud networking

##  I Introduction

In a cloud computing architecture, hardware/physical infrastructures are
physical resources composed of datacenters and communication networks [1]. All
cloud services above are then realized through cloud network mappings, which
include the mappings of demands (modeled as a logical network) onto the
physical infrastructure and the deployment/allocation of virtual machines and
physical resources [2].

Software-defined networking (SDN) [3] and network function virtualization
(NFV) [4], which allow fine-grained control, orchestration, and management of
heterogeneous physical resources, promise a future open marketplace where
applications can be rapidly deployed, programmed, and operated on a converged
infrastructure during their life cycles [5]. A software-defined infrastructure
(SDI), such as SAVI [5][6], supports virtual network function (VNF)
realization and enables application/service/infrastructure programmability.

The high-availability, reliability, and resilience of a software-defined
infrastructure promises better cloud services, thus it becomes the key
underlying network structure for SDI control and management [7][8]. The cloud
networking facilitated with SDN/NFV is often modeled as a cross-layer network.
In such a network, link or node failures in the SDN-enabled physical
infrastructure may disrupt not only its own connectivity and capacity, but
also fail or interrupt the users’ demands for cloud applications and services
in network abstraction (logical networks). Hence, leveraging SDN’s
programmability, our interest in this paper is to discover the optimal design
of SDN-enabled cloud networking with less chances of failure.

The survivable network design in single-layer networks, which guarantees the
network connectivity after network component’s failure(s), was studied in
[9][10][11]. They proposed two mechanisms, namely protection and restoration,
which were broadly adopted in modern networks. Nevertheless, the same
mechanisms cannot be directly applied to the design of survivable cross-layer
network, where the connectivity of the logical network remains after a single
or multiple failures of physical network component. To overcome this
challenge, [12][13][14] studied mappings of logical links onto disjoint
physical paths, and [15][16][17] proposed the mappings avoiding cross-layer
cuts. Another line of investigation is through route selection [14][18][19].
While approaches in [15][16] required the enumeration of all cutsets or path
sets, Zhou et al. [20][21] proposed the concept of protecting spanning tree
set which avoided such enumeration.

While most works in [12]–[20] are concentrated on finding a survivable cross-
layer mapping, an NP-hard problem, it is still an open question on which
routings should be chosen when a survivable mapping does not exist. Yallouz et
al. [22][23] introduced the _level of survivability_ which provides “a
quantitative measure for specifying any desired level of survivability” under
a single-layer network setting through spanning trees. Zhou et al. [21][24]
also introduced a similar concept of _partial survivability_ in cross-layer
networks. Based on these works, we define the survivable probability of a
given cross-layer network, a new evaluation metric which is the probability of
the logical network to remain connected after any physical link failure. We
wish to point out that _survivable probability_ is evaluated when each
physical link may fail with a uniform or random failure probability, while the
physical link failure probability considered in [21][24] is always 100%. Also,
the survivable probability discussed here is for cross-layer networks instead
of single-layer networks discussed in [22][23].

Another related work [25] also studied the cross-layer network reliability by
calculating the failure polynomials under random physical link failure. Our
proposed study is different from [25] in two aspects: (1) the solution
approach in [25] is based on cross-layer cutsets, while our approach
eliminates the needs to enumerate all cutsets, and (2) we consider not only
uniform but also random failure probability on all physical links.

Our contributions in this paper are: (1) we define a new evaluation metric of
reliability, i.e., the survivable probability, for cross-layer networks;
instead of approximating with failure polynomials, we propose an exact method
to identify a network’s survivable probability; (2) we introduce the concept
of _base protecting spanning tree set_ and prove its existence; (3) we prove
that the survivable probability of a network with unified physical link
failure probability is equivalent to the cross-layer network design with the
minimal number of shared physical links in a protecting spanning tree set; (4)
compared with the failure polynomial approximation for the reliability of
cross-layer networks, our approach avoids the enumeration of all cross-layer
cutsets and requires at most $|E_{P}|$ protecting spanning trees; (5) last but
not least, the proposed base protecting spanning tree set enables SDI control
and management and can be used to improve resilience of cloud services under
unpredictable failure(s), which can be treated as an auxiliary protection
scheme for SDN without introducing redundant physical resources.

The rest of this paper is organized as follows: Section II provides formal
definitions and problem description for survivable probability and protecting
spanning trees. Solution approaches for survivable probability are presented
in Section III. Section IV shows the simulation results for survivable
probability based on the protecting spanning tree set in a cross-layer
network, followed by the conclusion in Section V.

##  II Definitions and Problem Description

Given a cloud network with a physical network $G_{P}=(V_{P},E_{P})$ and a
logical network $G_{L}=(V_{L},E_{L})$, where each logical node has an one-to-
one mapping onto a physical node (denoted as $m(s)=i$ with $s\in V_{L}$ and
$i\in V_{P}$), and each logical link is mapped one-to-one onto a physical path
(denoted as $m(u)=p_{u}$ with $u\in E_{L}$ and $p_{u}\subset E_{P}$). We let
$\mathcal{M}(G_{L},G_{P})=\\{m(s),m(u):s\in V_{L},u\in E_{L}\\}$ represent the
mapping between logical to physical networks. Notations and parameters used in
this paper are listed in Table I.

Notation |  Description
---|---
$G_{P}=(V_{P},E_{P})$ |  Physical network with node set $V_{P}$ and link set $E_{P}$. $i,j$ are node indices and $e$ is the link index
$G_{L}=(V_{L},E_{L})$ |  Logical network with node set $V_{L}$ and link set $E_{L}$. $s,t$ are node indices and $u,v$ are link indices
$\mathcal{M}(G_{L},G_{P})$ |  The mapping between physical and logical networks, including node and link mappings
$\mathcal{P}_{u}$ |  The set of routings (physical paths) for $u\in E_{L}$, where $p_{u}\in\mathcal{P}_{u}$ is its element
$\lambda$ |  $\lambda=[\tau,\\{p_{u}:u\in\tau\\}]$, where $\tau\subset E_{L}$ is a logical spanning tree and $\\{p_{u}:u\in\tau\\}$ is the routings of the tree branches
$\mathcal{T}$ |  A spanning tree set, where $\lambda\in\mathcal{T}$
$E_{P}(\lambda)$ |  All physical links utilized by the routings of $\lambda$’s branches
$E^{C}_{P}(\mathcal{T})$ |  Common physical links shared by the routings of all $\lambda\in\mathcal{T}$
$M(E_{L})$ |  A set of logical link mappings, where $m(E_{L})\in M(E_{L})$ is one instance of logical link mapping
$R(m(E_{L}))$ |  A set of physical links whose failures will disconnect $G_{L}$ for a given mapping $m(E_{L})$
$\Phi(G_{P},G_{L})$ |  The maximal survivable probability of a cross-layer network
Parameter |  Description
$\rho_{e}$ |  Physical link failure probability with $e\in E_{P}$
$\rho$ |  Unified physical link failure probability with $e\in E_{P}$
TABLE I: Notations and parameters

###### Definition 1

Given $G_{P}$, $G_{L}$, and failure probability of physical link
$\rho_{e},e\in E_{P}$, the survivable probability of a cloud network is the
probability of the logical network to remain connected after physical link
failure(s).

Problem Description: Given a cloud network $G_{P},G_{L}$, and $\rho_{e},e\in
E_{P}$. We wish to identify its mappings $\mathcal{M}(G_{L},G_{P})$ which
provide the maximal survivable probability.

###### Definition 2

Given $G_{P}$, $G_{L}$, a logical spanning tree $\tau\in G_{L}$ and its
routings $\\{p_{u}:u\in\tau\\}$. $\tau$ is a protecting spanning tree if it
remains connected after one or multiple physical link failures.

We let $\lambda=[\tau,\\{p_{u}:u\in\tau\\}]$ denote a protecting spanning tree
in a cloud network and $E_{P}(\lambda)=\\{e:e\in\cup_{u\in\tau}p_{u}\\}$ be
the physical link set utilized by the routings of $\tau$. With the
introduction of physical link failure probability, we may further define the
maximal protecting spanning tree as follows. Given cross-layer network and any
logical link mapping, a maximal protecting spanning tree is a protecting
spanning tree with the maximal survivable probability.

###### Definition 3

Given $G_{P}$, $G_{L}$, $\rho_{e},e\in E_{P}$, the survivable probability of
$\lambda$$=[\tau,\\{p_{u}:u\in\tau\\}]$ is $\text{Prob}(\lambda)=\prod_{e\in
E_{P}(\lambda)}(1-\rho_{e})$.

This definition is derived from the fact that $\tau$ will remain connected
only if all physical links utilized by the routings of $\tau$ are not
disconnected.

We let $\mathcal{T}=\\{\lambda_{i}\\}$ be a set of protecting spanning trees
and
$E^{C}_{P}(\mathcal{T})=\cap_{\lambda_{i}\in\mathcal{T}}E^{C}_{P}(\lambda_{i})$
be the common physical links utilized by the routings of
$\lambda_{i}\in\mathcal{T}$. We use Fig. 1 as an instance to illustrate the
concept of protecting spanning tree set and how it can be use to improve
survivable probability. Given $G_{L}$ (top), $G_{P}$ (bottom), and
$\rho_{e},e\in E_{P}$ (noted on each physical link). We select a set of two
protecting spanning trees: (red tree)
$\lambda_{1}=[\\{(2,1),(1,3),(3,4)\\},\\{\\{(1,5),(5,2)\\},\\{(1,4),(4,6),(6,3)\\}$,
$\\{(4,6),(6,3)\\}\\}]$, where
$E_{P}(\lambda_{1})=\\{(1,4)(1,5),(2,5),(3,6),(4,6)\\}$ and the survivable
probability of $\lambda_{1}$ is $(1-0.2)(1-0.1)(1-0.2)(1-0.1)(1-0.1)=0.46656$;
(green tree)
$\lambda_{2}=[\\{(1,2),(2,4),(4,3)\\},\\{\\{(1,5),(5,2)\\},\\{(2,3),(3,6),(6,4)\\}$,
$\\{(4,6),(6,3)\\}\\}]$, where
$V_{P}(\lambda_{2})=\\{(1,5),(2,3),(2,5),(3,6),(4,6)\\}$ and the survivable
probability of $\lambda_{2}=(1-0.1)(1-0.2)(1-0.1)(1-0.1)(1-0.1)=0.52488$. When
considering $\lambda_{1}$ and $\lambda_{2}$ together, the common physical
links used by the routings of both trees are
$E^{C}_{P}(\lambda_{1},\lambda_{2})=\\{(1,5),(2,5),(3,6),(4,6)\\}$. Therefore,
any failure(s) among these links would cause the failure of both $\lambda_{1}$
and $\lambda_{2}$. Hence, the survivable probability of
$[\lambda_{1},\lambda_{2}]=(1-0.1)(1-0.2)(1-0.1)(1-0.1)=0.5832$ which is
higher than that of either $\lambda_{1}$ or $\lambda_{2}$.

Figure 1: Survivable probability with multiple protecting spanning trees

Derived from the example above, we have the following definition.

###### Definition 4

Given $G_{P},G_{L},\rho_{e},e\in E_{P}$, and a protecting spanning tree set
$\mathcal{T}=\\{\lambda_{i}\\}$, the survivable probability of $\mathcal{T}$
is $\text{Prob}(\mathcal{T})=\prod_{e\in E^{C}_{P}(\mathcal{T})}(1-\rho_{e})$.

###### Definition 5

Given $G_{P}$ and $G_{L}$, a base protecting spanning tree set for a cloud
network has the same survivable probability as that of the cloud network.

###  II-A Survivable Probability, Link Mapping, and Base Protecting Spanning
Tree Set

In this section, we explore the relationship among cross-layer networks,
logical link mappings, and protecting spanning tree sets. We then identify a
cross-layer network’s survivable probability based on the base protecting
spanning tree set.

Given a cross-layer network $G_{P}$, $G_{L}$, and cross-layer link mappings
$m(E_{L})=\\{p_{u},p_{u}\in\mathcal{P}_{u},u\in E_{L}\\}$ with
$M(E_{L})=\\{m(E_{L})\\}$. We define and analyze the maximal survivable
probability of a cross-layer network, $\Phi(G_{P},G_{L})$, as follows.

###### Proposition 1

For a given cloud network $G_{P}$, $G_{L}$, and its mappings $M(E_{L})$,
$\Phi(G_{P},G_{L})=\max_{m(E_{L})\in M(E_{L})}\prod_{e\in
R(m(E_{L}))}(1-\rho_{e})$, where $R(m(E_{L}))$ denotes a set of physical links
whose failure(s) disconnect $G_{L}$.

###### Proof:

With Definition 1, survivable probability of a cloud network is determined by
physical links whose failures disconnect the logical network. As the mapping
of logical links decides such physical link set, with logical link mapping set
$M(V_{L})$, $\Phi(G_{P},G_{L})=\max_{m(E_{L})\in M(E_{L})}\prod_{e\in
R(m(E_{L}))}(1-\rho_{e})$. ∎

We let $m^{*}(E_{L})$ denote the logical link mapping with the maximal
survivable probability, i.e., $m^{*}(E_{L})=\arg_{m(E_{L})\in
M(E_{L})}\Phi(G_{P},G_{L})$. Next, we prove the existence of the base
protecting spanning tree set with given $G_{P}$ and $G_{L}$.

###### Proposition 2

Given $G_{P}$, $G_{L}$, and $M(E_{L})$, the base protecting spanning tree set
exists.

###### Proof:

We prove this through two claims: Claim 1: given a logical link mapping
$m(E_{L})\in M(E_{L})$, a physical link is _protected_ by at least one
protecting spanning tree if its failure does not disconnect $G_{L}$; Claim 2:
with the same mapping $m(E_{L})$, a physical link is not protected by any
protecting spanning tree if its failure causes the disconnection of $G_{L}$.

Proof of Claim 1: for $\lambda=[\tau,\\{p_{u}:u\in\tau\\}]$, any single or
multiple link failures in $E_{P}\setminus E_{P}(\lambda)$ do not disconnect
$\tau$. Hence, $\lambda$ guarantees the connectivity of $G_{L}$ after the
failure(s) of link(s) in $E_{P}\setminus E_{P}(\lambda)$.

Proof of Claim 2: proof by contradiction. If the failure of a physical link
causing the disconnection of the logical network can be protected by a
protecting spanning tree, with Claim 1, the logical network should remain
connected after its failure. Contradiction!

With Claims 1 and 2, let a tuple $[\bar{\mathcal{T}},m(E_{L})]$ represent a
protecting spanning tree set and its mappings, where $\bar{\mathcal{T}}$
contains all protecting spanning trees and each tree protects at least one
physical link. $R(m(E_{L}))$ is a set of physical links not protected by trees
in $[\bar{\mathcal{T}},m(E_{L})]$. There exists a mapping
$m^{\prime}(E_{L})\in M(E_{L})$ such that $m^{\prime}(E_{L})=\arg_{m(E_{L})\in
M(E_{L})}\max\prod_{e\in
E^{C}_{P}([\bar{\mathcal{T}},m(E_{L})])}(1-\rho_{e})$. With Claim 2,
$R(m^{\prime}(E_{L}))=E^{C}_{P}([\bar{\mathcal{T}},m^{\prime}(E_{L})])$.
Therefore, with $m^{*}(E_{L})$ as a logical link mapping, there exists a
protecting spanning tree set which has the same survivable probability as that
of the given cross-layer network. The conclusion holds. ∎

We may derive from Proposition 2 the necessary and sufficient conditions of a
base protecting spanning tree set in a cross-layer network as follows.

###### Theorem 1

A protecting spanning tree set is a base protecting spanning tree set if and
only if it provides the maximal survivable probability $\prod_{e\in
E^{C}_{P}(\mathcal{T})}(1-p_{e})$.

###### Proof:

Proof of the necessary condition: given in Proposition 2.
Proof of the sufficient condition by contradiction to Definition 5: if there
exists a protecting spanning tree set with higher survivable probability than
that of the base protecting spanning tree set, it leads to higher cross-layer
survivable probability. Contradiction! ∎

###### Corollary 1

A survivable cross-layer network has 100% survivable probability against
arbitrary physical link failure.

###### Proof:

With Theorem 1 in [21], no common physical links are utilized by a protecting
spanning tree set $\mathcal{T}$, i.e.,
$\bigcap_{u\in\cup_{\lambda\in\mathcal{T}}}p_{u}=\emptyset$. With Definition
1, its survivable probability is 100%. ∎

Proposition 1 indicates that survivable cross-layer networks are a subset of
cross-layer networks with guaranteed 100% survivable probability.

###  II-B Special Case: Unified Physical Link Failure Probability

Unified physical link failure probability considered in this section is a
special case where the failure probability for all physical links is $\rho$.
We first study the maximal protecting spanning tree and have the following
conclusion.

###### Proposition 3

Given $G_{P}$, $G_{L}$, and physical link failure probability $\rho_{e}=\rho$
with $e\in E_{P}$, the maximal protecting spanning tree is a protecting
spanning tree with the minimal number of physical links utilized in its
branches’ routes.

###### Proof:

Based on Definition 3, the maximal survivable probability $=\max\prod_{e\in
E_{P}(\lambda)}(1-\rho_{e})$ $=\max(1-\rho)^{|E_{P}(\lambda)|}$ (with unified
physical link failure probability $\rho$), which is equivalent to
$\min|E_{P}(\lambda)|$. ∎

###### Theorem 2

Given $G_{P}$, $G_{L}$, and unified failure probability $\rho$, a base
protecting spanning tree set with $\min|E^{C}_{P}(\mathcal{T})|$ has
survivable probability $(1-\rho)^{\min|E^{C}_{P}(\mathcal{T})|}$.

###### Proof:

Derived from Proposition 3, given unified failure probability $\rho$, $G_{L}$
is disconnected if one or multiple physical links commonly used by the
routings of $\lambda\in\mathcal{T}$ fail. Thus, $\min|E^{C}_{P}(\mathcal{T})|$
also leads to the maximal survivable probability. Therefore, the conclusion
holds. ∎

Based on Theorem 2, the estimation of cross-layer network survivability with
unified failure probability is equivalent to solving a cross-layer network
design problem targeting the minimal number of shared physical links in its
logical link mappings. The above proof also demonstrates that a base
protecting spanning tree set and its mappings can provide a (partially)
survivable network design along with a more precise evaluation metric on its
survivability.

Compared with the cross-layer network reliability problem considered in [25]
where the reliability is approximated through enumerating exponential number
of cross-layer cutsets and evaluating failure polynomials, the base protecting
spanning tree set can provide exact computation for survivable probability
under both uniform and random physical link failure probability. Theorem 2
further demonstrates that the exact survivable probability problem in cross-
layer networks is equivalent to the cross-layer network routing problem which
guarantees minimal number of shared physical links by protecting spanning
trees in a base protecting spanning tree set.

We wish to point out that with random physical link failure probability, the
minimal cardinality of a set of physical links whose failures disconnect the
logical network may not lead to the same survivable probability of the
original cross-layer network.

##  III Solution Approach

Based on Theorems 1 and 2, we present in this section the mathematical
programming formulations to compute survivable probability of cross-layer
networks and its related problems. We first present the formulation with
unified physical link failure probability as a special case in Section III-A.
Then, the generalized formulation with random physical link failure
probability is presented in Section III-B. Variables and parameters used in
the formulations are listed in Table II.

Variable |  Description
---|---
$x_{ij}$ |  Binary variable indicating whether $(i,j)$’s failure disconnects the logical network. If yes, $x_{ij}=1$; otherwise, $x_{ij}=0$
$y^{st}_{ij}$ |  Binary variable indicating whether logical link $(s,t)$ is routed through physical link $(i,j)$ or not. If yes, $y^{st}_{ij}=1$; otherwise, $y^{st}_{ij}=0$
$z_{st}$ |  Binary variable indicating whether logical link $(s,t)$ is connected and forms a protecting spanning tree. If yes, $z_{st}=1$; otherwise, $z_{st}=0$
$w^{ij}_{st}$ |  Binary variable indicating whether logical link $(s,t)$ is connected and forms a protecting spanning tree after physical link $(i,j)$ fails. If yes, $w^{ij}_{st}=1$; otherwise, $w^{ij}_{st}=0$
$g_{ij}$ |  Binary variable indicating whether physical link $(i,j)$ is shared by trees in a base protecting spanning tree set. If yes, $g_{ij}=1$; otherwise, $g_{ij}=0$
Parameter |  Description
$c_{ij}$ |  The coefficient for physical link. With unified failure probability, $c_{ij}=1$; with random physical link failure probability, $c_{ij}=\ln(1-\rho_{ij})$
TABLE II: Variables and parameters used in mathematical formulations

###  III-A Special Case: Survivable Probability of Cross-layer Networks with
Unified Physical Link Failure Probability

We first present a mixed-integer programming formulation to generate the
maximal protecting spanning tree, followed by a formulation to generate a base
protecting spanning tree set for cross-layer network survivable probability.

####  III-A1 Maximal Protecting Spanning Tree

Given unified physical link failure probability $\rho$, _MaxPrctTree_ is a
mixed integer programming formulation with the objective to minimize the
number of physical links utilized by tree branches’ routings (based on
Proposition 3).

$\displaystyle\min_{x,y,z}\sum_{(i,j)\in E_{P}}x_{ij}$ $\displaystyle s.t.$
$\displaystyle\sum_{(i,j)\in E_{P}}y^{st}_{ij}-\sum_{(j,i)\in
E_{P}}y^{st}_{ji}=\left\\{\begin{matrix}z_{st},&\,\mbox{if }i=s,\\\
-z_{st},&\,\mbox{if }i=t,\\\ 0,&\,\mbox{if
}i\neq\\{s,t\\},&\end{matrix}\right.$ (1) $\displaystyle
y^{st}_{ij}+y^{st}_{ji}\leq x_{ij},(s,t)\in E_{L},(i,j)\in E_{P}$ (2)
$\displaystyle\sum_{(s,t)\in E_{L}}z_{st}-\sum_{(t,s)\in
E_{L}}z_{ts}=\left\\{\begin{matrix}|V_{L}|-1,\text{if}s=s_{0}\\\
-1,\text{if}s\neq s_{0},s\in V_{L}&\end{matrix}\right.$ (3)
$\displaystyle\sum_{(s,t)\in E_{L}}z_{st}=|V_{L}|-1,(i,j)\in E_{P}$ (4)
$\displaystyle x_{ij},y^{st}_{ij},z_{st}\in\\{0,1\\},(s,t)\in E_{L},(i,j)\in
E_{P}$ (5)

Constraint (1) maps logical links onto physical paths and forms a logical
spanning tree, in which $z_{st}$ on the right hand side indicates whether
$(s,t)$ is a branch of a logical spanning tree or not. Constraint (2)
indicates which physical links are utilized by the routings of a selected
protecting spanning tree. Constraints (3) and (4) form a protecting spanning
tree corresponding to the logical link mapping generated by constraint (1).
Constraint (5) provides the feasible regions for all decision variables.

####  III-A2 Base Protecting Spanning Tree Set

Extended from the _MaxPrctTree_ formulation, we present the mixed-integer
programming formulation _BasePrctTree_ to compute a cross-layer network’s
survivable probability with unified physical link failure probability. With
Theorems 1 and 2, the mixed-integer programming formulation has the objective
to minimize the total number of physical links shared by protecting spanning
trees.

$\displaystyle\min_{y,g}$ $\displaystyle\sum_{(i,j)\in E_{P}}g_{ij}$
$\displaystyle\ s.t.$ $\displaystyle\sum_{(i,j)\in
E_{P}}y^{st}_{ij}-\sum_{(j,i)\in
E_{P}}y^{st}_{ji}=\left\\{\begin{matrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1},&\,\mbox{if
}i=s,\\\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-1},&\,\mbox{if
}i=t,\\\ 0,&\,\mbox{if }i\neq\\{s,t\\},&\end{matrix}\right.$ (6)
$\displaystyle w^{ij}_{st}\leq 1-(y^{st}_{ij}+y^{st}_{ji}),(s,t)\in
E_{L},(i,j)\in E_{P}$ (7) $\displaystyle\sum_{(s,t)\in E_{L}}$ $\displaystyle
w^{ij}_{st}-\sum_{(t,s)\in
E_{L}}w^{ij}_{ts}=\left\\{\begin{matrix}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(1-g_{ij})},\qquad\text{if
}s=s_{0}\\\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(g_{ij}-1)/(|V_{L}|-1)},\\\
\qquad\quad\text{if }s\neq s_{0},s\in V_{L}&\end{matrix}\right.$ (8)
$\displaystyle y^{st}_{ij},$ $\displaystyle g_{ij}\in\\{0,1\\},w^{ij}_{st}\geq
0,(s,t)\in E_{L},(i,j)\in E_{P}$ (9)

Similar to constraint (1), constraint (6) generates physical paths for links
of tree branches of a spanning tree in a base protecting spanning tree set.
Constraints (7)–(8) generate a protecting spanning tree after any physical
link’s failure if the physical link is protected; otherwise, the physical link
is identified as unprotected. With the information of unprotected physical
links, the generated protecting spanning trees which protect at least one
physical link are then identified as the base protecting spanning tree set.
Constraint (9) provides the feasible regions for all decision variables.

###  III-B Survivable Probability of Cross-Layer Networks with Random Physical
Link Failure Probability

In this section, we discuss a more generalized and realistic physical link
failure scenario with random failure probability on physical links. With
Definition 5, the objective used to select a base protecting spanning tree set
is as follows:

$\displaystyle\max_{\tau,\mathcal{P}}\prod_{{}_{e\in\cup{u\in\tau}}p_{u}}(1-\rho_{e})$
(10)

The objective (10) is nonlinear. Applying the $\ln$ function on the objective
converts it into linear form as follows:

$\displaystyle\max_{\tau,\mathcal{P}}\sum_{{}_{e\in\cup{u\in\tau}}p_{u}}\ln(1-\rho_{e}).$

The generalized formulation for cross-layer survivable probability is then

$\displaystyle\min_{y,g}$ $\displaystyle\sum_{(i,j)\in E_{P}}c_{ij}g_{ij}.$
$\displaystyle s.t.$ $\displaystyle\text{ Constraints (\ref{fm:lightpath2}) --
(\ref{fm:maxTreeRegion2})}.$ (11)

Here with unified physical link failure probability, $c_{ij}=1$; and with
random physical link failure probability, $c_{ij}=-\ln(1-p_{ij})$. Note here
that since $p_{ij}$ and $1-p_{ij}$ are in (0,1] for all $(i,j)\in E_{P}$, and
$\ln(1-p_{ij})$ is in $(-\infty,0)$. Hence, maximizing negative $ln(1-p_{ij})$
equals to minimizing positive $c_{ij}$.

##  IV Simulation Study

In this section, we present our simulation settings and test cases, experiment
design, and simulation results. The goal is to validate and demonstrate the
efficiency of the proposed base protecting spanning tree set for a cloud
network’s survivable probability.

###  IV-A Simulation Setup

We select NSF as the physical network and create two logical networks denoted
as “LN1” and “LN2”. All networks are illustrated in Figs. 2 and 3. Two cross-
layer network mappings, namely LN1-over-NSF and LN2-over-NSF, are created. We
first apply the mathematical formulations in [20] and verify that LN1-over-NSF
is survivable and LN2-over-NSF is unsurvivable. The reason for choosing these
cases is to show that our approach not only can be applied to solve both cases
but also can produce results with maximal survivable probability when a
survivable routing does not exist.

Figure 2: NSF Figure 3: LN1 and LN2

Physical links are assigned failure probabilities based on (1) 150 uniform
failure probabilities in the range of 15% to 0% (decreased by 0.5% in each
step); and (2) 30 randomly generated failure probabilities with mean in the
range of 15% to 0% and variance 2%, where only failure probabilities above 0%
are selected. For the random failure probability, we report the average
survivable probabilities of _MaxPrctTree_ and _BasePrctTreeSet_ of 5 random
generated failure probability cases.

The formulations are implemented in IBM ILOG CPLEX 12.7.1 and executed on a
Dell Server with 8x AMD Opteron 6366 HE Processors and 256 GB memory. Each
formulation is limited to run for up to 450 seconds, and is terminated if its
running time exceeds the constraint. In general, the simulations on all tested
cases are completed within 1 minute.

###  IV-B Simulation Results

The simulations include two parts: (1) survivable cross-layer networks with
LN1-over-NSF; and (2) unsurvivable cross-layer network with LN2-over-NSF with
uniform and random generated physical link failure probability. For the
survivable cases, the base protecting spanning tree set is capable of
providing 100% survivability. The simulation results illustrated in Fig. 4
show that when the given cross-layer network is survivable, the proposed base
protecting spanning tree set approach can also produce 100% survivable design
with uniform and random physical link failure probabilities.

(a) LN1-over-NSF

(b) LN2-over-NSF

Figure 4: Survivable probability for survivable cross-layer networks

The survivable probability of non-survivable cross-layer network with uniform
and random physical link failure probabilities are shown in Fig. 5. We observe
that the maximal protecting spanning tree and cross-layer survivable
probability monotonically increase when the failure probability decreases.

(a) LN1-over-NSF

(b) LN2-over-NSF

Figure 5: Survivable probability for non-survivable cross-layer networks

Another interesting observation is the relation of the survivable probability
between _MaxPrctTree_ and _BasePrctTreeSet_ , the maximal protecting spanning
tree with a single logical protecting spanning tree providing the lower bound
estimation for the survivable probability. Figure 6 illustrates the ratio
between the survivable probability of _MaxPrctTree_ and _BasePrctTreeSet_. The
results for both survivable and non-survivable networks with uniform and
random physical link failure probabilities demonstrate that the lower the
physical link failure probability, the better the lower bound estimation of
survivable probability the maximal protecting spanning tree can provide. With
up to 15% of the average physical link failure probability, the lower bound
estimation of tested cases is higher than $\frac{1}{2}$ of survivable
probability of cross-layer network in all testing cases.

(a) LN1-over-NSF

(b) LN2-over-NSF

Figure 6: The ratio of survivable probability between _MaxPrctTree_ and
_BasePrctTreeSet_

##  V Conclusion

In this paper, we introduced a new evaluation metric, the survivable
probability, and explored exact solution approaches in the form of
mathematical programming formulations. We evaluated the probability of the
logical network to remain connected against physical link failure(s) with
unified or random failure probabilities. We discussed the relationship of
survivable probability in cross-layer networks and protecting spanning tree
set, which led to the base protecting spanning tree set approach. We proved
the existence of base protecting spanning tree set in a given cross-layer
network and its necessary and sufficient conditions. Our simulation results
show the effectiveness of proposed solution approaches.

## References

  * [1] C. Develder, M. D. Leenheer, B. Dhoedt, M. Pickavet, D. Colle, F. D. Turck, and P. Demeester, “Optical networks for grid and cloud computing applications,” _Proc. IEEE_ , vol. 100, no. 5, pp. 1149–1167, May 2012.
  * [2] M. Chowdhury, M. R. Rahman, and R. Boutaba, “ViNEYard: Virtual network embedding algorithms with coordinated node and link mapping,” _IEEE/ACM Trans. Netw._ , vol. 20, no. 1, pp. 206–219, Feb. 2012. [Online]. Available: http://dx.doi.org/10.1109/TNET.2011.2159308
  * [3] S. Sezer, S. Scott-Hayward, P. K. Chouhan, B. Fraser, D. Lake, J. Finnegan, N. Viljoen, M. Miller, and N. Rao, “Are we ready for SDN? implementation challenges for software-defined networks,” _IEEE Commun. Mag._ , vol. 51, no. 7, pp. 36–43, 2013.
  * [4] ETSI, “Network functions virtualisation (NFV); ecosystem; report on SDN usage in NFV architectural framework,” ETSI, Tech. Rep., 2015. [Online]. Available: http://standards.globalspec.com/std/9979634/etsi-gs-nfv-eve-005
  * [5] J.-M. Kang, T. Lin, H. Bannazadeh, and A. Leon-Garcia, “Software-defined infrastructure and the SAVI testbed,” in _International Conference on Testbeds and Research Infrastructures_. Springer, 2014, pp. 3–13.
  * [6] J.-M. Kang, H. Bannazadeh, and A. Leon-Garcia, “SAVI testbed: Control and management of converged virtual ICT resources,” in _IFIP/IEEE International Symposium on Integrated Network Management (IM)_. IEEE, 2013, pp. 664–667.
  * [7] D. Kreutz, F. M. Ramos, P. E. Verissimo, C. E. Rothenberg, S. Azodolmolky, and S. Uhlig, “Software-defined networking: A comprehensive survey,” _Proc. IEEE_ , vol. 103, no. 1, pp. 14–76, 2015.
  * [8] M. Yang, Y. Li, D. Jin, L. Zeng, X. Wu, and A. V. Vasilakos, “Software-defined and virtualized future mobile and wireless networks: A survey,” _Mobile Networks and Applications_ , vol. 20, no. 1, pp. 4–18, 2015.
  * [9] P. Cholda, “Network recovery, protection and restoration of optical, SONET-SDH, IP, and MPLS [book review],” _IEEE Commun. Mag._ , vol. 43, no. 7, pp. 12–12, 2005.
  * [10] P. E. Heegaard and K. S. Trivedi, “Network survivability modeling,” _Comput. Netw._ , vol. 53, no. 8, pp. 1215–1234, 2009.
  * [11] S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks. part I-protection,” in _Proc. IEEE INFOCOM_ , vol. 2. IEEE, 1999, pp. 744–751.
  * [12] M. Kurant and P. Thiran, “On survivable routing of mesh topologies in IP-over-WDM network,” in _Proc. IEEE INFOCOM_ , vol. 2, 2005, pp. 1106–1116.
  * [13] A. Todimala and B. Ramamurthy, “A scalable approach for survivable virtual topology routing in optical WDM networks,” _IEEE J. Sel. Areas Commun._ , vol. 25, pp. 63–69, 2007.
  * [14] M. Parandehgheibi, H.-W. Lee, and E. Modiano, “Survivable path sets: A new approach to survivability in multilayer networks,” _J. Lightw. Technol._ , vol. 32, no. 24, pp. 4139–4150, 2014.
  * [15] E. Modiano and A. Narula-Tam, “Survivable routing of logical topologies in WDM networks,” in _Proc. IEEE INFOCOM_ , vol. 1, 2001, pp. 348–357.
  * [16] K. Lee, E. Modiano, and H.-W. Lee, “Cross-layer survivability in WDM-based networks,” _IEEE/ACM Trans. Netw._ , vol. 19, no. 4, pp. 1000–1013, 2011\.
  * [17] M. R. Rahman and R. Boutaba, “SVNE: Survivable virtual network embedding algorithms for network virtualization,” _IEEE Trans. Netw. Service Manag._ , vol. 10, no. 2, pp. 105–118, 2013.
  * [18] Z. Ye, A. N. Patel, P. N. Ji, and C. Qiao, “Survivable virtual infrastructure mapping over transport software-defined networks (T-SDN),” in _Optical Fiber Communications Conference and Exhibition (OFC)_. IEEE, 2014, pp. 1–3.
  * [19] ——, “Survivable virtual infrastructure mapping with dedicated protection in transport software-defined networks,” _IEEE J. Opt. Commun. Netw._ , vol. 7, no. 2, pp. A183–A189, 2015.
  * [20] Z. Zhou, T. Lin, and K. Thulasiraman, “Survivable cloud network design against multiple failures through protecting spanning trees,” _J. Lightw. Technol._ , vol. 35, no. 2, pp. 288–298, 2017.
  * [21] Z. Zhou, T. Lin, K. Thulasiraman, and G. Xue, “Novel survivable logical topology routing by logical protecting spanning trees in IP-over-WDM networks,” _IEEE/ACM Trans. Netw._ , no. 3, pp. 1673–1685, 2017.
  * [22] J. Yallouz, O. Rottenstreich, and A. Orda, “Tunable survivable spanning trees,” _ACM SIGMETRICS Performance Evaluation Review_ , vol. 42, no. 1, pp. 315–327, 2014.
  * [23] J. Yallouz and A. Orda, “Tunable QoS-aware network survivability,” _IEEE/ACM Trans. Netw._ , vol. 25, no. 1, pp. 139–149, 2017.
  * [24] Z. Zhou, T. Lin, K. Thulasiraman, G. Xue, and S. Sahni, “Novel survivable logical topology routing in IP-over-WDM networks by logical protecting spanning tree set,” in _Proc. Intl. Congress on Ultra Modern Telecomm. and Control Sys._ , Oct 2012, pp. 650–656.
  * [25] H.-W. Lee, K. Lee, and E. Modiano, “Maximizing reliability in WDM networks through lightpath routing,” _IEEE/ACM Trans. Netw._ , vol. 22, no. 4, pp. 1052–1066, 2014.


Incidence Coalgebras: Automorphisms and Derivations

Piotr Krylov111National Research Tomsk State University, e-mail:
<EMAIL_ADDRESS>., Askar Tuganbaev222National Research University MPEI;
Lomonosov Moscow State University; e-mail<EMAIL_ADDRESS>.

Abstract. We describe automorphisms and derivations of the incidence coalgebra
$\text{Co}(X,F)$ of the partially ordered set $X$ over a field $F$. In this
case, the fact is significantly used that the dual algebra of the coalgebra
$\text{Co}(X,F)$ is isomorphic to the incidence algebra $I(X,F)$ of the
partially ordered set $X$ over the field $F$.

Key words: incidence coalgebra, incidence algebra, automorphism, derivation.

MSC2020 database 16T15, 16W25

The study is supported by grants of Russian Science Foundation (=RSF), no.
23-21-00375, https://rscf.ru/en/project/23-21-00375/ (P.A. Krylov) and no.
22-11-00052, https://rscf.ru/en/project/22-11-00052 (A.A. Tuganbaev).

###### Contents

  1. 1 Introduction
  2. 2 Coalgebras and Dual Algebras
  3. 3 Algebra Dual to Coalgebra $\text{Co}(X,F)$ and Incidence Algebra $I(X,F)$
  4. 4 On Group $\text{Aut}(I(X,F))$
  5. 5 Group $\text{Aut }C$
  6. 6 Two Subgroups in $\text{Aut }C$
  7. 7 Inner Automorphisms of Coalgebra $\text{Co}(X,F)$
  8. 8 Structure of Group $\text{Aut }C$
  9. 9 On Spaces $\text{Der }(I(X,F))$
  10. 10 Derivation Space $\text{Der }C$
  11. 11 Inner Derivations of Coalgebra $\text{Co}(X,F)$
  12. 12 Description of Derivation Space $\text{Der }C$

##  1 Introduction

In this paper, for a partially ordered set $X$ and a field $F$, we study
automorphisms and derivations of the incidence coalgebra $\text{Co}(X,F)$ of
$X$ over $F$. It is known that the algebra dual to the coalgebra
$\text{Co}(X,F)$ is canonically isomorphic to the incidence algebra $I(X,F)$
of the partially ordered set $X$ over a field $F$. The theory of incidence
algebras and coalgebras is presented in the book [7]. For more information, we
can refer to papers [1] and [6] which also contain a variety of material on
arbitrary coalgebras.

The structure of the automorphism group and the derivation space of the
incidence algebra $I(X,F)$ has been clarified quite a long time ago. The
corresponding results are presented in [7]. Subsequently, these results were
transferred and generalized in a fairly large number of papers to more general
incidence rings $I(X,R)$ , where $X$ is a pre-ordered set and $R$ is some ring
(e.g., see [2], [3], [4]). In a number of articles, rings that are close in
different senses to ordinary incidence rings were introduced and studied
(e.g., see [5] and [6]).

Under the study of automorphisms and derivations, we pass from the coalgebra
$\text{Co}(X,F)$ to the algebra $I(X,F)$, and conversely. However, the reverse
transition is difficult. In the general case, it is impossible to return from
the algebra $I(X,F)$ to the coalgebra $\text{Co}(X,F)$ in any standard way. At
the same time, it is important that automorphisms and derivations of the
coalgebra $\text{Co}(X,F)$ induce automorphisms and derivations of the dual
algebra and the algebra $I(X,F)$, respectively.

We denote the automorphism group of the partially ordered set $X$ by
$\text{Aut }X$. For any two elements $x,y\in X$, we denote by $[x,y]$ the
subset $\\{z\in X\,|\,x\leq z\leq y\\}$. It is called an interval in $X$.
Further, we assume that all intervals in $X$ are finite. In such a case, $X$
is called a locally finite partially ordered set.

If $V$ is a linear space over a field $F$ (an $F$-space, for brevity), then
$V^{*}$ is the dual space of $V$, i.e. $V^{*}=\text{Hom}_{F}(V,F)$. Further,
$\text{End}_{F}V$ denotes the endomorphism ring (i.e. the ring of linear
operators) of the space $V$ and $\text{Aut}_{F}V$ denotes the automorphism
group (i.e. the group of invertible linear operators) of the space $V$. The
role of the space $V$ is played either some algebra $A$ or the coalgebra $C$
and its dual algebra $C^{*}$.

Let $A$ be an algebra over a field $F$ (briefly, an $F$-algebra). Then
$\text{Aut }A$ is the automorphism group of the algebra $A$, $\text{In(Aut
}A)$ is the group of inner automorphisms, $\text{Der }A$ is the derivation
space of the algebra $A$ and $\text{In(Der }A)$ is a subspace of inner
derivations. The automorphism group of the coalgebra $C$ is also denoted by
$\text{Aut }C$.

For groups $G$ and $H$, we denote the semidirect product of $G$ and $H$ by
$G\leftthreetimes H$.

## Chapter I.
SUPPORTING RESULTS

##  2 Coalgebras and Dual Algebras

Let $(C,\Delta,\varepsilon)$ be some coalgebra over a field $F$. Thus, $C$ is
an $F$-space, $\Delta$ is a comultiplication in $C$, $\varepsilon$ is a counit
for $C$. We use the letter $C$ to denote this coalgebra.

We can naturally define the linear mappings $m\colon C^{*}\otimes C^{*}\to
C^{*}$ and $u\colon F\to C^{*}$ in such a way that we get the resulting
$F$-algebra $C^{*}=(C^{*},m,u)$. It is called the dual algebra for the
coalgebra $C$. The identity element of the algebra $C^{*}$ is a counit
$\varepsilon$. We remark that if $C$ is a finite-dimensional space, then the
duality also exists in the opposite direction.

We elaborate a little on what has just been said. The multiplication $m\colon
C^{*}\otimes C^{*}\to C^{*}$ is induced by the comultiplication $\Delta$.
Namely, let $\rho\colon C^{*}\otimes C^{*}\to(C\otimes C)^{*}$ be the
canonical monomorphism, where

$(\rho(\chi\otimes\xi))(c\otimes d)=\chi(c)\xi(d)$

for all $\chi,\xi\in C^{*}$ and $c,d\in C$. We set $m=\Delta^{*}\rho$, where
$\Delta^{*}\colon(C\otimes C)^{*}\to C^{*}$ is the induced mapping and
$\Delta^{*}(\theta)=\theta\Delta$ for $\theta\in(C\otimes C)^{*}$. Further, we
denote by $\omega$ the canonical isomorphism $F\otimes F\to F$. Then
$\rho(\chi\otimes\xi)=\omega\cdot(\chi\otimes\xi)$ for $\chi,\xi\in C^{*}$.

Let $c\in C$ and $\Delta(c)=\sum_{i}a_{i}\otimes b_{i}$, $a_{i},b_{i}\in C$.
We have the relations

$(m(\chi\otimes\xi))(c)=(\Delta^{*}\rho(\chi\otimes\xi))(c)=(\rho(\chi\otimes\xi)\Delta)(c)=(\omega\cdot(\chi\otimes\xi)\Delta)(c)=$
$=(\omega\cdot(\chi\otimes\xi))(\sum_{i}a_{i}\otimes
b_{i})=\omega(\sum_{i}\chi(a_{i})\otimes\xi(b_{i}))=\sum_{i}\chi(a_{i})\xi(b_{i}).$

We denote by $\chi\circ\xi$ the element $m(\chi\otimes\xi)$. In the following
lemma, the multiplication rule in the algebra $C^{*}$ is given.

Lemma 2.1. Let $\chi,\xi\in C^{*}$. Further, let $c\in C$ and
$\Delta(c)=\sum_{i}a_{i}\otimes b_{i}$, where $a_{i},b_{i}\in C$. Then we have

$(\chi\circ\xi)(c)=\sum_{i}\chi(a_{i})\xi(b_{i}).$

We denote by $\Gamma$ the mapping $\text{End}_{F}C\to\text{End}_{F}C^{*}$,
where $\Gamma(\varphi)=\varphi^{*}$ for every $\varphi\in\text{End}_{F}C$.
Here $\varphi^{*}$ is a linear mapping of the space $C^{*}$ induced by
$\varphi$, i.e. $\varphi^{*}(\chi)=\chi\varphi$ for every $\chi\in C^{*}$. If
$\varphi\in\text{Aut}_{F}C$, then it is clear that
$\varphi^{*}\in\text{Aut}_{F}C^{*}$.

We write down the following useful fact.

Lemma 2.2. The mapping $\Gamma$ is an antimonomorphism of $F$-algebras
$\text{End}_{F}C\to\text{End}_{F}C^{*}$ and a group antimonomorphism
$\text{Aut}_{F}C\to\text{Aut}_{F}C^{*}$.

Everywhere else $X$ is some locally finite partially ordered set. Let $C$ be a
linear space such that its basis consists of all intervals $[x,y]$ of the set
$X$. We define mappings $\Delta\colon C\to C\otimes C$ and $\varepsilon\colon
C\to F$ by setting

$\Delta([x,y])=\sum_{x\leq z\leq y}[x,z]\otimes[z,y],$
$\varepsilon([x,y])=\begin{cases}1,\text{if }x=y;\\\ 0,\text{if }x\neq
y\end{cases}$

for every interval $[x,y]$.

The triple $(C,\Delta,\varepsilon)$ is a coalgebra which is called the
incidence coalgebra of the locally finite partially ordered set $X$. We denote
it by $\text{Co}(X,F)$ or, like before, by the letter $C$.

##  3 Algebra Dual to Coalgebra $\text{Co}(X,F)$ and Incidence Algebra
$I(X,F)$

Sometimes we denote an incidence algebra $I(X,F)$ by the letter $A$. The
incidence coalgebra $\text{Co}(X,F)$ is denoted by $C$, as agreed at the end
of the previous section. We reveal the connections between the algebras
$C^{*}$ and $A$.

There are mutually inverse isomorphisms of $F$-algebras

$\Phi\colon C^{*}\to A\text{ and }\Psi\colon A\to C^{*},$ $\text{where
}\,(\Phi(\chi))(x,y)=\chi([x,y]),\;\chi\in C^{*},$
$(\Psi(f))([x,y])=f(x,y),\;f\in A,$

for all $x,y\in X$ with $x\leq y$.

In its turn, $\Phi$ and $\Psi$ induce mutually inverse isomorphisms of
algebras of linear mappings

$\Phi^{*}\colon\text{End}_{F}C^{*}\to\text{End}_{F}A,$
$\Psi^{*}\colon\text{End}_{F}A\to\text{End}_{F}C^{*},$ $\text{where
}\,\Phi^{*}(\eta)=\Phi\eta\Psi,\;\eta\in\text{End}_{F}C^{*},$
$\Psi^{*}(\xi)=\Psi\xi\Phi,\;\xi\in\text{End}_{F}A.$

We denote by $\Theta$ the antimonomorphism
$\Psi^{*}\Gamma\colon\text{End}_{F}C\to\text{End}_{F}A$ of algebras (see Lemma
2.2). Let’s find out how $\Theta$ works; this is very useful. For arbitrary
$\varphi\in\text{End}_{F}C$ and $f\in A$, we can write down the relations

$(\Theta(\varphi))(f)=((\Phi^{*}\Gamma)(\varphi))(f)=(\Phi^{*}(\Gamma(\varphi)))(f)=((\Phi\Gamma(\varphi))\Psi)(f)=$
$=\Phi(\Gamma(\varphi)(\Psi(f)))=\Phi(\Psi(f)\varphi),\text{ where
}\Psi(f)\varphi\in C^{*}.$

For any two elements $x,y\in X$ with $x\leq y$, we have the relation

$\Phi(\Psi(f)\varphi)(x,y)=\Psi(f)(\varphi([x,y])).$

As a result, we obtain the relation

$((\Theta(\varphi))(x,y)=\Psi(f)(\varphi([x,y])).$

Further, if

$\varphi([x,y])=\alpha_{1}[x_{1},y_{1}]+\ldots+\alpha_{k}[x_{k},y_{k}],\,\text{
where }\alpha_{i}\in F,$

then the relations

$\Psi(f)(\varphi([x,y]))=\alpha_{1}\Psi(f)([x_{1},y_{1}])+\ldots+\alpha_{k}\Psi(f)([x_{k}y_{k}])=$
$=\alpha_{1}f(x_{1},y_{1})+\ldots+\alpha_{k}f(x_{k},y_{k})$

hold.

Thus,, we can write down the following proposition.

Proposition 3.1. Let $\varphi\in\text{End}_{F}C$, $f\in I(X,F)$, $[x,y]$ is an
interval in $X$. There are assertions below.

  1. 1.

The relation

$((\Theta(\varphi))(f))(x,y)=\Psi(f)(\varphi([x,y])).$

is true. In particular, we obtain the relation

$\Psi(f)([x,y])=f(x,y)\quad\text{(for }\varphi=1).$

  2. 2.

If $\varphi([x,y])=\alpha_{1}[x_{1},y_{1}]+\ldots+\alpha_{k}[x_{k},y_{k}]$,
$\alpha_{i}\in F$, then the relation

$((\Theta(\varphi))(f))(x,y)=\alpha_{1}f(x_{1},y_{1})+\ldots+\alpha_{k}f(x_{k},y_{k})$

holds.

We also obtain the following relations related to multiplication in the dual
algebra $C^{*}$. Of course, they are consistent with Lemma 2.1. Namely, for
arbitrary functions $f,g\in A$ and an interval $[x,y]$, we have

$(\Psi(f)\circ\Psi(g))([x,y])=(\Psi(fg))([x,y])=fg([x,y])=\sum_{x\leq z\leq
y}f(x,z)g(z,y).$

##  4 On Group $\text{Aut}(I(X,F))$

We put together some information about the incidence algebra $I(X,F)$ and its
automorphism group (see [4] and [7] for details). Similar to the previous
section, the algebra $I(X,F)$ is also denoted by the letter $A$. For the
automorphism group of the partially ordered set $X$, we use the symbol
$\text{Aut }X$.

We recall some special functions in $I(X,F)$. For a given element $x\in X$, we
set $e_{x}(x,x)=1$ and $e_{x}(z,y)=0$ for all remaining pairs $(z,y)$. The
system $\\{e_{x}\,|\,x\in X\\}$ consists of pairwise orthogonal idempotents in
the ring $L_{1}$ (the last ring is defined in the next paragraph).

We define a subring $L_{1}$ and an ideal $M_{1}$ in $A$. We set

$\begin{cases}L_{1}=\\{f\in A\,|\,f(x,y)=0,\;\text{if }x\neq y\\},\\\
M_{1}=\\{f\in A\,|\,f(x,y)=0,\;\text{if }x=y\\}.\end{cases}$

We have a direct sum $A=L_{1}\oplus M_{1}$ of $F$-spaces. Therefore, the
algebra $A$ is a splitting extension of the ideal $M_{1}$ with the use of the
subring $L_{1}$. The ideal $M_{1}$ can be considered as an
$L_{1}$-$L_{1}$-bimodule and a non-unital algebra, as well.

Let we have an arbitrary element $x\in X$. We denote by $R_{x}$ the set of all
functions $f\in A$ such that $f(z,y)=0$ for $(z,y)\neq(x,x)$. The relations
$R_{x}=e_{x}Ae_{x}=e_{x}L_{1}e_{x}$ hold. Consequently, $R_{x}$ is a ring with
identity element $e_{x}$. More precisely, $R_{x}\cong F$.

Now we take two distinct elements $x,y$ and we set

$M_{xy}=\\{f\in A\,|\,f(s,t)=0,\,\text{ if }\,(s,t)\neq(x,y)\\}.$

Here $M_{xy}=e_{x}Ae_{y}$ and, therefore, $M_{xy}$ is an
$R_{x}$-$R_{y}$-bimodule. The relation $M_{xy}=e_{x}M_{1}e_{y}$ is also true;
in addition, $M_{xy}\cong F$.

The product $\prod_{x,y\in X}M_{xy}$ has a natural structure of an
$L_{1}$-$L_{1}$-bimodule. In this bimodule, we also can define a
multiplication by the use of the relation

$(g_{xy})(h_{xy})=(d_{xy}),\quad\text{where }\,d_{xy}=\sum_{x\leq z\leq
y}g_{xz}h_{zy}.$

Thereafter, the product $\prod_{x,y\in X}M_{xy}$ becomes a (non-unital)
algebra.

Proposition 4.1 [4, Proposition 3.1]. There are canonical algebra isomorphisms
$L_{1}\cong\prod_{x\in X}R_{x}$, $M_{1}\cong\prod_{x,y\in X}M_{xy}$ and a
canonical $L_{1}$-$L_{1}$-bimodule isomorphism $M_{1}\cong\prod_{x,y\in
X}M_{xy}$.

Let $\varphi$ be an arbitrary automorphism of the algebra $A$. Based on the
direct sum $A=L_{1}\oplus M_{1}$ of $F$-spaces, we can associate with the
automorphism $\varphi$ $2\times 2$ the matrix
$\left(\begin{smallmatrix}\alpha&\gamma\\\
\delta&\beta\end{smallmatrix}\right)$. In addition, $\gamma=0$ in our case
(see [4, Proposition 3.1]). Further, $\alpha$ is an automorphism of the
algebra $L_{1}$ and $\beta$ is an automorphism of the (non-unital) algebra
$M_{1}$. If $\delta=0$, then $\beta$ also is an automorphism of an
$L_{1}$-$L_{1}$-bimodule $M_{1}$.

Let $v$ be some invertible element of the algebra $A$. With the use of it, we
can obtain an automorphism $\mu_{v}$ of this algebra if we set
$\mu_{v}(f)=v^{-1}fv$ for every $f\in A$. Such an automorphism is called the
inner automorphism determined by the element $v$. All inner automorphisms form
a normal subgroup $\text{In(Aut }A)$ in $\text{Aut }A$. In our case, it is
useful to detail the defined notion as done in [4]. $\text{In}_{1}(\text{Aut
}A)$ (resp., $\text{In}_{0}(\text{Aut }A)$) are denoted by subgroup of inner
automorphisms determined by invertible elements of the form $1+g$, $g\in
M_{1}$ (resp., determined by invertible elements of the algebra $L_{1}$). The
first subgroup is normal in $\text{Aut }A$ and we have a semidirect
decomposition

$\text{In(Aut }A)=\text{In}_{1}(\text{Aut
}A)\leftthreetimes\text{In}_{0}(\text{Aut }A).$

In addition to $\text{In(Aut }A)$, we define two more subgroups of the group
$\text{Aut }A$.

We denote by $\text{Mult }A$ the subgroup of $\text{Aut }A$ consisting of the
automorphisms of the form $\left(\begin{smallmatrix}1&0\\\
0&\beta\end{smallmatrix}\right)$. Such automorphisms are said to be
multiplicative. Let’s approach their definition a little differently.

Definition 4.2. Let we have a system of non-zero elements $\\{c_{xy}\in
F\,|\,x<y\\}$ satisfying the relation

$c_{xy}=c_{xz}c_{zy}\;\text{ such that }\;x<z<y.$ $None$

The systems of elements defined in Definition 4.2 are called multiplicative
systems. It was possible to define a multiplicative system as a system
$\\{c_{xy}\,|\,x\leq y\\}$, where $c_{xx}=1$ for all $x$ and
$c_{xy}=c_{xz}c_{zy}$ such that $x\leq z\leq y$.

Let $\psi\in\left(\begin{smallmatrix}1&0\\\
0&\beta\end{smallmatrix}\right)\in\text{ Mult }A$. For any two elements $x,y$
with $x<y$, there exists a non-zero element $c_{xy}$ of the field $F$ such
that the relation $\beta(g)=c_{xy}g$ is true for all $g\in M_{xy}$. In
addition, the system $\\{c_{xy}\,|\,x<y\\}$ satisfies to the relation $(1)$
(see the paragraph before [4, Proposition 10.2]). Thus, we can associate the
automorphism $\psi$ with the multiplicative system $\\{c_{xy}\,|\,x<y\\}$.
Conversely, every multiplicative system $\\{c_{xy}\,|\,x<y\\}$ determines a
multiplicative automorphism $\psi$. Namely, for an element $g=(g_{xy})\in
M_{1}$, we set $\psi(g)=(c_{xy}g_{xy})$ and $\psi(f)=f$ for $f\in L_{1}$.

We can write down the following fact [4, Proposition 10.2].

Proposition 4.3. There is a one-to-one correspondence between multiplicative
automorphisms and multiplicative systems of elements.

We consider another type of automorphisms. Let $\tau\in\text{Aut }X$. We
define a mapping $\eta_{\tau}\colon A\to A$ by setting

$\eta_{\tau}(f)(x,y)=f(\tau(x),\tau(y))\;\text{ for all }f\in A,\;x,y\in X.$

Here $\eta_{\tau}$ is an automorphism of the algebra $A$ and the
correspondence $\tau\to\eta_{\tau}$ is an antiisomorphic embedding
$p\colon\text{Aut }X\to\text{Aut }A$ of groups. We identify $\tau$ with
$\eta_{\tau}$ using the mapping $p$. The automorphisms of the form
$\eta_{\tau}$ are called order automorphisms. The image of the embedding $p$
is denoted by $\text{Aut}_{A}X$.

We give the main result about the structure of the group $\text{Aut }A$. It is
contained in [7, Theorem 7.3.6]. Some its generaizations and clarification are
obtained in [4, Corollary 9.4]).

Theorem 4.4. There are the following relations of groups

$\text{Aut }A=(\text{In(Aut }A)\cdot\text{Mult
}A)\leftthreetimes\text{Aut}_{A}X=$ $=\text{In}_{1}\text{(Aut
}A)\leftthreetimes\text{Mult }A\leftthreetimes\text{Aut}_{A}X.$

## Chapter II. AUTOMORPHISM GROUP
OF INCIDENCE COALGEBRAS

##  5 Group $\text{Aut }C$

Let $C=(C,\Delta,\varepsilon)$ and
$C^{\prime}=(C^{\prime},\Delta^{\prime},\varepsilon^{\prime})$ be two
arbitrary coalgebras over a field $F$. A linear mapping $\varphi\colon C\to
C^{\prime}$ is called a homomorphism from the coalgebra $C$ into the coalgebra
$C^{\prime}$ provided that
$(\varphi\otimes\varphi)\Delta=\Delta^{\prime}\varphi$ and
$\varepsilon^{\prime}\varphi=\varepsilon$.

If $\varphi\colon C\to C$ is a homomorphism of coalgebras and $\varphi$ is a
bijection, then $\varphi$ is called an automorphism of the coalgebra $C$. All
automorphisms of the coalgebra $C$ form a group with respect to composition.
It is denoted by $\text{Aut }C$ and is called the automorphism group of the
coalgebra $C$. Certainly, $\text{Aut }C$ is a subgroup in the group
$\text{Aut}_{F}C$.

We recall that $\text{Aut }C^{*}$ is the automorphism group of the dual
algebra $C^{*}$ (see Section 2).

Lemma 5.1. If $\varphi\in\text{Aut }C$, then $\varphi^{*}\in\text{Aut }C^{*}$.

Proof. First of all, we have to verify that the relation
$\varphi^{*}m=m(\varphi^{*}\otimes\varphi^{*})$ holds. Since $\varphi$ is an
automorphism of the coalgebra $C$, the relation
$\Delta\varphi=(\varphi\otimes\varphi)\Delta$ holds. We also have the
relations

$\varphi^{*}m=\varphi^{*}\Delta^{*}\rho=\Delta^{*}(\varphi\otimes\varphi)^{*}\rho.$

On the other hand, the relation
$m(\varphi^{*}\otimes\varphi^{*})=\Delta^{*}\rho(\varphi^{*}\otimes\varphi^{*})$
is true. With use of simple calculations, it is easy to verify that the
relation $(\varphi\otimes\varphi)^{*}\rho=\rho(\varphi^{*}\otimes\varphi^{*})$
is true, which is required.

The identity element of $C^{*}$ is $\varepsilon$. It follows from the relation
$\varepsilon\varphi=\varepsilon$ that
$\varphi^{*}(\varepsilon)=\varepsilon\varphi=\varepsilon$, i.e. $\varphi^{*}$
maps the identity element to the identity element. It is clear that
$\varphi^{*}$ is a bijection. Consequently, $\varphi^{*}$ is an automorphism
of the algebra $C^{*}$. $\square$

##  6 Two Subgroups in $\text{Aut }C$

Until the end of the chapter, $C$ is an incidence coalgebra $\text{Co}(X,F)$
and $A$ is the incidence algebra $I(X,F)$. For the algebra $A$, we define
analogues of matrix units. Let $x,y\in X$ with $x<y$. We denote by $e_{xy}$ a
function $X\times X\to R$ such that $e_{xy}(s,t)=1$ if $s=x$, $t=y$, and
$e_{xy}(s,t)=0$ for all other pairs $(s,t)$. The functions $e_{xy}$ satisfy
the following property:

$\text{if }x<z<y,\text{ then }e_{xz}e_{zy}=e_{xy}.$

In view of Lemmas 2.2, 5.1 and the material in Section 3, we have group
antimonomorphisms

$\Gamma\colon\text{Aut }C\to\text{Aut }C^{*}\text{ and
}\;\Theta\colon\text{Aut }C\to\text{Aut }A.$

Now we define subgroups in $\text{Aut }C$ which are similar to the subgroups
$\text{Mult }A$ and $\text{Aut}_{A}X$ in $\text{Aut }A$ from Section 4.

Let we have a multiplicative system of elements $\\{d_{xy}\,|\,x<y\\}$
(similar systems appeared in Section 4). We define a mapping $\lambda\colon
C\to C$ by setting $\lambda([x,y])=d_{xy}[x,y]$ for every basis vector $[x,y]$
($x<y$) of the space $C$, and $\lambda([x,x])=[x,x]$ for every vector $[x,x]$.
We can naturally extend $\lambda$ to a linear mapping of the space $C$. It is
easy to verify that $\lambda$ is an automorphism of the coalgebra $C$. We call
it the multiplicative automorphism corresponding to the multiplicative system
$\\{d_{xy}\,|\,x<y\\}$.

All multiplicative automorphisms of the coalgebra $C$ form a subgroup in
$\text{Aut }C$ which is denoted by $\text{Mult }C$.

Proposition 6.1. The groups $\text{Mult }C$ and $\text{Mult }A$ are isomorphic
and the isomorphism carried out by the mapping $\Theta$.

Proof. First, we remark that the groups $\text{Mult }A$ and $\text{Mult }C$
are Abelian.

Let $\lambda\in\text{Mult }C$ and let $\\{d_{xy}\,|\,x<y\\}$ be the
corresponding multiplicative system. We have $\lambda([x,y])=d_{xy}[x,y]$ for
all basis vectors $[x,y]$ of the space $C$ (we can assume that $d_{xx}=1$ for
all vectors of the form $[x,x]$). With the use of Proposition 3.1 for any pair
$(s,t)$ with $s\leq t$, we can write down the relations

$((\Theta(\lambda))(e_{xy}))(s,t)=d_{st}e_{xy}(s,t)=\begin{cases}d_{xy},\,\text{
if }(s,t)=(x,y);\\\ 0,\,\text{ if }(s,t)\neq(x,y).\end{cases}$

Therefore, we obtain $(\Theta(\lambda))(e_{xy})=d_{xy}e_{xy}$. We conclude
that $\Theta(\lambda)$ is a multiplicative automorphism of the algebra $A$
corresponding to the system $\\{d_{xy}\,|\,x<y\\}$ (we have also take into
account Proposition 4.3). Therefore, $\Theta(\lambda)\in\text{Mult }A$.

Now we take some automorphism $\psi\in\text{Mult }A$. Let $\psi$ correspond to
the multiplicative system $\\{c_{xy}\,|\,x<y\\}$ from Proposition 4.3. We
denote by $\delta$ the multiplicative automorphism of the coalgebra $C$
corresponding to the system $\\{c_{xy}\,|\,x<y\\}$. It follows from the
previous paragraph that $\Theta(\delta)=\psi$. It can be argued that the
restriction of $\Theta$ to $\text{Mult }C$ maps from $\text{Mult }C$ onto
$\text{Mult }A$ and, therefore, is an isomorphism $\text{Mult }C\to\text{Mult
}A$. $\square$

Now we consider an analogue of order automorphisms for the coalgebra $C$. Let
we have an automorphism $\tau$ of a partially ordered set $X$. We define a
mapping $\tau\colon C\to C$ (we use the same symbol $\tau$ to designate it) by
setting $\tau([x,y])=[\tau(x),\tau(y)]$ for every basis vector $[x,y]$. We
obtain a linear mapping $\tau$ of the space $C$ with converse mapping
$\tau^{-1}$. More precisely, $\tau$ is an automorphism of the coalgebra $C$.

We also define a group monomorphism $q\colon\text{Aut }X\to\text{Aut }C$,
where $q(\tau)=\tau$, $\tau\in\text{Aut }X$. The image of the mapping $q$ is
denoted by $\text{Aut}_{C}X$. After Proposition 4.3, the group
antimonomorphism $p\colon\text{Aut }X\to\text{Aut }A$ appeared.

Proposition 6.2. 1. The relation $\Theta q=p$ is true.

2. The mapping $\Theta$ is a group antiisomorphism $\text{Aut}_{C}X\to\text{Aut}_{A}X$.

Proof. 1. Let $\tau\in\text{Aut }X$, $f\in A$, and let $x,y\in X$ with $x<y$.
We clarify that

$((p(\tau))(f))(x,y)=f(\tau(x),\tau(y)),\quad
q(\tau)([x,y])=[\tau(x),\tau(y)].$

By the use of Proposition 3.1, we now write down the relations

$(((\Theta
q)(\tau))(f))(x,y)=((\Theta(q(\tau)))(f))(x,y)=f(\tau(x),\tau(y))=((p(\tau))(f))(x,y).$

Therefore, $\Theta q=\rho$.

2. The assertion directly follows from 1. $\square$

With use of Proposition 6.2, we obtain the relation $\Gamma q=\Psi^{*}p$, as
well; see Section 3.

##  7 Inner Automorphisms of Coalgebra $\text{Co}(X,F)$

We introduce the notion of an inner automorphism of the coalgebra. The purpose
of the section is to verify that the group of inner automorphisms of the
coalgebra $\text{Co}(X,F)$ is antiisomorphic to the group of inner
automorphisms of the algebra $I(X,F)$.

For a while let $C$ be an arbitrary coalgebra.

Definition 7.1. An automorphism $\nu$ of the coalgebra $C$ is said to be inner
if $\nu^{*}$ is an inner automorphism of the dual algebra $C^{*}$.

All inner automorphisms of the coalgebra $C$ form a normal subgroup in
$\text{Aut }C$ which is denoted by $\text{In(Aut }C)$.

From this point until the end of the section, the letter $C$ again denotes the
incidence coalgebra $\text{Co}(X,F)$ and $A$ is the incidence algebra
$I(X,F)$.

Let $\nu\in\text{In(Aut }C)$. We have an inclusion $\nu^{*}\in\text{In(Aut
}C^{*})$. Then we can to verify that $\Phi^{*}(\nu^{*})\in\text{In(Aut }A)$.
Therefore, we obtain a group antiisomorphic embedding

$\Theta\colon\text{In(Aut }C)\to\text{In(Aut }A)$

(see the beginning of Section 6).

Based on an arbitrary invertible function $h$ of the algebra $A$, we define
some elements of the field $F$. We take specific elements $x,y$ of the set $X$
with $x\leq y$. For elements $s,t\in X$ with $x\leq s\leq t\leq y$, we set

$\alpha_{xy}(s,t)=h^{-1}(x,s)\cdot h(t,y).$ $None$

Lemma 7.2. The following assertions are true.

  1. 1.

For elements $x,s,r,t,y\in X$ with $x\leq s\leq r\leq t\leq y$, we have the
relation

$\alpha_{xy}(s,t)=\alpha_{xr}(s,r)\cdot\alpha_{ry}(r,t).$

  2. 2.

Let we have $x,p,q,u,v,y\in X$ with $x\leq p\leq q<u\leq v\leq y$. Then the
sum $\sum_{q\leq z\leq u}\alpha_{xz}(p,q)\cdot\alpha_{zy}(u,v)$ is equal to
zero.

  3. 3.

The following relations are true:

$\alpha_{xx}(x,x)=1,\quad\sum_{x\leq s\leq y}\alpha_{xy}(s,s)=0\text{ for
}x<y.$

Proof. 1. It follows from relation $(1)$ that

$\alpha_{xr}(s,r)\cdot\alpha_{ry}(r,t)=h^{-1}(x,s)h(r,r)h^{-1}(r,r)\cdot
h(t,y).$

It remains to remark that $h(r,r)=1=h^{-1}(r,r)$, see [4, Theorem 4.3].

2. We can write down the relations

$\sum_{q\leq z\leq u}\alpha_{xz}(p,q)\cdot\alpha_{zy}(u,v)=\sum_{q\leq z\leq
u}h^{-1}(x,p)\cdot h(q,z)\cdot h^{-1}(z,u)\cdot h(v,y)=$ $=h^{-1}(x,p)\cdot
h(v,y)\left(\sum_{q\leq z\leq u}h(q,z)\cdot h^{-1}(z,u)\right)=$
$=h^{-1}(x,p)\cdot h(v,y)\cdot hh^{-1}(q,u)=h^{-1}(x,p)\cdot h(v,y)\cdot
1_{A}(q,u)=0$

(here $1_{A}$ is the identity mapping of the algebra $A$).

The relations of assertion 3 are directly verified. $\square$

As before, $h$ is some invertible function in $A$. We define a linear mapping
$\nu$ of the space $C$ by setting

$\nu([x,y])=\sum_{x\leq s\leq t\leq y}\alpha_{xy}(s,t)[s,t]=\sum_{x\leq s\leq
t\leq y}h^{-1}(x,s)[s,t]h(t,y).$ $None$

for every basis vector of $V$.

We denote by $\mu$ the inner automorphism of the algebra $A$ determined by its
invertible element $h$.

Proposition 7.3. The mapping $\nu$ is an inner automorphism of the coalgebra
$C$. In addition, the relation $\Theta(\nu)=\mu$ is true.

Proof. We verify the relation $\Delta\nu=(\nu\otimes\nu)\Delta$, where, as
before, $\Delta$ is a comultiplication in $C$.

We take an arbitrary interval $[x,y]$. By calculating, we obtain the relations

$\Delta\nu([x,y])=\sum_{x\leq s\leq r\leq t\leq
y}\alpha_{xy}(s,t)([s,r]\otimes[r,t]),$ $None$
$(\nu\otimes\nu)\Delta([x,y])=\sum_{x\leq p\leq q\leq z\leq u\leq v\leq
y}\alpha_{xz}(p,q)\alpha_{zy}(u,v)([p,q]\otimes[u,v]).$ $None$

It is necessary to verify the coincidence of the coefficients for the same
basis vectors of the space $C\otimes C$ contained in the right sides of
relations $(3)$ and $(4)$.

There is one-to-one correspondence between the summands in $(3)$ and the
summands in $(4)$ with $q=z=u$. The specific summand
$\alpha_{xy}(s,t)([s,r]\otimes[r,t])$ in $(3)$ corresponds to the summand
$\alpha_{xr}(s,r)\alpha_{ry}(r,t)([s,r]\otimes[r,t])$ in $(4)$. In view of
Lemma 7.2, $\alpha_{xy}(s,t)=\alpha_{xr}(s,r)\alpha_{ry}(r,t)$.

Now we prove that the sum of all summands in $(4)$ with $q<u$ is equal to
zero. To do this, we divide this sum into the sum of summands. Then it will be
easy to see that all such summands are equal to zero.

We take some basis vector $[p,q]\otimes[u,v]$ with $q<u$. There are several
summands with this basis vector, since $z$ takes values in the interval
$[q,u]$. The coefficient of the taken vector is equal to $\sum_{q\leq z\leq
u}\alpha_{xz}(p,q)\alpha_{zy}(u,v)$. The last expression is equal to zero, by
Lemma 7.2. The relation $\Delta\nu=(\nu\otimes\nu)\Delta$ is proved.

We also have to verify the relation $\varepsilon\nu=\varepsilon$. Let $[x,y]$
be an arbitrary basis vector of the coalgebra $C$. If $x=y$, then
$\varepsilon([x,x])=1$ and $\nu([x,x])=\alpha_{xx}(x,x)[x,x]$, where
$\alpha_{xx}(x,x)=1$, by Lemma 7.2.

If $x<y$, then $\varepsilon([x,y])=0$. By Lemma 7.2, we have $\sum_{x\leq
s\leq y}\alpha_{xy}(s,s)=0$. With the use relation $(2)$, we obtain the
required result.

It remains to verify that $\nu$ is a bijection. First, we verify that the
relation $\Theta(\nu)=\mu$ is true. Then it will be easy to obtain that $\nu$
is bijective.

Let $f\in A$ and $x,y\in X$ ($x\leq y$). With the use of Proposition 3.1 we
have the relation

$((\Theta(\nu))(f))(x,y)=\sum_{x\leq s\leq t\leq y}\alpha_{xy}(s,t)f(s,t).$

We also write down the relation $(\mu(f))(x,y)=h^{-1}fh(x,y)$ and do some
calculations:

$h^{-1}fh(x,y)=\sum_{x\leq t\leq y}(h^{-1}f)(x,t)\cdot h(t,y)=\sum_{x\leq
t\leq y}\left(\sum_{x\leq s\leq t}h^{-1}(x,s)f(s,t)\right)\cdot h(t,y)=$
$=\sum_{x\leq s\leq t\leq y}h^{-1}(x,s)\cdot h(t,y)\cdot f(s,t)=\sum_{x\leq
s\leq t\leq y}\alpha_{xy}(s,t)f(s,t).$

The relation $\Theta(\nu)=\mu$ is really true.

Similar to $(1)$, we set

$\beta_{xy}(s,t)=h^{-1}(t,y)h(x,s).$ $None$

Then we define linear mapping $\varkappa\colon C\to C$ by the use of the
relation

$\varkappa([x,y])=\sum_{x\leq s\leq t\leq y}\beta_{xy}(s,t)[s,t].$ $None$

Similar to the case of $\nu$, we can verify that $\varkappa$ is a homomorphism
of coalgebras and $\Theta(\varkappa)=\mu^{-1}$. Now it follows from relations
$\Theta(\nu\varkappa)=1=\Theta(\varkappa\nu)$ that
$\nu\varkappa=1=\varkappa\nu$ and $\nu$, $\varkappa$ are mutually inverse
isomorphisms. The last relations are also verified by direct calculation.

Thus, $\nu$ is an inner automorphism of the coalgebra $C$ and
$\Theta(\nu)=\mu$. The proof of the proposition is completed. $\square$

We conclude that all inner automorphisms of the coalgebra $C$ can be obtained
from invertible elements of the algebra $A$ with the use of relations $(1)$
and $(2)$. The following statement gives the exact meaning to the last phrase.

Corollary 7.4. The restriction of the mapping $\Theta$ to $\text{In(Aut }C)$
is an antiisomorphism between the groups $\text{In(Aut }C)$ and $\text{In(Aut
}A)$.

We set

$\text{In}_{0}(\text{Aut }C)=\Theta^{-1}(\text{In}_{0}(\text{Aut
}A)),\quad\text{In}_{1}(\text{Aut }C)=\Theta^{-1}(\text{In}_{1}(\text{Aut
}A)).$

Before Definition 4.2, it was write down the semidirect decomposition

$\text{In(Aut }A)=\text{In}_{1}(\text{Aut
}A)\leftthreetimes\text{In}_{0}(\text{Aut }A).$

Taking into account Corollary 7.4, we write down the following fact.

Corollary 7.5. We have a semidirect decomposition of groups

$\text{In(Aut }C)=\text{In}_{1}(\text{Aut
}C)\leftthreetimes\text{In}_{0}(\text{Aut }C).$

##  8 Structure of Group $\text{Aut }C$

We have Theorem 4.4 about the structure of the group $\text{Aut }(I(X,F))$ and
Proposition 6.1, 6.2 and Corollaries 7.4, 7.5, as well.

They allow to formulate the main result of Chapter 1.

We remark that the designation $\text{Aut}_{C}X$ appeared before Proposition
6.2.

Theorem 8.1. Let $A$ be an incidence algebra $I(X,F)$ and let $C$ be the
incidence coalgebra $\text{Co}(X,F)$. The following assertions are true.

  1. 1.

There are the relations

$\text{Aut }C=(\text{In}(\text{Aut }C)\text{Mult
}C)\leftthreetimes\text{Aut}_{C}X=\text{In}_{1}(\text{Aut
}C)\leftthreetimes\text{Mult }C\leftthreetimes\text{Aut}_{C}X.$

  2. 2.

The automorphism groups $\text{Aut }C$ and $\text{Aut }A$ are antiisomorphic.
For example, the antiisomorphism can be obtained with the use of the mapping
$\Theta$.

Proof. 1. We take an arbitrary automorphism $\varphi\in\text{Aut }C$. Then
$\Theta(\varphi)\in\text{Aut }A$ (see Lemma 5.1 and the beginning of Section
6). By Theorem 4.4, we have the relation $\Theta(\varphi)=\mu\psi\tau$, where
$\mu\in\text{In}_{1}(\text{Aut }A)$, $\psi\in\text{Mult }A$,
$\tau\in\text{Aut}_{A}X$. Now we use Propositions 6.1, 6.2 and Corollary 7.4
to write down

$\Theta(\nu)=\mu,\;\Theta(\lambda)=\psi,\;\Theta(\sigma)=\tau,$

where $\nu\in\text{In}_{1}(\text{Aut }C)$, $\lambda\in\text{Mult }C$,
$\sigma\in\text{Aut}_{C}X$. Therefore,
$\Theta(\sigma\lambda\nu)=\Theta(\nu)\Theta(\lambda)\Theta(\sigma)$.
Consequently, $\varphi=\sigma\lambda\nu$ or
$\varphi=\nu^{\prime}\lambda^{\prime}\sigma$ for some
$\nu^{\prime}\in\text{In}_{1}(\text{Aut }C)$, $\lambda^{\prime}\in\text{Mult
}C$. Assertion 1 is proved. At the same time, Assertion 2 is actually proved.
$\square$

## Chapter III. DERIVATION SPACE
OF INCIDENCE COALGEBRA

##  9 On Spaces $\text{Der }(I(X,F))$

We state the main facts about the derivation space $\text{Der}(I(X,F))$ of the
incidence algebra $I(X,F)$. Like before, we denote this algebra by the letter
$A$.

We formulate several familiar definitions.

Let $R$ be an algebra over some commutative ring $T$. The mapping $d\colon
R\to R$ is called a derivation of the algebra $R$ if $d$ is a linear mapping,
i.e. an endomorphism of the $T$-module $R$, and the relation
$d(ab)=d(a)b+ad(b)$ holds for any $a,b\in R$. All derivations of the algebra
$R$ form a $T$-module. We denote it by $\text{Der }R$.

For an element $c\in R$, we define a mapping $d_{c}$ from $R$ into $R$ by
assuming that $d_{c}(a)=ac-ca$, $a\in R$. Then $d_{c}$ is a derivation which
is said to be inner. We say that $d_{c}$ is determined by the element $c$. All
inner derivations of the algebra $R$ form a submodule of the $T$-module
$\text{Der }R$. We use the symbol $\text{In(Der }R)$ to designate it.

There is a notion of a derivation in a more general form. Let $N$ be an
$R$-$R$-bimodule. A homomorphism of $T$-modules $d\colon R\to N$, such that
$d(ab)=d(a)b+ad(b)$ for all $a,b\in R$, is called a derivation of the algebra
$R$ with values in the bimodule $N$. Such a derivation is said to be inner if
there exists an element $c\in N$ such that $d(a)=ac-ca$, $a\in R$.

We use the material and notation contained at the beginning of Section 4.
Thus, the splitting extension $A=L_{1}\oplus M_{1}$ will be useful.

We take an arbitrary derivation $d$ of the algebra $A$. Similar to the case of
automorphisms, the derivation $d$ can be associated with the matrix
$\left(\begin{smallmatrix}\alpha&\gamma\\\
\delta&\beta\end{smallmatrix}\right)$ with respect to the direct decomposition
$A=L_{1}\oplus M_{1}$. It is important that $\gamma=0$ by [4, Lemma 14.1]. We
have the following assertion [4, Corollaries 14.3, 15.4].

Corollary 9.1.

  1. 1.

Every derivation $d$ of the incidence algebra $A$ is of the form
$\left(\begin{smallmatrix}\alpha&0\\\ \delta&\beta\end{smallmatrix}\right)$.
Here $\alpha$ is a derivation of the algebra $L_{1}$, $\beta$ is a derivation
of the algebra $M_{1}$ (as a non-unital algebra), and $\delta$ is a derivation
of the algebra $L_{1}$ with values in $L_{1}$-$L_{1}$-bimodule $M_{1}$.

  2. 2.

If $\delta=0$, then the relations

$\beta(ad)=\alpha(a)d+a\beta(d),\quad\beta(cb)=\beta(c)b+c\alpha(b)$

hold for all $a,b\in L_{1}$ and $c,d\in M_{1}$.

We denote by $\text{In}_{0}(\text{Der }A)$ (resp., $\text{In}_{1}(\text{Der
}A)$) the subspace of inner derivations of the algebra $A$ determined by
elements of $L_{1}$ (resp., $M_{1}$).

Lemma 9.2 [4, Lemma 15.1]. There is a direct decomposition of spaces

$\text{In(\text{Der }}A)=\text{In}_{0}(\text{Der
}A)\oplus\text{In}_{1}(\text{Der }A).$

Let the symbol $\text{Add }A$ denote the subspace in $\text{Der }A$,
consisting of derivations of the form $\left(\begin{smallmatrix}0&0\\\
0&\beta\end{smallmatrix}\right)$. Such derivations are said to be additive.
Similar to multiplicative automorphisms, we can also define them with the sue
of certain systems of elements of the field $F$ (see [4]).

Definition 9.3. Let we have a system of elements $\\{c_{xy}\in F\,|\,x<y\\}$
such that the relation

$c_{xy}=c_{xz}+c_{zy}$ $None$

holds for all $x,z,y\in X$ with $x<z<y$. We call such systems additive
systems.

We can also define an additive system as a system $\\{c_{xy}\in F\,|\,x\leq
y\\}$ such that $c_{xx}=0$ for all $x$ and $c_{xy}=c_{xz}+c_{zy}$ if $x\leq
z\leq y$.

If $d=\left(\begin{smallmatrix}0&0\\\
0&\beta\end{smallmatrix}\right)\in\text{Add }A$, then for any $x,y\in X$ with
$x<y$, there exists an element $c_{xy}\in F$ such that $\beta(b)=c_{xy}b$,
where $b$ is an arbitrary element of $M_{xy}$. In this case, the system of the
elements $\\{c_{xy}\,|\,x<y\\}$ is additive.

It turns out that this additive derivation $d$ can be associated with an
additive system of elements $c_{xy}$ ($x,y\in X$, $x<y$) of the field $F$.
Conversely, every additive system of elements $\\{c_{xy}\in F\,|\,x<y\\}$
leads to an additive derivation. More precisely if $g=(g_{xy})\in M_{1}$, then
we have to set

$d(g)=(c_{xy}g_{xy})\text{ and }d(f)=0\text{ for }f\in L_{1}.$

Based on the above, we write down the following statement.

Proposition 9.4. There is a one-to-one correspondence between additive
derivations of the algebra $A$ and additive systems elements of the field $F$.

At the end of the section, we write down a theorem which describes the
structure of the space $\text{Der }A$.

Theorem 9.5 [7]. We have the relation

$\text{Der }A=\text{In}_{1}(\text{Der }A)\oplus\text{Add }A.$

##  10 Derivation Space $\text{Der }C$

For a while let $C$ be an arbitrary coalgebra $(C,\Delta,\varepsilon)$.

Definition 10.1. A linear mapping $d\colon C\to C$ is called a derivation of
the coalgebra $C$ if the relation $\Delta d=(d\otimes 1)\Delta+(1\otimes
d)\Delta$ holds.

All derivations of the coalgebra $C$ form an $F$-space which is called the
derivation space of the coalgebra $C$. We fix the symbol $\text{Der }C$ to
denote it.

Lemma 10.2. If $d\in\text{Der }C$, then $d^{*}\in\text{Der }C^{*}$.

Proof. We have to verify that the relation

$d^{*}m=m(d^{*}\otimes 1)+m(1\otimes d^{*})$

is true (mappings $m$ and $\rho$, found below, are defined at the beginning of
Section 2).

It follows from the relation $\Delta d=(d\otimes 1)\Delta+(1\otimes d)\Delta$
that

$d^{*}\Delta^{*}=\Delta^{*}(d\otimes 1)^{*}+\Delta^{*}(1\otimes d)^{*}.$

We also have the relations

$d^{*}m=d^{*}\Delta^{*}\rho=\Delta^{*}(d\otimes 1)^{*}\rho+\Delta^{*}(1\otimes
d)^{*}\rho,$ $m(d^{*}\otimes 1)+m(1\otimes d^{*})=\Delta^{*}\rho(d^{*}\otimes
1)+\Delta^{*}\rho(1\otimes d^{*}).$

Calculations show that the relations

$(d\otimes 1)^{*}\rho=\rho(d^{*}\otimes 1),\quad(1\otimes
d)^{*}\rho=\rho(1\otimes d^{*})$

hold; this implies the required result. $\square$

Beginning with this place and until the end of the chapter, $C$ denotes the
incidence coalgebra $\text{Co}(X,F)$.

It follows from Lemma 10.2 that there are group monomorphisms

$\Gamma\colon\text{Der }C\to\text{Der }C^{*},\quad d\to d^{*},$
$\Theta\colon\text{Der }C\to\text{Der }A,$

where $A$ is the incidence algebra $I(X,F)$. Here we also need to take into
account that the isomorphism $\Phi^{*}$ maps $\text{Der }C^{*}$ onto
$\text{Der }A$. (The mapping $\Gamma$ appeared at the end of Section 2, and
$\Phi^{*}$ and $\Theta$ appeared at the beginning of Section 3.) Theorem 12.1
actually states that in reality $\Gamma$ and $\Theta$ are isomorphisms.

In the previous section, we defined additive derivations and additive systems
of elements corresponding to them (see Proposition 9.4). Now we will carry out
similar considerations regarding the coalgebra $C$.

Let we have an additive system of elements $\\{c_{xy}\in F\,|\,x<y\\}$ (see
Definition 9.3). We define a mapping $\lambda\colon C\to C$ by setting
$\lambda([x,y])=c_{xy}[x,y]$ for every basis vector $[x,y]$ of the space $C$
with $x<y$, and $\lambda([x,x])=0$ for every $x$. Then $\lambda$ is a
derivation of the coalgebra $C$. We call it the additive derivation
corresponding to the additive system $\\{c_{xy}\in F\,|\,x<y\\}$.

All additive derivations form a space which is denoted by $\text{Add }C$.

Proposition 10.3. The spaces $\text{Add }A$ and $\text{Add }C$ are isomorphic.
The mapping $\Theta$ is an isomorphism of these spaces.

Proof. We can carry out reasoning similar to the reasoning from the proof of
Proposition 6.1. $\square$

##  11 Inner Derivations of Coalgebra $\text{Co}(X,F)$

We introduce the notion of an inner derivation of the incidence coalgebra
$C=\text{Co}(X,F)$. The following definition also makes sense for an arbitrary
coalgebra.

Definition 11.1. A derivation $\nu$ of the coalgebra $C$ is said to be inner
if $\nu^{*}$ is an inner derivation the dual of the algebra $C^{*}$.

All inner derivations of the coalgebra $C$ form a subspace; we denote it by
$\text{In(Der }C)$.

Let $\nu\in\text{In(Der }C)$. It is easy to verify that
$\Phi^{*}(\nu^{*})\in\text{In(Der }A)$ in our case. Therefore, we have an
isomorphic embedding of spaces

$\Theta\colon\text{In(Der }C)\to\text{In(Der }A).$

The purpose of further consideration is to show that these spaces are
isomorphic. Therefore, it can be argued that a derivation $\nu$ of the
coalgebra $C$ is inner if and only if $\Theta(\nu)$ is an inner derivation of
the algebra $A$.

Let $g$ be some function from the ring $A$ and let $\mu$ be the inner
derivation determined by this function.

For any two elements $x,y\in X$ with $x\leq y$, we set

$\nu([x,y])=\sum_{x\leq u\leq y}[x,u]g(u,y)-\sum_{x\leq v\leq y}g(x,v)[v,y].$
$None$

We obtain a linear mapping $\nu$ of the space $C$.

Proposition 11.2. The mapping $\nu$ is a derivation of the space $C$. In
addition, $\Theta(\nu)=\mu$.

Proof. We have to verify that the relation $\Delta\nu=(\nu\otimes
1)\Delta+(1\otimes\nu)\Delta$ is true.

We take an arbitrary basis vector $[x,y]$ of the space $C$. By calculating, we
obtain that there are relations

$\Delta\nu([x,y])=\sum_{x\leq s\leq u\leq
y}g(u,y)([x,s]\otimes[s,u])-\sum_{x\leq v\leq t\leq
y}g(x,v)([v,t]\otimes[t,y]),$ $None$ $((\nu\otimes
1)\Delta+(1\otimes\nu)\Delta)([x,y])=$ $\left[\sum_{x\leq v\leq p\leq
y}g(p,y)([x,v]\otimes[v,p])-\sum_{x\leq\ell\leq z\leq
y}g(x,\ell)([\ell,z]\otimes[z,y])\right]+$ $None$ $+\left[\sum_{x\leq k\leq
z\leq y}g(k,z)([x,k]\otimes[z,y])-\sum_{x\leq v\leq q\leq
y}g(v,q)([x,v]\otimes[q,y])\right].$

The expression from first pair of square brackets in $(3)$ coincides with the
right part of relation $(2)$, and the expression in the second pair of square
brackets is equal to zero.

Why $\Theta(\nu)=\mu$? Let $f\in A$ and let $x,y$ be two elements of $X$ with
$x\leq y$. With the use of Proposition 3.1, we obtain from $(1)$ the relation

$((\Theta(\nu))(f))(x,y)=\sum_{x\leq u\leq y}g(u,y)f(x,u)-\sum_{x\leq v\leq
y}g(x,v)f(v,y).$

Its right part coincides with the right part of the relation
$(\mu(f))(x,y)=(fg-gf)(x,y)$. $\square$

By the use of Proposition 10.3 and 11.2, we can write down the following
result.

Corollary 11.3. There exists a group isomorphism

$\Theta\colon\text{In(Der }C)\to\text{In(Der }A).$

We obtain that every inner derivation of the coalgebra $C$ is of the form
specified in $(1)$.

The subgroups of inner automorphisms $\text{In}_{0}(\text{Aut }C)$ and
$\text{In}_{1}(\text{Aut }C)$ were defined before Corollary 7.5. We can
similarly define the subspaces of inner derivations $\text{In}_{0}(\text{Der
}C)$ and $\text{In}_{1}(\text{Der }C)$ of the coalgebra $C$. Then the
following assertion follows from Lemma 9.2 and Corollary 11.3.

Corollary 11.4. We have a direct decomposition of $F$-spaces:

$\text{In(Der }C)=\text{In}_{0}(\text{Der }C)\oplus\text{In}_{1}(\text{Der
}C).$

##  12 Description of Derivation Space $\text{Der }C$

We write down a theorem which contain complete information about the structure
of the derivation space of the coalgebra $C$.

Theorem 12.1. Let $A$ be an incidence algebra $I(X,F)$ and let $C$ be the
incidence coalgebra $\text{Co}(X,F)$.

  1. 1.

There are relations

$\text{Der }C=\text{In(Der }C)+\text{Add }C=\text{In}_{1}(\text{Der
}C)\oplus\text{Add }C.$

  2. 2.

The derivation spaces $\text{Der }C$ and $\text{Der }A$ are isomorphic.

Proof. 1. We take an arbitrary derivation $d$ of the coalgebra $C$. Then
$\Theta(d)\in\text{Der }A$; see Lemma 10.2 and the text after its proof. We
can write down $\Theta(d)=\mu+\psi$, where $\mu\in\text{In}_{1}(\text{Der
}A)$, $\psi\in\text{Add }A$ (Theorem 9.5). In view of Corollary 11.3 and
Proposition 10.3, there are derivations $\nu\in\text{In}_{1}(\text{Der }C)$
and $\lambda\in\text{Add }C$ such that $\Theta(\nu)=\mu$ and
$\Theta(\lambda)=\psi$. Therefore, $\Theta(\nu+\lambda)=\mu+\psi=\Theta(d)$
and, therefore, $d=\nu+\lambda$.

2. The fact that $\Theta$ is the required isomorphism follows from the proof of assertion 1 (or from Proposition 10.3 and Corollary 11.3). $\square$

Open Questions.

1. Is it possible to define an inner automorphism of an arbitrary coalgebra $C$ (in particular, of the incidence coalgebra $C$) in terms of the coalgebra itself, i.e. without referring to the dual algebra $C^{*}$?

2. A similar question makes sense regarding inner derivations of the coalgebra $C$ (see Definitions 7.1 and 11.1).

## References

  * [1] Aquiar, M.; Santos, W. F. Galois connections for incidence Hopf algebras of partially ordered sets // Adv. Math. – 2000. – Vol. 151. – P. 71–100.
  * [2] Khrypchenko, M. Automorphisms of finitary incidence rings // Algebra and Discrete Mathematics. – 2010. – Vol. 9, no. 2. – P. 78–97.
  * [3] Khrypchenko, M. Derivations of Finitary Incidence Rings // Comm. Algebra. – 2012. – Vol. 40, no. 7. – P. 2503–2522.
  * [4] Krylov, Piotr; Tuganbaev, Askar. Incidence rings: automorphisms and derivations // arXiv:2305.02984v1 [math.RA], 2023.
  * [5] Leroux, P., Sarraillé, J. Structure of incidence algebras of graphs // Comm. Algebra. – 1981. – Vol. 9, no. 15. – P. 1479–1517.
  * [6] Schmitt, W. R. Incidence Hopf algebras // J. Pure Appl. Algebra. – 1994. – Vol. 96, no. 3. – P. 299–330.
  * [7] Spiegel, E.; O’Donnell, C. J. Incidence Algebras. – New York. – Marcel Dekker. – 1997.