††footnotetext: This work is based upon research funded by Iran National
Science Foundation under project number 99003814. The research of Ali
Mohammadian is supported by the Natural Science Foundation of Anhui Province
with grant identifier 2008085MA03 and by the National Natural Science
Foundation of China with grant number 12171002. The research of Meysam
Miralaei was supported by a grant from IPM.

# The weak saturation number of $\boldsymbol{K_{2,t}}$

Meysam Miralaei${}^{{}^{1}}$, Ali Mohammadian${}^{{}^{2}}$, Behruz Tayfeh-
Rezaie${}^{{}^{1}}$
${}^{{}^{1}}$School of Mathematics, Institute for Research in Fundamental
Sciences (IPM),
P.O. Box 19395-5746, Tehran, Iran
${}^{{}^{2}}$School of Mathematical Sciences, Anhui University,
Hefei 230601, Anhui, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

For two graphs $G$ and $F$, we say that $G$ is weakly $F$-saturated if $G$
contains no copy of $F$ as a subgraph and one could join all the nonadjacent
pairs of vertices of $G$ in some order so that a new copy of $F$ is created at
each step. The weak saturation number $\mathrm{wsat}(n,F)$ is the minimum
number of edges of a weakly $F$-saturated graph on $n$ vertices. In this
paper, we examine $\mathrm{wsat}(n,K_{s,t})$, where $K_{s,t}$ is the complete
bipartite graph with parts of sizes $s$ and $t$. We determine
$\mathrm{wsat}(n,K_{2,t})$, correcting a previous report in the literature. It
is also shown that $\mathrm{wsat}(s+t,K_{s,t})=\binom{s+t-1}{2}$ if
$\gcd(s,t)=1$ and $\mathrm{wsat}(s+t,K_{s,t})=\binom{s+t-1}{2}+1$, otherwise.

Key words and phrases: Complete bipartite graph, Weak saturation number.

2020 Mathematics Subject Classification: 05C35.

##  1 Introduction

All graphs throughout this paper are finite, undirected, and without loops or
multiple edges. The edge set of a graph $G$ is denoted by $E(G)$. For given
two graphs $G$ and $F$, a spanning subgraph $H$ of $G$ is said to be a weakly
$F$-saturated subgraph of $G$ if $H$ has no copy of $F$ as a subgraph and
there is an ordering $e_{1},e_{2},\dots$ of edges in $E(G)\setminus E(H)$ such
that for $i=1,2,\ldots$ the addition of $e_{i}$ to the spanning subgraph of
$G$ with the edge set $E(H)\cup\\{e_{1},\ldots,e_{i-1}\\}$ creates a copy of
$F$ that contains $e_{i}$. The minimum number of edges in a weakly
$F$-saturated subgraph of $G$ is called the weak saturation number of $F$ in
$G$ and is denoted by $\mathrm{wsat}(G,F)$. For the purpose of simplification,
a weakly $F$-saturated subgraph of $K_{n}$ is said to be a weakly
$F$-saturated graph and $\mathrm{wsat}(K_{n},F)$ is written as
$\mathrm{wsat}(n,F)$, where $K_{n}$ is the complete graph on $n$ vertices. For
example, each path graph is weakly $K_{3}$-saturated and
$\mathrm{wsat}(n,K_{3})=n-1$. Determining the exact value of
$\mathrm{wsat}(n,F)$ for a given graph $F$ is often quite difficult. It is
worth mentioning that the study of any extremal parameter is an important task
in graph theory and often receives a great deal of attention. Weak saturation
is closely related to the so-called graph bootstrap percolation which was
introduced for the first time in [2]. The notion of weak saturation was
initially introduced by Bollobás [3] in 1968. Although the weak saturation
number has been studied for a long time, related literature is still poor.
Indeed, the main difficulty lies in proving lower bounds where usually
combinatorial methods do not seem to work. Most arguments that have been used
in this area are based on algebraic methods. However, our proofs in the
current paper are all combinatorial. For results on weak saturation and
related topics, we refer to the survey [6].

Lovász [13] established that
$\mathrm{wsat}(n,K_{r})=\binom{n}{2}-\binom{n-r+2}{2}$ when $n\geqslant
r\geqslant 2$, settling a conjecture of Bollobás [3]. The result is also
proved by Frankl [8], Kalai [10], Alon [1], and Yu [14]. Surprisingly, these
proofs all are based on algebraic techniques and no combinatorial proof has
been found so far.

After complete graphs, the next most natural question to consider regarding
weak saturation numbers is description of the behavior of
$\mathrm{wsat}(n,K_{s,t})$, where $K_{s,t}$ is the complete bipartite graph
with parts of sizes $s$ and $t$. Borowiecki and Sidorowicz [4] proved that
$\mathrm{wsat}(n,K_{1,t})=\binom{t}{2}$ provided $n\geqslant t+1$. A short
proof of this result is given in [7]. The equality
$\mathrm{wsat}(n,K_{2,2})=n$ follows from Theorem 16 of [4] for all
$n\geqslant 4$. Faudree, Gould, and Jacobson [7] showed that
$\mathrm{wsat}(n,K_{2,3})=n+1$ for all $n\geqslant 5$. Kalai [9] established
that $\mathrm{wsat}(n,K_{t,t})=(t-1)n-\binom{t-1}{2}$ if $n\geqslant 4t-4$.
This result is also proved by Kronenberg, Martins, and Morrison [12] for
$n\geqslant 3t-3$ by a linear algebraic argument. They posed the following
question: For every two positive integers $s,t$ with $t>s$, is there an
integer $n_{0}$ such that $\mathrm{wsat}(n,K_{s,t})=(s-1)(n-s)+\binom{t}{2}$
for any integer $n\geqslant n_{0}$? They affirmatively answered to the
question for $t=s+1$.

It is claimed in [5] that $\mathrm{wsat}(n,K_{2,t})$ is argumentatively
determined for $t\geqslant 4$ and $n\geqslant 2t-1$. However, the given proof
is completely confusing and a lot of details of the proof are missing so that
a reader can in no way be sure of the truth of the proof. In the current
paper, we fill this gap in the literature by proving the following result.

######  Theorem 1.1.

For every two integers $n,t$ with $t\geqslant 3$ and $n\geqslant t+2$, the
following hold.

  * (i)

If $t$ is odd, then $\mathrm{wsat}(n,K_{2,t})=n-2+\binom{t}{2}$.

  * (ii)

If $t$ is even and $n\leqslant 2t-2$, then
$\mathrm{wsat}(n,K_{2,t})=n-1+\binom{t}{2}$.

  * (iii)

If $t$ is even and $n\geqslant 2t-1$, then
$\mathrm{wsat}(n,K_{2,t})=n-2+\binom{t}{2}$.

A relatively new trend in extremal graph theory has been developed to extend
the classical deterministic results to random analogues. The study reveals the
behavior of extremal parameters for a typical graph. In this regard, it is
interesting to investigate the weak saturation problem in random graphs. More
precisely, one may ask to determine
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{s,t})$ for given fixed integers $s,t$,
where $\mathbbmsl{G}(n,p)$ is the Erdős–Rényi random graph model. Kalinichenko
and Zhukovskii [11] studied the necessary conditions on a graph $F$ so that
$\mathrm{wsat}(\mathbbmsl{G}(n,p),F)=\mathrm{wsat}(n,F)$ holds with high
probability. Our results combined with Corollary 1 of [11] show that with high
probability
$\mathrm{wsat}(\mathbbmsl{G}(n,p),K_{2,t})=\mathrm{wsat}(n,K_{2,t})$ for
constant $p$.

Let us fix some more notation and terminology for later use. Let $G$ be a
graph. The vertex set of $G$ is denoted by $V(G)$ and the order of $G$ is
defined as $|V(G)|$. The complement of $G$, denoted by $\overline{G}$, is a
graph with vertex set $V(G)$ in which $uv\in E(\overline{G})$ if $u\neq v$ and
$uv\notin E(G)$. For a subset $X$ of $V(G)$, we denote the induced subgraph of
$G$ on $X$ by $G[X]$. For a subset $Y$ of $E(G)$, we denote by $G-Y$ the graph
obtained from $G$ by removing the edges in $Y$. For a subset $Y$ of
$E(\overline{G})$, we adopt the notation $G+Y$ to denote the graph with vertex
set $V(G)$ and edge set $E(G)\cup Y$. For a vertex $v$ of $G$, set
$N_{G}(v)=\\{x\in V(G)\,|\,x\text{ is adjacent to }v\\}$ and define the degree
of $v$ as $|N_{G}(v)|$. We drop the subscript if there is no danger of
confusion. For the sake of convenience, we set $N[u]=\\{u\\}\cup N(u)$ and
$N(u,v)=N(u)\cap N(v)$.

##  2 Determination of $\boldsymbol{\mathrm{wsat}(s+t,K_{s,t})}$

The problem of determining $\mathrm{wsat}(n,F)$ when $F$ is of order $n$ is
interesting to explore. In this section, we solve this problem when $F$ is a
complete bipartite graph. The following lemma helps us to get a lower bound.

######  Lemma 2.1.

Let $s,t$ be positive integers and let $G$ be a weakly $K_{s,t}$-saturated
graph on $s+t$ vertices. Then, $\overline{G}$ has no cycle. Moreover,
$\overline{G}$ is not connected if $\gcd(s,t)\neq 1$.

###### Proof.

Fix an order $e_{1},e_{2},\ldots$ of $E(\overline{G})$ that is obtained from a
weakly $K_{s,t}$-saturation process on $G$. By contrary, suppose that
$\overline{G}$ has a cycle, say $C$. Let $e_{i}$ be the first edge of $C$ that
appears in the order. In view of the definition of weakly $K_{s,t}$-saturation
process, there is a partition $\\{A,B\\}$ of $V(G)$ with $|A|=s$ and $|B|=t$
such that $e_{i}$ is the only missing edge between $A$ and $B$ in
$G+\\{e_{1},\ldots,e_{i-1}\\}$. So, both endpoints of each edge among
$e_{i+1},e_{i+2},\ldots$ belong to one of $A$ or $B$. This is impossible,
since $C$ has to pass through at least one edge $e_{j}$ with $j>i$ having
endpoint in both $A$ and $B$. This yields that $\overline{G}$ has no cycle.

