Tight Bounds on Probabilistic Zero Forcing on Hypercubes and Grids

Zero forcing is an iterative graph colouring procedure which can model certain real-world propagation and search processes such as rumor spreading. Given a graph $G$ and a set of marked, or blue, vertices $Z\subseteq G$, the process of zero forcing involves the application of the zero forcing colour change rule in which a blue vertex $u$ forces a non-blue (white) vertex $v$ to become blue if $N(u)\setminus Z=\{v\}$, that is, $u$ forces $v$ to become blue if $v$ is the only white neighbour of $u$.

We say that $Z$ is a zero forcing set if when starting with $Z$ as the set of initially blue vertices, after iteratively applying the zero forcing colour change rule until no more vertices can be forced blue, the entire vertex set of $G$ becomes blue. Note that the order in which forces happen is arbitrary since if $u$ is in a position in which it can force $v$, this property will not be destroyed if other vertices are turned blue. As a result, we may process vertices sequentially (in any order) or all vertices that are ready to turn blue can do so simultaneously. The zero forcing number, denoted $z(G)$, is the cardinality of the smallest zero forcing set of $G$.

Zero forcing has sparked a lot of interest recently. Some work has been done on calculating or bounding the zero forcing number for specific structures such as graph products [12], graphs with large girth [8] and random graphs [1, 16], while others have studied variants of zero forcing such as connected zero forcing [4] or positive semi-definite zero forcing [2].

While zero forcing is a relatively new concept (first introduced in [12]), the problem has many applications to other branches of mathematics and physics. For example, zero forcing can give insight into linear and quantum controllability for systems that stem from networks. More precisely, in [5], it was shown that for both classical and quantum control systems that can be modelled by networks, the existence of certain zero forcing sets guarantees controllability of the system.

Another area closely related to zero forcing is power domination [19]. Designed to model the situation where an electric company needs to continually monitor their power network, one method that is used is to place phase measurement units (PMUs) periodically through their network. To reduce the cost associated with this, one asks for the least number of PMUs necessary to observe a specific network fully. To be more specific, given a network modelled with a simple graph $G$, a PMU placed at a vertex will be able to observe every adjacent vertex. Furthermore, if an observed vertex has exactly one unobserved neighbour, this observed vertex can observe this neighbour. In this way, power domination involves an observation rule compatible with the zero forcing colour change rule.

In the present paper we are concerned with a parameter associated with zero forcing known as the propagation time, which is the fewest number of rounds necessary for a zero forcing set of size $z(G)$ to turn the entire graph blue. More formally, given a graph $G$ and a zero forcing set $Z$, we generate a finite sequence of sets $Z_{0}\subsetneq Z_{1}\subsetneq\dots\subsetneq Z_{t}$, where $Z_{0}=Z$, $Z_{t}=V(G)$, and given $Z_{i}$, we define $Z_{i+1}=Z_{i}\cup Y_{i}$, where $Y_{i}\subseteq V(G)\setminus Z_{i}$ is the set of white vertices that can be forced in the next round if $Z_{i}$ is the set of the blue vertices. Then the propagation time of $Z$, denoted $pt(G,Z)$, is defined to be $t$. The propagation time of the graph $G$ is then given by $pt(G)=\min_{Z}pt(G,Z)$, where the minimum is taken over all zero forcing sets $Z$ of cardinality $z(G)$. The propagation time for zero forcing has been studied in [13].

Zero forcing was initially formulated to bound a problem in linear algebra known as the min-rank problem [12]. In addition to this application to mathematics, zero forcing also models many real-world propagation processes. One specific application of zero forcing could be to rumor spreading, but the deterministic nature of zero forcing may not fit the chaotic nature of real-life situations. As such, probabilistic zero forcing has also been proposed and studied where blue vertices have a non-zero probability of forcing white neighbours, even if there is more than one white neighbour. More specifically, given a graph $G$, a set of blue vertices $Z$, and vertices $u\in Z$ and $v\in V(G)\setminus Z$ such that $uv\in E(G)$, in a given time step, vertex $u$ will force vertex $v$ to become blue with probability

where $N[u]$ is the closed neighbourhood of $u$.