Now, assume that $\overline{G}$ is a tree. Let $H_{0}=\overline{G}$ and
$H_{i}=\overline{G}-\\{e_{1},\ldots,e_{i}\\}$ for any $i\geqslant 1$. We claim
that for any $i\geqslant 0$, $H_{i}$ is a forest whose connected components
are of order divisible by $d$, where $d=\gcd(s,t)$. Since
$\overline{G}-\\{e_{1},e_{2},\ldots\\}=\overline{K}_{s+t}$, we find that
$d=1$, as required.

We prove the claim by induction on $i$. The claim is clearly valid for $i=0$.
So, assume that $i\geqslant 1$. According to the definition of weakly
$K_{s,t}$-saturation process, there is a partition $\\{A,B\\}$ of $V(G)$ with
$|A|=s$ and $|B|=t$ such that $e_{i}$ is the only missing edge between $A$ and
$B$ in $G+\\{e_{1},\ldots,e_{i-1}\\}$. Hence, $e_{i}$ is the only edge in
$H_{i-1}$ between $A$ and $B$. Let $C_{1},\ldots,C_{i}$ be the connected
components of $H_{i-1}$. Without loss of generality, assume that $e_{i}\in
E(C_{1})$. So, the connected components of $H_{i}$ are
$C_{1}^{\prime},C_{1}^{\prime\prime},C_{2},\ldots,C_{i}$, where
$C_{1}^{\prime}$ and $C_{1}^{\prime\prime}$ are the induced subgraphs of
$C_{1}$ on $A\cap V(C_{1})$ and $B\cap V(C_{1})$, respectively. As $e_{i}$ is
the only edge in $H_{i-1}$ between $A$ and $B$, we conclude that either
$V(C_{i})\subseteq A$ or $V(C_{i})\subseteq B$ for any $i\geqslant 2$. It
follows that $A$ is a disjoint union of $V(C^{\prime}_{1})$ and some sets
among $V(C_{2}),\ldots,V(C_{i})$. The induction hypothesis yields that
$|V(C_{2})|,\ldots,|V(C_{i})|$ are multiples of $d$. This and the divisibility
of $|A|$ by $d$ imply that $|V(C^{\prime}_{1})|$ is a multiple of $d$. A
similar argument works for $|V(C_{1}^{\prime\prime})|$. The claim is
established. ∎

The following consequence immediately follows from Lemma 2.1.

######  Corollary 2.2.

For every integers $s,t$,
$\mathrm{wsat}(s+t,K_{s,t})\geqslant\binom{s+t-1}{2}$. Moreover, if
$\gcd(s,t)\neq 1$, then
$\mathrm{wsat}(s+t,K_{s,t})\geqslant\binom{s+t-1}{2}+1$.

We present the following two lemmas to obtain a tight upper bound. We use the
notation $P_{n}$ for the path graph of order $n$.

######  Lemma 2.3.

Let $s$ and $t$ be positive integers. Then,
$\mathrm{wsat}(s+t,K_{s,t})\leqslant\binom{s+t-1}{2}+1$.

###### Proof.

We prove that $G=\overline{P_{s+t-1}\cup K_{1}}$ is weakly
$K_{s,t}$-saturated. Denote by $v_{1},\ldots,v_{s+t-1}$ the vertices of
$P_{s+t-1}$ going in the natural order of the path and set
$V(K_{1})=\\{v_{s+t}\\}$. Let $e_{1}=v_{s}v_{s+1}$, $e_{i}=v_{i-1}v_{i}$ for
$i=2,\ldots,s$, and $e_{i}=v_{i}v_{i+1}$ for $i=s+1,\ldots,s+t-2$. We claim
that $e_{1},\ldots,e_{s+t-2}$ is an order in which the weakly
$K_{s,t}$-saturation process occurs. Let $H_{0}=G$ and
$H_{i}=G+\\{e_{1},\ldots,e_{i}\\}$ for $i=1,\ldots,s+t-2$. We find a partition
$\\{A_{i},B_{i}\\}$ of $V(G)$ such that $|A_{i}|=s$, $|B_{i}|=t$, and
$e_{i+1}$ is the only missing edge between $A_{i}$ and $B_{i}$ in $H_{i}$ for
$i=0,1,\ldots,s+t-3$. This obviously establishes the claim. We introduce
$A_{0},A_{1},\ldots A_{s+t-3}$ below. Let $A=\\{v_{1},\ldots,v_{s}\\}$. Now,
set $A_{0}=A$, $A_{i}=(A\setminus\\{v_{i}\\})\cup\\{v_{s+t}\\}$ for
$i=1,\ldots,s-1$, and $A_{i}=(A\setminus\\{v_{1}\\})\cup\\{v_{i+1}\\}$ for
$i=s,\ldots,s+t-3$. ∎

######  Lemma 2.4.

Let $s$ and $t$ be positive integers with $\gcd(s,t)=1$. Then,
$\mathrm{wsat}(s+t,K_{s,t})\leqslant\binom{s+t-1}{2}$.

###### Proof.

We prove that $G=\overline{P}_{s+t}$ is weakly $K_{s,t}$-saturated. We proceed
by induction on $s+t$. The assertion clearly holds for $s+t=2$. Let
$t+s\geqslant 3$ and denote by $v_{1},\ldots,v_{s+t}$ the vertices of
$P_{s+t}$ going in the natural order of the path. Partition $V(G)$ into two
subsets $A=\\{v_{1},\ldots,v_{s}\\}$ and $B=\\{v_{s+1},\ldots,v_{s+t}\\}$.
Since the edge $e=v_{s}v_{s+1}$ is the only missing edge between $A$ and $B$
in $G$, we consider $e$ as the first element in an ordering of
$E(\overline{G})$ in the weakly $K_{s,t}$-saturation process on $G$. Let
$G^{\prime}=G+e$ for the sake of convenience. Without loss of generality,
assume that $t\geqslant s$. Using the definition, in each step of a weakly
$K_{s,t-s}$-saturation process on $G^{\prime}[B]$, there is a partition
$\\{C,D\\}$ of $B$ such that $|C|=s$, $|D|=t-s$, and all edges between $C$ and
$D$ are present except exactly one. Since there is no edge between $A$ and $B$
in $\overline{G^{\prime}}$, every step of a weakly $K_{s,t-s}$-saturation
process on $G^{\prime}[B]$ corresponding to a vertex partition $\\{C,D\\}$ can
be considered as a step of a weakly $K_{s,t}$-saturation process on
$G^{\prime}$ corresponding to the vertex partition $\\{C,A\cup D\\}$. Hence,
by the induction hypothesis, $G^{\prime}[B]$ may be completed to reach to
$K_{t}$ in a weakly $K_{s,t}$-saturation process. Thus, it remains to show
that $G^{\prime\prime}=G^{\prime}+\\{v_{i}v_{i+1}\,|\,s\leqslant i\leqslant
s+t-1\\}$ is weakly $K_{s,t}$-saturated. For $i=1,\ldots,s-1$, the edge
$e_{i}=v_{i}v_{i+1}$ is the only missing edge between
$\\{v_{1},\ldots,v_{i}\\}\cup\\{v_{s+1},\ldots,v_{2s-i}\\}$ and
$\\{v_{i+1},\ldots,v_{s}\\}\cup\\{v_{2s-i+1},\ldots,v_{s+t}\\}$ in
$G^{\prime\prime}$ and therefore we may add $e_{i}$ to $G^{\prime\prime}$ in
the weakly $K_{s,t}$-saturation process. ∎

We summarize the results of this section as follows.

######  Theorem 2.5.

For every two positive integers $s$ and $t$,

$\displaystyle\mathrm{wsat}(s+t,K_{s,t})=\left\\{\begin{array}[]{ll}\binom{s+t-1}{2}&\text{if
}\gcd(s,t)=1,\\\ \\\ \binom{s+t-1}{2}+1&\text{otherwise}.\end{array}\right.$

##  3 Determination of $\boldsymbol{\mathrm{wsat}(n,K_{2,t})}$

In this section, we establish Theorem 1.1 which is a direct consequent of
Lemmas 3.2, 3.4 and 3.8. Recall that the minimum vertex degree of a graph $G$
is denoted by $\delta(G)$. The following lemma is well known.

######  Lemma 3.1.

Let $F$ be a graph with $\delta(F)\geqslant 1$ and let $G$ be a weakly
$F$-saturated graph such that $|V(G)|\geqslant|V(F)|-1$. Join a new vertex $v$
to $\delta(F)-1$ arbitrary vertices of $G$. Then the resulting graph is also
weakly $F$-saturated.

###### Proof.

Denote the resulting graph by $G^{\prime}$. Since $G$ is weakly $F$-saturated,
we may add all edges in $E(\overline{G})$ to $G$ in some order to obtain a
complete subgraph on $V(G)$. Let $e\in E(F)$ be incident to a vertex of degree
$\delta(F)$. For each vertex $x\in V(G)\setminus N_{G^{\prime}}(v)$, there is
a copy of $F-e$ in $G^{\prime}$ containing the vertices in $\\{v,x\\}\cup
N_{G^{\prime}}(v)$ and so, we may connect $v$ to $x$ in the weakly
$F$-saturation process on $G^{\prime}$. The assertion follows. ∎

######  Lemma 3.2.

For every two integers $n,t$ with $t\geqslant 3$ and $n\geqslant t+2$, the
following hold.

  * (i)

If $t$ is odd, then $\mathrm{wsat}(n,K_{2,t})\leqslant n-2+\binom{t}{2}$.

  * (ii)

If $t$ is even and $n\leqslant 2t-2$, then $\mathrm{wsat}(n,K_{2,t})\leqslant
n-1+\binom{t}{2}$.

  * (iii)

If $t$ is even and $n\geqslant 2t-1$, then $\mathrm{wsat}(n,K_{2,t})\leqslant
n-2+\binom{t}{2}$.

###### Proof.

Let $H$ be a weakly $K_{2,t}$-saturated graph on $t+2$ vertices and
$\mathrm{wsat}(t+2,K_{2,t})$ edges. Attach $n-t-2$ pendent vertices to an
arbitrary vertex of $H$ to obtain a graph $G$ of order $n$. By Lemma 3.1, $G$
is a weakly $K_{2,t}$-saturated graph with $n-t-2+\mathrm{wsat}(t+2,K_{2,t})$
edges. Parts (i) and (ii) follow from Theorem 2.5. The graph
$\mathnormal{\Gamma}_{n}$ depicted in Figure 1 and introduced in [5, 12], is
weakly $K_{2,t}$-saturated for $n\geqslant 2t-1$. This can be proved by using
a proof similar to that of Proposition 14 in [12]. Since the graph has $n$
vertices and $n-2+\binom{t}{2}$ edges, (iii) follows. ∎

$K_{t-1}$$\overline{K}_{n-t-2}$ Figure 1: The graph $\mathnormal{\Gamma}_{n}$.
We have not drawn the edges in gray elliptical desk.

It what follows, we bound $\mathrm{wsat}(n,K_{2,t})$ from below. The following
lemma is trivially true.

######  Lemma 3.3.

Fix a graph $F$ and let $G$ and $H$ be two graphs with the same vertex set.
Assume that the graph obtained from $H$ by adding a sequence of edges in the
weakly $F$-saturation process contains $G$ as a subgraph. If $G$ is weakly
$F$-saturated, then so is $H$.

######  Lemma 3.4.

Let $t\geqslant 3$ and $n\geqslant t+2$. Then,
$\mathrm{wsat}(n,K_{2,t})\geqslant n-2+\binom{t}{2}$.

###### Proof.

Let $G$ be a weakly $K_{2,t}$-saturated graph on $n$ vertices. We show that
$|E(G)|\geqslant n-2+\binom{t}{2}$. By Lemma 3.1, if we add a pendent vertex
to $G$, then the resulting graph is also weakly $K_{2,t}$-saturated whose
number of vertices is one more than the number of vertices of $G$ and whose
number of edges is one more than the number of edges of $G$. In the following,
we will add pendent vertices to $G$ whenever needed.

We define a process in which step, $G$ is updated so that a special structure
on $G$ is preserved. In each step of the process, $G$ looks as follows. The
edges of $G$ are colored by two colors black and red. The number of black
edges is fixed. The spanning subgraph of $G$ induced on black edges is
connected. There exist two disjoint subsets $A$ and $B$ of $V(G)$ which are
equipped with the following features. There is an ordering on $A$ under which
the vertices in $A$ can be arranged as $x_{1},\ldots,x_{k}$, where $k=|A|$.
Every red edge has at least one endpoint in $A$. There exist partition
$\\{A_{1},\ldots,A_{m}\\}$ of $A$ and partition $\\{B_{1},\ldots,B_{m}\\}$ of
$B$ which are described below. To do this, fix $i\in\\{1,\ldots,m\\}$ and
denote by $x_{s_{i}}$ the first element among $x_{1},\ldots,x_{k}$ which
appears within $A_{i}$. The following properties will be held in each step of
the process.

  * (P1)

For every two vertices $x,y\in A_{i}$, we have
$N(x)\setminus\\{y\\}=N(y)\setminus\\{x\\}$.

  * (P2)

The set $A_{i}$ is either a clique of size at least $2$ or an independent set
of size $2$ or $3$.

  * (P3)

Every edge between $x_{s_{i}}$ and $A_{i}\setminus\\{x_{s_{i}}\\}$ is black
whenever $A_{i}$ is a clique.

  * (P4)

Every vertex in $A_{i}$ is adjacent to every vertex in $A_{j}$ whenever $j\neq
i$.

  * (P5)

Each edge between $x_{s_{i}}$ and $V(G)\setminus A$ is black.

  * (P6)

Every vertex $x_{r}\in A_{i}$ is adjacent to every vertex $x_{s_{j}}$ by a
black edge if $s_{j}<r$ and $j\neq i$.

  * (P7)

$|B_{i}|=t-s_{i}$.

  * (P8)

For any vertex $x\in B_{i}$, we have $N(x)=A_{i}$.

  * (P9)

Any vertex $x_{r}\in A_{i}$ is adjacent to exactly $\alpha_{r}$ vertices in
$B_{i}$ by black edges, where

$\displaystyle\alpha_{r}=\left\\{\begin{array}[]{ll}t-r&\quad\,\,\,\text{if
}r=s_{i},\\\ \\\ t-r+2&\quad\begin{array}[]{l}\text{if $A_{i}$ is an
independent set of size}\\\ \text{3 and $x_{r}$ is the third element of
$A_{i}$,}\end{array}\\\ \\\
t-r+1&\quad\,\,\,\text{otherwise}.\end{array}\right.$

The configuration described above is designed so that at each step of the
process, the graph induced on black edges is weakly $K_{2,t}$-saturated, and
red edges are the ones that are added through the weakly $K_{2,t}$-saturation
process. This will be shown in Cases I, II, III below.

At the beginning of the process, all edges are black and $A=B=\varnothing$. In
Cases I, II, III, we explain how in each step of the process we update $G$,
$A$, and $B$ to proceed to the next step. More precisely, we repeat the
process until one of the following occurs.

  * (T1)

$|A_{i}|\geqslant t-1$ for some $i$.

  * (T2)

$k=t$, $|A_{i}|\leqslant t-2$ for any $i$, and there are two vertices $u,v\in
V(G)\setminus(A\cup B)$ such that $|N(u,v)|\geqslant t-1$ and
$N(u)\setminus\\{v\\}\neq N(v)\setminus\\{u\\}$.

  * (T3)

$k=t+1$, $|A_{i}|\leqslant t-2$ for any $i$, and there are two vertices
$u,v\in V(G)\setminus(A\cup B)$ such that $|N(u,v)|\geqslant t-1$ and
$N(u)\setminus\\{v\\}\neq N(v)\setminus\\{u\\}$.

  * (T4)

$k=t+1$, $|A_{i}|\leqslant t-2$ for any $i$, and there are two vertices $u\in
A$ and $v\in V(G)\setminus(A\cup B)$ such that $|N(u,v)|\geqslant t-1$ and
$N(u)\setminus\\{v\\}\neq N(v)\setminus\\{u\\}$.

We now show what we do in each step of the process before termination. In the
beginning of each step, $G$ is weakly $K_{2,t}$-saturated and so there are two
vertices $a,b$ such that $|N(a,b)|\geqslant t-1$ and $N(a)\setminus\\{b\\}\neq
N(b)\setminus\\{a\\}$. Since (T1) is not happened, (P8) forces that $a,b\notin
B$. We distinguish the following three cases.

Case I. $a,b\notin A$.

Since (T2) and (T3) are not happened, $k\leqslant t-1$. Set $x_{k+1}=a$,
$x_{k+2}=b$, $s_{m+1}=k+1$, and $A_{m+1}=\\{x_{k+1},x_{k+2}\\}$. Suppose that
$x_{k+1}$ or $x_{k+2}$ is not adjacent to $x_{s_{i}}$ for some $i$. We have
$|N(x_{k+1},x_{k+2})\setminus A|\geqslant t-1-|N(x_{k+1},x_{k+2})\cap
A|\geqslant t-1-(k-|A_{i}|)\geqslant|A_{i}|\geqslant 2$. So, we may remove two
arbitrary edges between $x_{k+2}$ and $N(x_{k+1},x_{k+2})\setminus A$ and join
both $x_{k+1}$ and $x_{k+2}$ to $x_{s_{i}}$ by black edges and to all vertices
in $A_{i}\setminus\\{x_{s_{i}}\\}$ by red edges. By repeating this, we derive
$A\subseteq N(x_{k+1},x_{k+2})$ and hence $|N(x_{k+1},x_{k+2})\setminus
A|\geqslant t-1-k$. We now remove $t-1-k$ arbitrary edges between $x_{k+2}$
and $N(x_{k+1},x_{k+2})\setminus A$ and connect $x_{k+2}$ to all vertices in a
subset $B_{m+1}$ consisting of $t-1-k$ arbitrary pendent vertices in
$N(x_{k+1})$.

Now, update $A$ to $A\cup A_{m+1}$ with partition $\\{A_{1},\ldots,A_{m+1}\\}$
and update $B$ to $B\cup B_{m+1}$ with partition $\\{B_{1},\ldots,B_{m+1}\\}$.

Case II. $a\in A_{i}$ for some $i$ and $b\notin A$.

Since (T4) is not happened, $k\leqslant t$. In view of (P1) and without loss
of generality, we may assume that $a=x_{s_{i}}$. Let $x_{k+1}=b$.

First, assume that $A_{i}\cup\\{x_{k+1}\\}$ is an independent set of size $3$.
Suppose that $x_{k+1}$ is not adjacent to $x_{s_{j}}$ for some $j\neq i$. We
have $|N(x_{s_{i}},x_{k+1})\setminus A|\geqslant t-1-|N(x_{s_{i}},x_{k+1})\cap
A|\geqslant t-1-(k-|A_{j}|)\geqslant|A_{j}|-1\geqslant 1$. So, we may remove
an arbitrary edge between $x_{k+1}$ and $N(x_{s_{i}},x_{k+1})\setminus A$ and
join $x_{k+1}$ to $x_{s_{j}}$ by a black edge and to all vertices in
$A_{j}\setminus\\{x_{s_{j}}\\}$ by red edges. By repeating this, we derive
$A\setminus A_{i}\subseteq N(x_{s_{i}},x_{k+1})$ and thus
$|N(x_{s_{i}},x_{k+1})\setminus A|\geqslant t-1-(k-|A_{i}|)\geqslant t-k+1$.
We now remove $t-k+1$ arbitrary edges between $x_{k+1}$ and
$N(x_{s_{i}},x_{k+1})\setminus A$ and connect $x_{k+1}$ to $t-k+1$ arbitrary
distinct vertices in $B_{i}$ by black edges.

Next, assume that $A_{i}\cup\\{x_{k+1}\\}$ is not an independent set of size
$3$. Let $x_{k+1}$ be not adjacent to $x_{s_{j}}$ for some $j$. We have
$|N(x_{s_{i}},x_{k+1})\setminus A|\geqslant t-1-|N(x_{s_{i}},x_{k+1})\cap
A|\geqslant t-1-(k-|A_{j}|)\geqslant|A_{j}|-1\geqslant 1$. So, we may remove
an arbitrary edge between $x_{k+1}$ and $N(x_{s_{i}},x_{k+1})\setminus A$ and
join $x_{k+1}$ to $x_{s_{j}}$ by a black edge and to all vertices in
$A_{j}\setminus\\{x_{s_{j}}\\}$ by red edges. By repeating this, we derive
$A\subseteq N(x_{k+1})$. If $A_{i}$ is a clique, then
$A\setminus\\{x_{s_{i}}\\}\subseteq N(x_{s_{i}},x_{k+1})$. Suppose that
$A_{i}$ is an independent set. We have $N(x_{s_{i}},x_{k+1})\cap A=A\setminus
A_{i}$ and hence $|N(x_{s_{i}},x_{k+1})\setminus A|\geqslant
t-1-(k-|A_{i}|)\geqslant|A_{i}|-1$. We now remove $|A_{i}|-1$ arbitrary edges
between $x_{k+1}$ and $N(x_{s_{i}},x_{k+1})\setminus A$ and join $x_{s_{i}}$
to all vertices in $A_{i}\setminus\\{x_{s_{i}}\\}$ by black edges, resulting
$A\setminus\\{x_{s_{i}}\\}\subseteq N(x_{s_{i}},x_{k+1})$. Therefore,
regardless of whether $A_{i}$ is a clique or an independent set,
$|N(x_{s_{i}},x_{k+1})\setminus A|\geqslant t-1-(|A|-1)=t-k$. Remove $t-k$
arbitrary edges between $x_{k+1}$ and $N(x_{s_{i}},x_{k+1})\setminus A$ and
connect $x_{k+1}$ to $t-k$ arbitrary distinct vertices in $B_{i}$ by black
edges.

Now, update $A_{i}$ to $A_{i}\cup\\{x_{k+1}\\}$ and $A$ to
$A\cup\\{x_{k+1}\\}$ with partition $\\{A_{1},\ldots,A_{m}\\}$.

Case III. $a\in A_{i}$ and $b\in A_{j}$ for some $i,j$ with $i<j$.

In view of (P1) and without loss of generality, we may assume that
$a=x_{s_{i}}$ and $b=x_{s_{j}}$. Let $x_{r}\in A_{j}$. By (P9), there are
exactly $\alpha_{r}$ black edges between $x_{r}$ and $B_{j}$. Remove all edges
between $x_{r}$ and $B_{j}$ and connect $x_{r}$ to $\alpha_{r}$ arbitrary
vertices in $B_{i}$ by black edges. This is possible, as $|B_{i}|>\alpha_{r}$.
Note that, if $A_{j}$ is an independent set of size $3$ and $x_{r}$ is the
third element of $A_{j}$, then we have connected one more edge between $x_{r}$
and $B_{i}$ than needed.

Remove all black edges between $x_{s_{j}}$ and $x_{r}$, with $r>s_{j}$. The
number of such edges is $k-s_{j}-q$, where $q=|A_{j}\setminus N[x_{s_{j}}]|$.
Note that, $|N(x_{s_{i}},x_{s_{j}})\cap A|=k-p-q-2$, where $p=|A_{i}\setminus
N[x_{s_{i}}]|$. We have $|N(x_{s_{i}},x_{s_{j}})\setminus A|\geqslant
t-1-(k-p-q-2)$. Since $t-1-(k-p-q-2)+(k-s_{j}-q)=p+(t-s_{j})+1$, we may
connect $x_{s_{i}}$ to all vertices in $(A_{i}\setminus N[x_{s_{i}}])\cup
B_{j}$ and $x_{s_{j}}$ to an arbitrary vertex in $B_{i}$ by black edges. Now,
update $A_{i}$ to $A_{i}\cup A_{j}$ and consider the partition
$\\{A_{1},\ldots,A_{j-1},A_{j+1},\ldots,A_{m}\\}$ for $A$ and the partition
$\\{B_{1},\ldots,B_{j-1},B_{j+1},\ldots,B_{m}\\}$ for $B$.

At the end of each of Cases I, II, III, we do the following. In order to
establish (P1) and (P3), for each vertex $w$ with $N(w)\cap
A_{i}\neq\varnothing$, join $w$ to all vertices in $A_{i}\setminus N(w)$ by
red edges. In order to establish (P5), for each vertex $w\in
V(G)\setminus(A\cup B)$ with $N(w)\cap A_{i}\neq\varnothing$, since there
exists at least a vertex $x_{r}\in A_{i}$ so that the color of the edge
$wx_{r}$ is black, we may switch the color of the edge $wx_{r}$ with the color
of the edge $wx_{s_{i}}$. Note that, after doing all these changes, the number
of black edges does not change and the resulting graph have Properties
(P1)–(P9). Moreover, by Lemma 3.3, $G$ is still weakly $K_{2,t}$-saturated.

Now, assume that the process is terminated. For every two subsets
$X,Y\subseteq V(G)$, let $e(X,Y)$ denote the number of black edges with one
endpoint in $X$ and the other endpoint in $Y$. Let $\beta$ and $\gamma$ be the
number of independent sets among $A_{1},\ldots,A_{m}$ of sizes $2$ and $3$,
respectively. Denoting the number of black edges of $G$ by $e(G)$, we have

$\displaystyle e(G)$ $\displaystyle\geqslant
e(A,B)+e(A,A)+e\big{(}V(G),V(G)\setminus(A\cup B)\big{)}$ (4)
$\displaystyle\geqslant\left(\sum_{r=1}^{k}\alpha_{r}\right)+\left(\sum_{r=1}^{k}\big{|}\\{i\,|\,s_{i}<r\\}\big{|}-\beta-2\gamma\right)+\left(n-|A|-\sum_{i=1}^{m}|B_{i}|\right)$
(5)
$\displaystyle=\left(\sum_{r=1}^{t}(t-r+1)-m+\gamma-\delta\right)+\left(\sum_{i=1}^{m}\big{|}\\{r\,|\,r>s_{i}\\}\big{|}-\beta-2\gamma\right)+\left(n-k-\sum_{i=1}^{m}(t-s_{i})\right)$
$\displaystyle=\left(\binom{t+1}{2}-m+\gamma-\delta\right)+\left(\sum_{i=1}^{m}(k-s_{i})-\beta-2\gamma\right)+\left(n-k-\sum_{i=1}^{m}(t-s_{i})\right)$
$\displaystyle=\bigg{(}n-2+\binom{t}{2}\bigg{)}+\bigg{(}(m-1)(k-t-1)-\beta-\gamma-\delta+1\bigg{)},$
(6)

where $\delta$ is $1$ if $k=t-1$ and $0$ otherwise. We consider the
termination states (T1)–(T4) in the following four cases. In each of Cases
1–4, we will establish that $e(G)\geqslant n-2+\binom{t}{2}$ using (6).

Case 1. (T1) has happened.

In this case, either $m=1$ and $k\in\\{t-1,t,t+1\\}$ or $m=2$ and $k=t+1$. If
$\beta+\gamma+\delta\leqslant 1$, then (6) implies that $e(G)\geqslant
n-2+\binom{t}{2}$, we are done. So, assume that $\beta+\gamma+\delta\geqslant
2$. This forces that either $m=\beta+\gamma=\delta=1$ or $m=2$,
$\beta=\gamma=1$, $\delta=0$. Since there is an independent set of size $t-1$
among $A_{1},\ldots,A_{m}$, one concludes that $t=3$ or $4$. The induced
subgraph of $G$ on $A\cup B$, say $H$, is bipartite. It is clearly seen for
$m=1$ and one may consider the vertex partition $\\{A_{1}\cup B_{2},A_{2}\cup
B_{1}\\}$ for $m=2$. If $e(V(G),V(G)\setminus(A\cup B))>|V(G)\setminus(A\cup
B)|$, then (4) and (6) yield that $e(G)\geqslant n-2+\binom{t}{2}$, noting
that the second summand in (6) equals $-1$. Otherwise, using connectivity of
$G$ and starting by $H$, we may add vertices in $V(G)\setminus(A\cup B)$ to
$H$ in some order such that in each step the resulting graph is bipartite.
This means that $G$ is bipartite which is impossible, since a bipartite graph
is clearly not weakly $K_{2,t}$-saturated.

Case 2. (T2) has happened.

As $k=t$, it follows from (6) that $e(G)\geqslant
n-2+\binom{t}{2}-(m+\beta+\gamma-2)$. We show that there are at least
$m+\beta+\gamma-2$ black edges in $G$ which we have not counted them yet.

By an argument similar to the one used in Case I, we may assume that either
$A\subseteq N(u,v)$ or $N(u,v)\cap A=A\setminus A_{i}$ for some $i$ with
$|A_{i}|=2$. First, suppose that $A\subseteq N(u,v)$. So, there are $2m$ black
edges between $\\{u,v\\}$ and $\\{x_{s_{1}},\ldots,x_{s_{m}}\\}$ which only
two of them have been counted in the third term in (5). Therefore, $2m-2$ new
black edges are found. Since $m+\beta+\gamma-2\leqslant 2m-2$, there is
nothing to do. Next, suppose that $N(u,v)\cap A=A\setminus A_{i}$ for some $i$
with $|A_{i}|=2$. Then, we have $|N(u,v)\setminus A|=|N(u,v)|-|N(u,v)\cap
A|\geqslant t-1-|A\setminus A_{i}|=1$. Let $w\in N(u,v)\setminus A$. Then,
there are $2m$ black edges between $\\{u,v\\}$ and
$(\\{x_{s_{1}},\ldots,x_{s_{m}}\\}\setminus\\{x_{s_{i}}\\})\cup\\{w\\}$ which
only three of them have been counted in the third term in (5). Therefore,
$2m-3$ new black edges are found. If $m\geqslant\beta+\gamma+1$, then
$2m-3\geqslant m+\beta+\gamma-2$, we are done. So, assume that
$m=\beta+\gamma$ which means that $A_{1},\ldots,A_{m}$ are independent sets.

We need to show the existence of one black edge in $G$ which is not counted
yet. We may assume that $uv\notin E(G)$, since otherwise we are done. For each
vertex $z\in N(u,v)\setminus A$, choose a pendent vertex $w_{z}$ in $N(u)$ and
delete the black edge between $v$ and $z$ and connect $v$ to $w_{z}$ by a
black edge. As $uv\notin E(G)$, $G$ is not a complete graph and so there are
two vertices $x,y$ such that $|N(x,y)|\geqslant t-1$ and
$N(x)\setminus\\{y\\}\neq N(y)\setminus\\{x\\}$. Set $A_{m+1}=\\{u,v\\}$ and
$x_{s_{m+1}}=u$ and update $A$ to $A\cup A_{m+1}$. Consider the following
three subcases.

Subcase 2.1. $x,y\notin A\cup B$.

If $N(x,y)\cap A=\varnothing$, then we may remove two arbitrary edges between
$y$ and $N(x,y)$ and join both $x,y$ to $x_{s_{i}}$ by black edges for some
$i$. So, we may assume that the number of common neighbors of $x,y$ in
$\\{x_{s_{1}},\ldots,x_{s_{m+1}}\\}$, say $\ell$, is nonzero. First, suppose
that $\ell=1$. We have $N(x,y)\cap A=A_{i}$ for some $i$ and so $|N(x,y)\cap
A|\leqslant t-2$. This means that $x,y$ have at least one common neighbor in
$V(G)\setminus(A\cup B)$ which gives us one extra edge. Next, suppose that
$\ell\geqslant 2$. Then, there are at least four black edges between
$\\{x,y\\}$ and $\\{x_{s_{1}},\ldots,x_{s_{m+1}}\\}$ which two of them are
already counted. Hence, we have two extra black edges.

Subcase 2.2. $x\in A_{i}$ for some $i$ and $y\in V(G)\setminus(A\cup B)$.

If $N(x,y)\cap A=\varnothing$, then we may remove one arbitrary edge between
$y$ and $N(x,y)$ and join $y$ to $x_{s_{j}}$ by a black edge for some $j\neq
i$. So, we assume that the number of common neighbors of $x,y$ in
$\\{x_{s_{1}},\ldots,x_{s_{m+1}}\\}$, say $\ell$, is nonzero in view of (P3)
and (P6). First, suppose that $\ell=1$. We have $N(x,y)\cap A=A_{j}$ for some
$j\neq i$, since $A_{1},\ldots,A_{m}$ are independent sets. Hence,
$|N(x,y)\cap A|\leqslant t-2$ and so $x,y$ have at least one common neighbor
in $V(G)\setminus(A\cup B)$ which gives us one extra edge. Next, suppose that
$\ell\geqslant 2$. Then, there are at least two black edges between $y$ and
$\\{x_{s_{1}},\ldots,x_{s_{m+1}}\\}$ which one of them are already counted.
Thus, we find one extra black edge.

Subcase 2.3. $x,y\in A$.

Since $A_{1},\ldots,A_{m+1}$ are independent sets, $x,y$ have at most $t-2$
common neighbors in $A$ and hence they have at least one common neighbor in
$V(G)\setminus(A\cup B)$ which gives us one extra edge.

Case 3. (T3) has happened.

As $k=t+1$, it follows from (6) that $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)$. We show that there are at least
$\beta+\gamma-1$ black edges in $G$ which are not already counted.

By an argument similar to the one used in Case I, we may assume that either
$A\subseteq N(u,v)$ or $N(u,v)\cap A=A\setminus A_{i}$ for some $i$ with
$|A_{i}|=2$ or $3$. First, suppose that $A\subseteq N(u,v)$. Then, there are
$2m$ black edges between $\\{u,v\\}$ and $\\{x_{s_{1}},\ldots,x_{s_{m}}\\}$
which only two of them have been counted in the third term in (5). Therefore,
$2m-2$ new black edges are found. Since $2m-2\geqslant\beta+\gamma-1$, we are
done. Next, suppose that $N(u,v)\cap A=A\setminus A_{i}$ for some $i$ with
$|A_{i}|=2$ or $3$. There are $2m-2$ black edges between $\\{u,v\\}$ and
$\\{x_{s_{1}},\ldots,x_{s_{m}}\\}\setminus\\{x_{s_{i}}\\}$ which only two of
them have been counted in the third term in (5). Therefore, $2m-4$ new black
edges are found. If either $m\geqslant 3$ or $m=2$ and $\beta+\gamma\leqslant
1$, then $2m-4\geqslant\beta+\gamma-1$ and hence there is nothing to do.
Otherwise, $m=\beta+\gamma=2$ and thus $t=4$ or $5$. Since
$2m-4=(\beta+\gamma-1)-1$, we need to show the existence of one black edge in
$G$ which is not counted yet. First, let $t=4$. As $A_{1},\ldots,A_{m}$ all
are of size at most $t-2$, one concludes that $\gamma=0$ and so $m=\beta=2$
which means that $k=4$, contradicting $k=t+1$. Now, let $t=5$. From $k=t+1$,
we have $\beta=0$ and $\gamma=2$ which in turns gives $|A_{i}|=3$ and
$|N(u,v)\cap A|=3$. It follows that $|N(u,v)\setminus A|\geqslant 1$ which
gives us one extra black edge.

Case 4. (T4) has happened.

As $k=t+1$, it follows from (6) that $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)$. We show that there are at least
$\beta+\gamma-1$ black edges in $G$ which are not already counted.