In a given round, each blue vertex will attempt to force each white neighbour independently. If this happens, we may say that the edge $uv$ is forced. A vertex becomes blue as long as it is forced by at least one blue neighbour, or in other words if at least one edge incident with it is forced. Note that if $v$ is the only white neighbour of $u$, then with probability $1$, $u$ forces $v$, so given an initial set of blue vertices, the set of vertices forced via probabilistic zero forcing is always a superset of the set of vertices forced by traditional zero forcing. In this sense, probabilistic zero forcing and traditional zero forcing can be coupled. In the context of rumor spreading, the probabilistic colour change rule captures the idea that someone is more likely to spread a rumor if many of their friends have already heard the rumor.

Under probabilistic zero forcing, given a connected graph, it is clear that starting with any non-empty subset of blue vertices will with probability 1 eventually turn the entire graph blue, so the zero forcing number of a graph is not an interesting parameter to study for probabilistic zero forcing. Initially in [17], the authors studied a parameter that quantifies how likely it is for a subset of vertices to become a traditional zero forcing set the first time-step that it theoretically could under probabilistic zero forcing.

Instead, in this paper, we will be concerned with a parameter that generalizes the zero forcing propagation time. This generalization was first introduced in [11]. Given a graph $G$, and a set $Z\subseteq V(G)$, let $pt_{pzf}(G,Z)$ be the random variable that outputs the propagation time when probabilistic zero forcing is run with the initial blue set $Z$. For ease of notation, we will write $pt_{pzf}(G,v)=pt_{pzf}(G,\{v\})$. The propagation time for the graph $G$ will be defined as the random variable $pt_{pzf}(G)=\min_{v\in V(G)}pt_{pzf}(G,v)$. More specifically, $pt_{pzf}(G)$ is a random variable for the experiment in which $n$ iterations of probabilistic zero forcing are performed independently, one for each vertex of $G$, then the minimum is taken over the propagation times for these $n$ independent iterations.

Our results are asymptotic in nature, that is, we will assume that $n\to\infty$. Formally, we consider a sequence of graphs $G_{n}=(V_{n},E_{n})$ (for example, $G_{n}$ is an $n$-dimensional hypercube or $n$ by $n$ grid) and we are interested in events that hold asymptotically almost surely (a.a.s.), that is, events that hold with probability tending to 1 as $n\to\infty$.