From $u\in A$ and in view of (P1), we may assume that $u=x_{s_{i}}$ for some
$i$. Suppose that $v$ is not adjacent to $x_{s_{j}}$ for some $j\neq i$. We
have $|N(u,v)\setminus A|\geqslant t-1-|N(u,v)\cap A|\geqslant
t-1-(k-|\\{u\\}\cup A_{j}|)=|A_{j}|-1\geqslant 1$. So, we may remove an
arbitrary edge between $v$ and $N(u,v)\setminus A$ and join $v$ to $x_{s_{j}}$
by a black edge and to all vertices in $A_{j}\setminus\\{x_{s_{j}}\\}$ by red
edges. By repeating this, we get $A\setminus A_{i}\subseteq N(u,v)$.
Accordingly, there are $m-1$ black edges between $v$ and
$\\{x_{s_{1}},\ldots,x_{s_{m}}\\}\setminus\\{x_{s_{i}}\\}$ which only one of
them have been counted in the third term in (5). Therefore, $m-2$ new black
edges are found and hence there is nothing to prove if
$m\geqslant\beta+\gamma+1$. So, assume that $m=\beta+\gamma$ which means that
$A_{1},\ldots,A_{m}$ are independent sets. We need one more extra black edge
which is not already counted. We may assume that $uv\notin E(G)$, since
otherwise we are done by (P6). By property (P2), we have $|A_{i}|=2,3$. Update
$A_{i}$ to $A_{i}\cup\\{v\\}$. Note that $|A_{i}|\leqslant t-2$. By contrary,
suppose that $|A_{i}|=t-1$. Then $t=4$ or $t=5$. If $t=4$, then $m=2$ and so
$|A_{j}|=3$ for $j\neq i$ which is a contradiction since $|A_{j}|\leqslant
t-2$. Hence $t=5$. In this case we have $|N(u,v)\cap A|=3$. So
$|N(u,v)\setminus A|\geqslant 1$ and there is an extra black edge which is not
already counted. Therefore, $|A_{i}|\leqslant t-2$. As $G$ is not a complete
graph, there are two vertices $x,y\notin B$ such that $|N(x,y)|\geqslant t-1$
and $N(x)\setminus\\{y\\}\neq N(y)\setminus\\{x\\}$ and we proceed to the
three subcases in Case 2 to show that there exists a black edge not counted
yet. ∎

The following two lemmas are easily checked.

######  Lemma 3.5.

Let $G$ be a graph with the vertex set partition $V(G)=X\cup Y\cup Z$ and the
edge set $E(G)=\\{ab|\ (a,b)\in(X,X)\cup(X,Y)\cup(Y,Z)\\}$, where
$|X|\geqslant 2$ and $|Y|\geqslant 1$. Then $G$ is weakly $K_{2,t}$-saturated
if and only if either $|X|\geqslant t$ or $|Y|\geqslant t-1$ and
$|X|+|Z|\geqslant t$.

######  Lemma 3.6.

Let $G$ be a connected graph with the vertex set partition $V(G)=X\cup Y$ such
that $e(V(G),Y)=|Y|$. Then the vertices in $Y$ with maximum possible distance
from $X$ are of degree one and form an independent set.

######  Lemma 3.7.

Let $G$ be a weakly $K_{2,t}$-saturated graph on $n$ vertices with $n\leqslant
2t-2$. Let $v$ be a degree one vertex in $G$. Then $G\setminus\\{v\\}$ is also
weakly $K_{2,t}$-saturated.

###### Proof.

Do the weakly $K_{2,t}$-saturation process on $V(G)\setminus\\{v\\}$ joining
nonadjacent vertices as far as possible. By contradiction, suppose that
$G\setminus\\{v\\}$ is not a complete graph. Define the relation $\approx$ on
$V(G)\setminus\\{v\\}$ as $x\approx y$ if $|N_{G}(x)\cap N_{G}(y)|\geqslant
t-1$. Clearly, $\approx$ is an equivalence relation on $V(G)\setminus\\{v\\}$.
Note that the equivalence classes are cliques or independent sets and the
connections between two distinct equivalence classes are all present or all
absent. Moreover, the size of an independent equivalence class is at most
$t-2$, since otherwise we have $n\geqslant 2t-1$. And the size of a clique
equivalence class is at most $t-1$. This is since otherwise, by connectivity
of $G$, we observe that $K_{t+1}$ is a subgraph of $G\setminus\\{v\\}$ and
hence it is weakly $K_{2,t}$-saturated by Lemma 3.1, a contradiction.