Given two functions $f=f(n)$ and $g=g(n)$, we will write $f(n)=O(g(n))$ if there exists an absolute constant $c\in{\mathbb{R}}_{+}$ such that $|f(n)|\leq c|g(n)|$ for all $n$, $f(n)=\Omega(g(n))$ if $g(n)=O(f(n))$, $f(n)=\Theta(g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, and we write $f(n)=o(g(n))$ or $f(n)\ll g(n)$ if $\lim_{n\to\infty}f(n)/g(n)=0$. In addition, we write $f(n)\gg g(n)$ if $g(n)=o(f(n))$ and we write $f(n)\sim g(n)$ if $f(n)=(1+o(1))g(n)$, that is, $\lim_{n\to\infty}f(n)/g(n)=1$.

Finally, as typical in the field of random graphs, for expressions that clearly have to be an integer, we round up or down but do not specify which: the choice of which does not affect the argument.

In [11], the authors studied probabilistic zero forcing, and more specifically the expected propagation time for many specific structures. A summary of this work is provided in the following theorem.

In [6], the authors used tools developed for Markov chains to analyze the expected propagation time for many small graphs. The authors also showed, in addition to other things, that $\min_{v\in V(K_{n})}\mathbb{E}(pt_{pzf}(K_{n},v))=\Theta(\log\log n)$ and for any connected graph $G$, $\min_{v\in V(G)}\mathbb{E}(pt_{pzf}(G,v))=O(n)$. This result was then improved in [18], where the authors showed that

for general connected graphs $G$. In the same paper, the authors also showed that

where $r\geq 1$ denotes the radius of the connected graph $G$. Moreover, they provided a class of graphs for which the bounds of the theorem are tight.

In addition to the results mentioned above, the authors of [11] also considered the binomial random graph ${\cal G}(n,p)$, proving the following theorem.

The results of most interest to us are from [14]. The authors of that paper are concerned with hypercubes $Q_{n}$ and grids $G_{m\times n}$, and prove the following result.

In this paper, we improve both results from [14]. Instead of considering the expectation of the propagation time, we will calculate bounds on the propagation time that a.a.s. hold. The lower bounds for both families of graphs are trivial so the improvement is for the upper bounds.

The bounds for $Q_{n}$ are asymptotically tight. Unfortunately, we could not prove the matching upper bound for $G_{m\times n}$ but our upper bound is very tight, and so it supports the conjecture that a.a.s. $pt_{pzf}(G_{n\times n})\sim n$. This conjecture is supported by independent simulations performed in [14] as well as our own.

Let us first state a specific instance of Chernoff’s bound that we will find useful. Let $X\in\textrm{Bin}(n,p)$ be a random variable with the binomial distribution with parameters $n$ and $p$. Then, a consequence of Chernoff’s bound (see e.g. [15, Corollary 2.3]) is that

for $0<\varepsilon<3/2$. Moreover, let us mention that the bound holds for the general case in which $X=\sum_{i=1}^{n}X_{i}$ and $X_{i}\in\textrm{Bernoulli}(p_{i})$ with (possibly) different $p_{i}$ (again, e.g. see [15] for more details).

Let $X_{0},X_{1},\ldots$ be an infinite sequence of random variables that make up a martingale; that is, for any $a\in{\mathbb{N}}$ we have $\mathbb{E}[X_{a}|X_{a-1}]=X_{a-1}$. Suppose that there exist constants $c_{a}>0$ such that $|X_{a}-X_{a-1}|\leq c_{a}$ for each $a\leq t$. Then, the Hoeffding–Azuma inequality implies that for every $b>0$,

This result is due to Chung, Lam, Liu and Mitzenmacher [7]. Let $M$ be a discrete time ergodic Markov chain with state space $[n]$ and the stationary distribution $\pi$. $M$ may be interpreted as either the chain itself or the corresponding $n$ by $n$ transition matrix. The total variation distance between $u$ and $w$, two distributions over $[n]$, is defined as

For any $\varepsilon>0$, the mixing time of Markov chain $M$ is defined as

where $x$ is an arbitrary initial distribution. We will also need a definition of the $\pi$-norm. The inner product under the $\pi$-kernel is defined as $\langle u,v\rangle_{\pi}=\sum_{i\in[n]}u_{i}v_{i}/\pi_{i}$. Then, the $\pi$-norm of $u$ is defined as $\left\lVert u\right\rVert_{\pi}=\sqrt{\langle u,u\rangle_{\pi}}$. Note that, in particular, $\left\lVert\pi\right\rVert_{\pi}=1$.

Now we are ready to state the main result from [7]. Let $T=T(\varepsilon)$ be the $\varepsilon$-mixing time of Markov chain $M$ for $\varepsilon\leq 1/8$. Let $(V_{1},V_{2},\ldots,V_{t})$ denote a $t$-step random walk on $M$ starting from an initial distribution $\varphi$ on $[n]$. For every $i\in[t]$, let $f_{i}:[n]\rightarrow[0,1]$ be a weight function at step $i$ such that the expected weight $\mathbb{E}_{v\leftarrow\pi}[f_{i}(v)]=\mu$ for all $i$. Define the total weight of the walk by $X=\sum^{t}_{i=1}f_{i}(V_{i})$. There exists some constant $c$ (which is independent of $\mu$, $\delta$ and $\epsilon$) such that for $0\leq\delta\leq 1$

We will be using the following obvious coupling to simplify both upper and lower bounds. Having said that, in our case we will only need to prove upper bounds. Indeed, for lower bounds, it might be convenient to make some white vertices blue at some point of the process. Similarly, for upper bounds, one might want to make some blue vertices white. Given a graph $G$, $S,T\subseteq V(G)$, and $\ell\in{\mathbb{N}}$, let $A(S,T,\ell)$ be the event that starting with blue set $S$, after $\ell$ rounds every vertex in $T$ is blue. The following simple observation was proved in [9].