Assume that $\mathcal{A}$ is the equivalence class containing the neighbor of
$v$. Note that $\mathcal{A}\not=V(G)\setminus\\{v\\}$. We continue the weakly
$K_{2,t}$-saturation process on $G$ by joining $v$ to all vertices in
$\mathcal{A}$. Since $G$ is not complete, there is a vertex $w$ such that
$|N_{G}(v)\cap N_{G}(w)|\geqslant t-1$ and $N_{G}(v)\setminus\\{w\\}\neq
N_{G}(w)\setminus\\{v\\}$. Since $N_{G}(v)=\mathcal{A}$, we have
$|\mathcal{A}|=t-1$ and $\mathcal{A}\subseteq N_{G}(w)$ meaning that
$\mathcal{A}$ is a clique and $w\notin\mathcal{A}$. Let $w$ be in the
equivalence class $\mathcal{B}$. We claim that $\mathcal{B}$ is an independent
set. By the contrary, suppose that $w$ has a neighbor, say $b$ in
$\mathcal{B}$. Let $a\in\mathcal{A}$. Then
$(\mathcal{A}\setminus\\{a\\})\cup\\{w\\}\subseteq N_{G}(a)\cap N_{G}(b)$.
Then $a\approx b$ which is a contradiction. Add $v$ to $\mathcal{B}$ and make
the neighborhood of $v$ and $w$ the same in $G$. The resulting graph is not
still complete. Thus, to proceed with the weakly $K_{2,t}$-saturation process,
there must be two vertices $x$ and $y$ from different equivalence classes with
the common neighborhood $C$ of size $t-1$ and containing $v$ (and so
$\mathcal{B}$). If $C\cap\mathcal{A}=\varnothing$, then $n\geqslant 2t-1$, a
contradiction. So $C\cap\mathcal{A}\neq\varnothing$. If $x\in\mathcal{A}$,
then $(\mathcal{A}\setminus\\{x\\})\cup\mathcal{B}\subset C$ and so
$|C|\geqslant t$, a contradiction. Hence, $x,y\notin\mathcal{A}$ and
$\mathcal{A}\subseteq C$ which results in $|C|\geqslant t+1$, a contradiction
again. ∎

######  Lemma 3.8.

Let $t\geqslant 4$ be even and $t+2\leqslant n\leqslant 2t-2$. Then,
$\mathrm{wsat}(n,K_{2,t})\geqslant n-1+\binom{t}{2}$.

###### Proof.

For $t=4$, the assertion follows from Theorem 2.5. Hence, let $t\geqslant 6$.
Assume that $G$ is a weakly $K_{2,t}$-saturated graph on $n$ vertices. Towards
a contradiction and in view of Lemma 3.4, we assume that $G$ has
$n-2+\binom{t}{2}$ edges. Also suppose that for the given $t$, $G$ is a
counterexample with minimum possible number of vertices. Therefore, by Theorem
2.5, $n>t+2$. Also by Lemma 3.7, $\delta(G)>1$. We set $G_{0}=G$.

We apply the process defined in the proof of Lemma 3.4 to $G$. Assume that the
process has terminated. We need a careful examination of termination states
(T1)-(T4) to obtain a contradiction.

Case 1. (T1) has happened.

As Case 1 in the proof of Lemma 3.4, we have $\beta+\gamma+\delta\leqslant
m+\delta\leqslant 2$ and $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma+\delta-1)$. By the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $\beta+\gamma+\delta=2$ or
$\beta+\gamma+\delta=1$. Note that if $m=\beta+\gamma$, then $k\leqslant 6$
and hence $t\leqslant 5$, a contradiction. Thus we have $m>\beta+\gamma$.

If $\beta+\gamma+\delta=2$, then by $\beta+\gamma<m\leqslant 2$, we obtain
that $\beta+\gamma\leqslant 1$ and thus $\delta=1$. This yields
$m=\beta+\gamma=1$, a contradiction. So let $\beta+\gamma+\delta=1$. Then, we
have equality in (5) and so $e(V(G),V(G)\setminus(A\cup
B))=|V(G)\setminus(A\cup B)|$. Considering only black edges in $G$, by Lemma
3.6 and $\delta(G_{0})>1$, we observe that the maximum distance of vertices of
$V(G)\setminus(A\cup B)$ from $(A\cup B)$ is one. This shows that
$V(G)\setminus(A\cup B)$ is an independent set. If $m=1$, then by
$m>\beta+\gamma$, we have $\beta=\gamma=0$, $\delta=1$ and so
$G=K_{t-1}\vee\overline{K}_{n-t+1}$ which is not a weakly $K_{2,t}$-saturated
graph. So let $m=2$. Then from $t\geqslant 6$, $k=t+1$ and the termination
condition $|A_{i}|\geqslant t-1$ for some $i$, we obtain that $\beta=1$ and
$\gamma=0$. It is not hard to see that $G_{0}$ is a subgraph of the graph $H$
depicted in Figure 2, where $X=K_{t-1},|Y_{1}|=2,|Z|+|Y_{2}|\leqslant t-3$.
However, $H$ is not weakly $K_{2,t}$-saturated by Lemma 3.5, a contradiction.

Case 2. (T2) has happened.

As Case 2 in the proof of Lemma 3.4, we consider the following two situations.
First, suppose that $A\subseteq N(u,v)$. Let $A_{m+1}=\\{u,v\\}$ and update
$A$ to $A\cup\\{u,v\\}$. From $e(G)\geqslant
n-2+\binom{t}{2}-(m+\beta+\gamma-2)+2m-2$ and the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $m\leqslant\beta+\gamma$ and hence
$m=\beta+\gamma$ which in turn gives $e(V(G),V(G)\setminus(A\cup
B))=|V(G)\setminus(A\cup B)|$. Considering only black edges in $G$, by Lemma
3.6 and $\delta(G_{0})>1$, we observe that the maximum distance of vertices of
$V(G)\setminus(A\cup B)$ from $(A\cup B)$ is one. This shows that
$V(G)\setminus(A\cup B)$ is an independent set. Since $G$ is not a complete
graph, there are two vertices $x,y\in A$ such that $|N(x,y)|\geqslant t-1$ and
$N(x)\setminus\\{y\\}\neq N(y)\setminus\\{x\\}$. However,
$A_{1},\ldots,A_{m+1}$ are independent sets and so $x$ and $y$ have at most
$t-2$ common neighbors, a contradiction.

Now suppose that $N(u,v)\cap A=A\setminus A_{i}$ for some $i$ with
$|A_{i}|=2$. Let $A_{m+1}=\\{u,v\\}$, update $A$ to $A\cup\\{u,v\\}$ and $B$
to $B\cup\\{w\\}$. From $e(G)\geqslant
n-2+\binom{t}{2}-(m+\beta+\gamma-2)+2m-3$ and the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $m\leqslant\beta+\gamma+1$ and hence
$m=\beta+\gamma$ or $\beta+\gamma+1$. First let $m=\beta+\gamma+1$. Then
$e(V(G),V(G)\setminus(A\cup B))=|V(G)\setminus(A\cup B)|$. Considering only
black edges in $G$, by Lemma 3.6 and $\delta(G_{0})>1$, we again find that
$V(G)\setminus(A\cup B)$ is an independent set. If $A_{i}$ is an independent
set, then $G_{0}$ is a subgraph of the graph $H$ depicted in Figure 2, where
$X=K_{t-2},Y_{1}=A_{i}\cup A_{m+1},|Z|+|Y_{2}|\leqslant t-4$. However, $H$ is
not weakly $K_{2,t}$-saturated by Lemma 3.5, a contradiction. So let $A_{i}$
be a clique. Since $G$ is not a complete graph, there are two vertices $x,y\in
A$ such that $|N(x,y)|\geqslant t-1$ and $N(x)\setminus\\{y\\}\neq
N(y)\setminus\\{x\\}$. However, all $A_{j}$ except $A_{i}$ are independent
sets and there is no edge between $A_{i}$ and $A_{m+1}$, so $x$ and $y$ have
at most $t-2$ common neighbors, a contradiction.

Now let $m=\beta+\gamma$. Then there is one other black edge in $G$ beyond
what we have counted so far. This may cause some $A_{j}$, $j\not=i,m+1$, to
merge. So we obtain that $G_{0}$ is a subgraph of the graph $H$ depicted in
Figure 2, where $X=K_{t-2},Y_{1}=A_{i}\cup A_{m+1},|Z|+|Y_{2}|\leqslant t-4$.
However, $H$ is not weakly $K_{2,t}$-saturated by Lemma 3.5, a contradiction.

Case 3. (T3) has happened.

As Case 3 in the proof of Lemma 3.4, we consider the following two situations.
First, suppose that $A\subseteq N(u,v)$. Then, from $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)+2m-2$ and the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $2m\leqslant\beta+\gamma+1$ and so
$m=1$, a contradiction.

Now suppose that $N(u,v)\cap A=A\setminus A_{i}$ for some $i$ with $|A_{i}|=2$
or $3$. If $|A_{i}|=3$, then from $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)+2m-3$ and the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $2m\leqslant\beta+\gamma+2\leqslant m+2$
and so $m=\beta+\gamma=2$ which in turn yields that $k=t+1\leqslant 6$ and so
$t\leqslant 5$, contradiction. Thus let $|A_{i}|=2$. Let $A_{m+1}=\\{u,v\\}$
and update $A$ to $A\cup\\{u,v\\}$. From $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)+2m-4$ and the assumption
$e(G)=n-2+\binom{t}{2}$, we find that $2m\leqslant\beta+\gamma+3\leqslant m+3$
and so $m=2,3.$ Let $m=3$. Then $\beta+\gamma=3$ and so $k=t+1\leqslant 8$
which implies that $t=6$. Take a vertex from $A_{i}$ and another vertex from
$A_{m+1}$. They have five common neighbors and so the two sets $A_{i}$ and
$A_{m+1}$ are merged to form an independent set of size four. Since $G$ is not
still complete, there are two distinct vertices $x,y$ such that
$|N(x,y)|\geqslant t-1$ and $N(x)\setminus\\{y\\}\neq N(y)\setminus\\{x\\}$.
Note that we have counted all black edges and so $x,y\in A$. However, three
sets $A_{j}$ are all independent sets and are of size 2,3,4 which means that
$x$ and $y$ have at most four common neighbors, a contradiction. Let now
$m=2$. Since $k=t+1$ and $|A_{i}|=2$, we have $|A_{j}|=t-1$ for some $j$, a
contradiction.

Case 4. (T4) has happened.

As Case 4 in the proof of Lemma 3.4, let $A\setminus A_{i}\subseteq N(u,v)$.
Then from $e(G)\geqslant n-2+\binom{t}{2}-(\beta+\gamma-1)+m-2$ and the
assumption $e(G)=n-2+\binom{t}{2}$, we find that $m\leqslant\beta+\gamma+1$
and so $m=\beta+\gamma$ or $\beta+\gamma+1$.

First let $m=\beta+\gamma+1$. Then there is no other black edge in $G$ beyond
what we have counted so far. This shows that $|A_{i}|=2$. Update $A_{i}$ to
$A_{i}\cup\\{v\\}$ and $A$ to $A\cup\\{v\\}$. Then $e(V(G),V(G)\setminus(A\cup
B))=|V(G)\setminus(A\cup B)|$. Considering only black edges in $G$, by Lemma
3.6 and $\delta(G_{0})>1$, we observe that the maximum distance of vertices of
$V(G)\setminus(A\cup B)$ from $(A\cup B)$ is one. This shows that
$V(G)\setminus(A\cup B)$ is an independent set. We claim that there is an
independent set $A_{j}$ with $|A_{j}|=3$. If $A_{i}$ is independent, then we
are done since $|A_{i}|=3$. So assume that $A_{i}$ is a clique. Then by
$m=\beta+\gamma+1$, all $A_{j}$ for $j\not=i$ are independent sets. If they
are all of size 2, then $t+2$ is odd, a contradiction. The claim is proved.
Now $G_{0}$ is a subgraph of the graph $H$ depicted in Figure 2, where
$X=K_{t-1},|Y_{1}|=3,|Z|+|Y_{2}|\leqslant t-4$. However, $H$ is not weakly
$K_{2,t}$-saturated by Lemma 3.5, a contradiction.

Now let $m=\beta+\gamma$. First let $|A_{i}|=3$. Update $A_{i}$ to
$A_{i}\cup\\{v\\}$ and $A$ to $A\cup\\{v\\}$. From $e(G)\geqslant
n-2+\binom{t}{2}-(\beta+\gamma-1)+m-1$ and the assumption
$e(G)=n-2+\binom{t}{2}$, it turns out that we have counted all black edges.
Hence, $e(V(G),V(G)\setminus(A\cup B))=|V(G)\setminus(A\cup B)|$. This again
shows that $V(G)\setminus(A\cup B)$ is an independent set. Now $G_{0}$ is a
subgraph of the graph $H$ depicted in Figure 2, where
$X=K_{t-2},Y_{1}=A_{i},|Z|+|Y_{2}|\leqslant t-4$. However, $H$ is not weakly
$K_{2,t}$-saturated by Lemma 3.5, a contradiction.

Next assume that $|A_{i}|=2$. Let $u$ and $v$ be adjacent. Update $A_{i}$ to
$A_{i}\cup\\{v\\}$ and $A$ to $A\cup\\{v\\}$. Since we have counted all black
edges, $e(V(G),V(G)\setminus(A\cup B))=|V(G)\setminus(A\cup B)|$. This again
shows that $V(G)\setminus(A\cup B)$ is an independent. Also $A_{i}$ is a
clique of size 3. If all $A_{j}$, $j\not=i$ are of size 2, then $t+2$ is odd,
a contradiction. So there is an independent set $A_{j}$ with $|A_{j}|=3$. Now
$G_{0}$ is a subgraph of the graph $H$ depicted in Figure 2, where
$X=K_{t-1},|Y_{1}|=3,|Z|+|Y_{2}|\leqslant t-4$. However, $H$ is not weakly
$K_{2,t}$-saturated by Lemma 3.5, a contradiction. Now let $u$ and $v$ not be
adjacent. Update $A_{i}$ to $A_{i}\cup\\{v\\}$ and $A$ to $A\cup\\{v\\}$. So
$A_{i}$ is an independent set of size 3. There is one black edge uncounted. If
$t\geqslant 8$, then the only way to proceed with the weakly
$K_{2,t}$-saturation process is to merge some $A_{j}$ using the uncounted
black edge. This shows that $G_{0}$ is a subgraph of the graph $H$ depicted in
Figure 2, where $X=K_{t-1},Y_{1}=A_{i},|Z|+|Y_{2}|\leqslant t-4$. However, $H$
is not weakly $K_{2,t}$-saturated by Lemma 3.5, a contradiction. Hence, assume
that $t=6.$ Then $m=3$. Without loss of generality assume that
$|A_{1}|=2,|A_{2}|=3,|A_{3}|=3.$ Let $x,y$ be two vertices such that
$|N(x,y)|\geqslant t-1$ and $N(x)\setminus\\{y\\}\neq N(y)\setminus\\{x\\}$.
If $x,y\in V(G)\setminus(A\cup B)$, then we find at least two more black
edges, a contradiction. If $x\in A_{j}$ for some $j$ and $y\in
V(G)\setminus(A\cup B)$, then we add $y$ to $A_{j}$ and update $A$ to
$A\cup\\{y\\}$. Now $|A_{j}|\leqslant 4$ for any $j$. So any two vertices from
two distinct $A_{j}$ have at most four common neighbors. This means that the
graph is not weakly $K_{2,t}$-saturated. Finally, if $x,y\in A$, then we find
that $x$ and $y$ have at most three common neighbors in $A$ and so at least
two common neighbors in $V(G)\setminus(A\cup B)$ which gives us two more black
edges, a contradiction. ∎

$X$$Y_{1}$$Z$$Y_{2}$ Figure 2: The graph $H$. We have not drawn the edges in
gray elliptical desk.

## References

  * [1] N. Alon, An extremal problem for sets with applications to graph theory, J. Combin. Theory Ser. A 40 (1985) 82–89.
  * [2] J. Balogh, B. Bollobás, R. Morris, Graph bootstrap percolation, Random Structures Algorithms 41 (2011) 413–440.
  * [3] B. Bollobás, Weakly $k$-saturated graphs, Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967), Teubner, Leipzig, 1968, pp. 25–31.
  * [4] M. Borowiecki, E. Sidorowicz, Weakly $\mathscr{P}$-saturated graphs, Discuss. Math. Graph Theory 22 (2002) 17–29.
  * [5] Y. Cui, L. Pu, Weak saturation numbers of $K_{2,t}$ and $K_{p}\cup K_{q}$, AKCE Int. J. Graphs Comb. 16 (2019) 237–240.
  * [6] B.L. Currie, J.R. Faudree, R.J. Faudree, J.R. Schmitt, A survey of minimum saturated graphs, Electron. J. Combin. (2021) #DS19.
  * [7] R.J. Faudree, R.J. Gould, M.S. Jacobson, Weak saturation numbers for sparse graphs, Discuss. Math. Graph Theory 33 (2013) 677–693.
  * [8] P. Frankl, An extremal problem for two families of sets, European J. Combin. 3 (1982) 125–127.
  * [9] G. Kalai, Hyperconnectivity of graphs, Graphs Combin. 1 (1985) 65–79.
  * [10] G. Kalai, Weakly saturated graphs are rigid, in: Convexity and graph theory (Jerusalem, 1981), North-Holland Math. Stud., 87, Ann. Discrete Math., 20, North-Holland, Amsterdam, 1984, pp. 189–190.
  * [11] O. Kalinichenko, M. Zhukovskii, Weak saturation stability, available online at: http://arxiv.org/pdf/2107.11138v2.pdf.
  * [12] G. Kronenberg, T. Martins, N. Morrison, Weak saturation numbers of complete bipartite graphs in the clique, J. Combin. Theory Ser. A 178 (2021) 105357.
  * [13] L. Lovász, Flats in matroids and geometric graphs, in: Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway Coll., Egham, 1977), Academic Press, London, 1977, pp. 45–86.
  * [14] J. Yu, An extremal problem for sets: a new approach via Bezoutians, J. Combin. Theory Ser. A 62 (1993) 170–175.


in}(Z)}\longrightarrow\overline{{in{Dm_{\omega}}}}$

The first follows from Lemma 2.2.7, especially (16), and Announcement 2.2.8,
especially (24). The next three follow directly from definitions (33). The
last equality has been proven in Lemma 3.5.5.

It follows that the equation below holds for functions $\overline{{\tt
in}(Z)}\longrightarrow\overline{{\tt out}(Z)}$:

$\mathcal{P}(\omega)(f)=S^{\prime\prime}_{\omega}\circ E_{\omega,f}\circ
S^{\prime}_{\omega}\circ C_{\omega,f}=S^{\prime\prime}_{\psi}\circ
E_{\psi,g}\circ S^{\prime}_{\psi}\circ
C_{\psi,g}=\mathcal{P}(\psi)(g)=\mathcal{P}(\psi)\circ\mathcal{P}(\phi)(f)$

Indeed, the left-hand equality and the second-to-last equality are by
definition of $\mathcal{P}$ on morphisms, as given in (34). The second
equality is found by a diagram chase using the six equations above. ∎

##  4\. Future work

The authors hope that this work can be put to use rather directly in modeling
and design applications. The relationship between the operad $\mathcal{W}$ and
its algebra $\mathcal{P}$ is quite explicitly a relationship between form and
function. The ability to zoom in and out, i.e. to change levels of abstraction
with ease is a facility which we believe is essential to any good theory of
the brain, computer programs, cyber-physical systems, etc.

Below we will discuss some possibilities for future work. We see three major
directions in which to go. The first is to connect this work to other work on
wiring diagrams. The second is to consider applications, e.g. to computer
science and cognitive neuroscience. The third is to investigate the notion of
dependency, or cause and effect, in our formalism. We discuss these in turn
below.

###  4.1. Connecting to other work on wiring diagrams

While wiring diagrams have been useful in engineering for many years, there
are a few mathematical approaches that should connect to our own, including
[AADF], [BB], [DL], and [Sp2].

The work by [AADF] studies dynamics inside of strongly connected (transitive)
networks of identical units. Their main aim is to relate the dynamics on the
network to properties of the underlying network architecture. The underlying
network should be viewed as analogous to a morphism $\psi$ in $\mathcal{W}$,
while the dynamics lying over the network should be viewed as analogous to the
morphism $\mathcal{P}(\psi)$. The cells in their networks are considered to
have internal states which collude with the inputs to produce the output of a
cell. There exists an algebra over $\mathcal{W}$ of “propagators with internal
states” and a retract from this algebra to $\mathcal{P}$, which should allow
the transfer of results of [AADF] to our framework. Arguably one of the main
aims of [AADF] is to introduce a notion of inflation for these networks. A
careful comparison, see for example [AADF, Figure 15] and [AADF, Figure 29],
reveals that their inflation procedure is a special case of the composition of
morphisms in $\mathcal{W}$ where the black boxes being inserted into a wiring
diagram come from a special class called inflations.

In [BB], the authors investigate reaction networks and in particular
stochastic Petri nets. There, various species (e.g. chemicals or populations)
interact in prescribed ways, and the dynamics of their changing populations
are studied. A similar but more complex situation is studied in [DL]. Both of
these papers work with continuous time processes, whereas we work with
discrete time processes. Still, we plan to investigate the relationship
between these ideas in the future.

The only other place, other than the present paper, where operads are
explicitly mentioned in the context of wiring diagrams seems to be [Sp2],
where the author studies systems of interacting relations using an operad
$\mathcal{T}$. One might think that an operad functor would appropriately
relate it to the present operad $\mathcal{W}$, but that does not appear to be
the case because of the delay nodes that exist in $\mathcal{W}$ but not
$\mathcal{T}$. Instead, these two operads need to be compared via a third, in
which delay nodes do not occur, but wires are still directed. We hope to make
this precise in the future.

###  4.2. Applications, e.g. to computer science and cognitive neuroscience

The authors’ primary purposes in the above work was to formalize what we
considered fundamental principles in the relation of form and function in both
computers and brains. On the operad/form level we are speaking of hierarchical
chunking; on the algebra/function level we are speaking of historical
propagators.

One can ask several interesting questions at this point. For example, can we
create from $\mathcal{W}$ and $\mathcal{P}$ a viable computer programming
language? We would hope that the propagators given by computable functions are
closed in, i.e. form a subalgebra of, $\mathcal{P}$. But perhaps one could ask
for more as well. For example, if each transistor in a computer acts like a
NOR gate, one could ask whether or not the subalgebra generated by NOR gates
is Turing complete. We conjecture that something like this is true. If so, we
believe our language will provide a simple, grounded, and useful perspective
on the actual operation of computers.

There are also many interesting questions on the neuroscience side that
motivated this work. These essentially amount to a question of “what”. What is
a neuron? What is a brain? What is the relationship between the actions of
individual neurons and the brain as a whole? It is easy to imagine that a
neuron is simply a black box where we assign certain multisets of
neurotransmitters to each input and output, the historical propagators would
then record activity patterns of discretized neurons. If this turns out to be
the case then the distinction between neuron and brain becomes blurred, each
is simply a black box with some specified inputs and outputs. From this
perspective the questions of how the activity of individual neurons relates to
the activity of a functional brain region or of the entire brain becomes
subsumed by the operad formalism where we can think of each as a different
choice of chunking within a single (massively complex) wiring diagram
representing the connections occurring within an entire brain. Deep questions
regarding precisely how the actions of neurons in one part of the brain
influence the activity in other areas will rely on the work of
neuroscientists’ understanding of the precise wiring pattern of the brain and
remain to be understood. We will speak more on these questions of dependency
within our formalism in the next section.

###  4.3. Investigating the notion of dependency

Given a propagator with $m$-inputs and $n$-outputs, one may ask about the
relation of dependency between them. When one says that the outcome of a
process is dependent on the inputs, this should mean that changing the inputs
will cause a change in the outputs.

In one form or another, the ability to track changes as they propagate through
a network of processes is one of the basic questions in almost any field of
research. Indeed, concern with notions of cause and effect is an essential
characteristic of human thought. Making mathematical sense of this notion
would presumably be immensely valuable. In particular, it should have direct
applications to neuroscience and computer programming disciplines.

It is not clear that there exists a reasonable notion of causality that is
algebraic in nature, i.e. one that can be formulated as a
$\mathcal{W}$-algebra receiving a morphism from $\mathcal{P}$. In that case we
may look to other approaches, e.g. that of Bayesian networks as in [Pea] and
[Fon]. Whether Bayesian networks also form an algebra on $\mathcal{W}$ or a
related operad, and how such an algebra compares with $\mathcal{P}$ should
certainly be investigated.

## References

  * [Awo] S. Awodey. (2010) Category theory. Second edition. Oxford Logic Guides, 52. Oxford University Press, Oxford.
  * [AADF] Aguiar, M., Ashwin, P., Dias, A., Field, M. (2010) “Dynamics of coupled cell networks: synchrony, heteroclinic cycles, and inflation”. Journal of nonlinear science, Springer.
  * [Bou] Bourbaki, N. (1972) “Univers”. In M. Artin et al. eds. SGA 4 - vol 1, Lecture Notes in Mathematics 269 (in French). Springer-Verlag pp. 185–217.
  * [BB] Baez, J.C., Biamonte, J. (2012). “A Course on Quantum Techniques for Stochastic Mechanics”. Available online, http://arxiv.org/abs/1209.3632.
  * [BV] Boardman, M.; Vogt, R. (1973) “Homotopy invariant algebraic structures on topological spaces.” Lecture notes in mathematics 347\. Springer-Verlag.
  * [BW] Barr M., Wells, C. (1990) Category theory for computing science. Prentice Hall International Series in Computer Science. Prentice Hall International, New York.
  * [DL] Deville, L., Lerman, E. (2013) “Dynamics on networks of manifolds”. Available online: http://arxiv.org/pdf/1208.1513v2.pdf.
  * [Fon] Fong, B. (2013) “Causal Theories: A Categorical Perspective on Bayesian Networks”. Available online http://arxiv.org/abs/1301.6201
  * [Lei] Leinster, T. (2004) Higher Operads, Higher Categories. London Mathematical Society Lecture Note Series 298, Cambridge University Press.
  * [Luc] Lucas, É. (1891), Théorie des nombres (in French) 1, Gauthier-Villars.
  * [Lur] Lurie, J. (2012) “Higher algebra”. http://www.math.harvard.edu/~lurie/papers/HigherAlgebra.pdf.
  * [Mac] (1998) Mac Lane, S. Categories for the working mathematician. Second edition. Graduate Texts in Mathematics, 5. Springer-Verlag, New York.
  * [Man] Manzyuk, O. (2009) “Closed categories vs. closed multicategories”. http://arxiv.org/abs/0904.3137
  * [May] May, P. (1972). The geometry of iterated loop spaces. Springer-Verlag.
  * [NIST] National Institute of Standards and Technology (1993). IDEF0: functional modeling method.
  * [Pea] Pearl, J. (2009) Causality: Models, reasoning, and inference. Cambridge University Press.
  * [Pen] Penrose, R. (2011). Cycles of time: An extraordinary new view of the universe. Random House.
  * [RS] Radul, A.; Sussman, G.J. (2009). “The art of the propagator”. MIT Computer science and artificial intelligence laboratory technical report.
  * [Sp1] Spivak, D.I. (2013) Category theory for scientists. http://arxiv.org/abs/1302.6946
  * [Sp2] Spivak, D.I. (2013) “The operad of wiring diagrams: Formalizing a graphical language for databases, recursion, and plug-and-play circuits.” ePrint available: http://arxiv.org/abs/1305.0297