Zero Forcing with Random Sets

Bryan Curtis¹¹1Department of Mathematics, Iowa State University [email protected]. This work is partially supported by NSF grant 1839918. Luyining Gan²²2Department of Mathematics and Statistics, University of Nevada Reno [email protected]. This work is supported by AMS-Simons Travel Grant 2022-2024. Jamie Haddock³³3Department of Mathematics, Harvey Mudd College [email protected]. This work is supported by NSF DMS award #2211318. Rachel Lawrence⁴⁴4Department of Electrical Engineering and Computer Science, University of California, Berkeley [email protected]. Sam Spiro⁵⁵5Department of Mathematics, UCSD [email protected]. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1650112.

Abstract

Given a graph $G$ and a real number $0\leq p\leq 1$ , we define the random set $B_{p}(G)\subseteq V(G)$ by including each vertex independently and with probability $p$ . We investigate the probability that the random set $B_{p}(G)$ is a zero forcing set of $G$ . In particular, we prove that for large $n$ , this probability for trees is upper bounded by the corresponding probability for a path graph. Given a minimum degree condition, we also prove a conjecture of Boyer et. al. regarding the number of zero forcing sets of a given size that a graph can have.

Keywords: Random set zero forcing, Zero forcing polynomial, Random graphs, Graph threshold.

1 Introduction

Let $G$ be a graph with vertex set $V(G)$ initially colored either blue or white. If $u$ is a blue vertex of $G$ and the neighborhood $N_{G}(u)$ of $u$ contains exactly one white vertex $v$ , then we may change the color of $v$ to blue. This iterated procedure of coloring a graph is called zero forcing. A zero forcing set $B$ is a subset of vertices of $G$ such that if $G$ initially has all of the vertices of $B$ colored blue, then the zero forcing process can eventually color all of $V(G)$ blue. We let $\operatorname{ZFS}(G)$ denote the set of all zero forcing sets of $G$ . The zero forcing number $Z(G)$ is the minimum cardinality of a zero forcing set in $G$ ; that is, $Z(G)=\min_{B\in\operatorname{ZFS}(G)}|B|$ . The zero forcing process was first introduced by Burgarth and Giovannetti [BG07], and the zero forcing number was introduced by an AIM’s research group [Gro08] as a bound for the maximum nullity of a graph $G$ .

(a)

(b)

(c)

Figure 1: An example of zero forcing on a graph.

In this paper we consider a randomized version of the zero forcing process. There are seemingly two natural ways to define such a random process: one can either use a deterministic set of blue vertices $B$ together with forces that occur randomly, or one can use a random set of vertices together with deterministic forces. The process known as probabilistic zero forcing, which was introduced by Kang and Yi [KY13], is of the former type and is by now well studied, see for example [CCG⁺20, GH18, NS21, EMPa21, HS20]. In this paper we introduce a process of the latter type which we call random set zero forcing.

1.1 Main Results

Given a graph $G$ and real number $0\leq p\leq 1$ , we define the random set $B_{p}(G)\subseteq V(G)$ by including each vertex of $G$ independently and with probability $p$ . For example, $B_{1}(G)=V(G)$ , $B_{0}(G)=\emptyset$ , and $B_{1/2}(G)$ is equally likely to be any subset of $V(G)$ .

The central problem we wish to ask is, given $G$ and $p$ , what is (approximately) the probability that $B_{p}(G)$ is a zero forcing set of $G$ ? For example, one general bound we can prove is the following.

Theorem 1.1.

Let $G$ be an $n$ -vertex graph with minimum degree at least $\delta\geq 1$ . For all $p$ , we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\delta np^{\delta}.

In fact, we prove a slightly stronger version of this theorem that holds for graphs with “few” vertices of degree less than $\delta$ ; see Theorem 3.3. Theorem 1.1 can be viewed as a probabilistic analog to the basic fact that $Z(G)\geq\delta$ if $G$ is a graph with minimum degree $\delta$ .

Many other results from classical zero forcing also have probabilistic analogs for random set zero forcing. For example, it is straightforward to show that if $G$ is an $n$ -vertex graph, then $Z(G)\leq Z(\overline{K_{n}})$ with equality if and only if $G=\overline{K_{n}}$ . In the random setting, it is also easy to show the analogous result that for all $n$ -vertex graphs $G$ and $0\leq p\leq 1$ , we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\geq\Pr[B_{p}(\overline{K_{n}})\in\operatorname{ZFS}(\overline{K_{n}})],

with equality holding if and only if either $p\in\{0,1\}$ or $G=\overline{K_{n}}$ .

In the classical setting, it is well known that amongst $n$ -vertex graphs, the path $P_{n}$ is the unique graph with the smallest zero forcing number. We conjecture that an analog of this result holds in the random setting.

Conjecture 1.2.

If $G$ is an $n$ -vertex graph and $0\leq p\leq 1$ , then

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})],

with equality holding if and only if either $p\in\{0,1\}$ or $G=P_{n}$ .

While we do not prove this conjecture in full, we provide some partial results; in particular, we prove the conjecture when restricted to trees and with $n$ sufficiently large.

Theorem 1.3.

If $T$ is an $n$ -vertex tree with $n$ sufficiently large, then for all $0\leq p\leq 1$ ,

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})],

with equality holding if and only if either $p\in\{0,1\}$ or $T=P_{n}$ .

For many graphs $G$ , it will happen that there exists a $p$ such that $B_{p^{\prime}}(G)$ is very unlikely to be a zero forcing set if $p^{\prime}$ is much smaller than $p$ , and that $B_{p^{\prime}}(G)$ is very likely to be zero forcing if $p^{\prime}$ is much larger than $p$ , see for example Figure 2. To capture what this value of $p$ is, we define the threshold probability $p(G)$ to be the unique $p$ such that $\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]=\frac{1}{2}$ , and it is not difficult to see that $p(G)$ is well defined. This definition is motivated by the study of thresholds in random graphs, which is one of the fundamental topics in probabilistic combinatorics (see, for example [FK16]).

Figure 2: Exact (left) and Monte Carlo estimates (right) of

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]

for the path, square grid, hypercube, and left-complete binary tree graphs on 16 and 256 vertices respectively.

We note that if Conjecture 1.2 were true, then in particular we would have $p(G)>p(P_{n})$ for all $n$ -vertex graphs $G\neq P_{n}$ ; we subsequently prove that this is true up to a constant factor. Here and throughout the paper we use standard asymptotic notation, which is recalled in Subsection 1.2.

Theorem 1.4.

If $G$ is an $n$ -vertex graph, then

p(G)=\Omega(p(P_{n}))=\Omega(n^{-1/2}).

In essence this result says that a random set of much less than $n^{1/2}$ vertices of any $n$ -vertex graph $G$ is very unlikely to be a zero forcing set for sufficiently large $n$ .

Conjecture 1.2 can be viewed as a weakened version of a conjecture involving the number of zero forcing sets of a given size. To this end, we observe that if $G$ is an $n$ vertex graph and $z(G;k)$ is the number of zero forcing sets of $G$ of size $k$ , then

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]=\sum_{k=1}^{n}z(G;k)p^{k}(1-p)^{n-k}.

(1)

The notation $z(G;k)$ follows that of Boyer et. al. in [BBE⁺19] who introduced the study of zero forcing polynomials and found many explicit formulas for $z(G;k)$ , including:

z(P_{n};k)=\binom{n}{k}-\binom{n-k-1}{k}.

(2)

Observe that, by (1), Conjecture 1.2 is a weakened version of the following conjecture.

Conjecture 1.5 ([BBE⁺19]).

If $G$ is an $n$ -vertex graph, then for all $k$ ,

z(G;k)\leq z(P_{n};k)={n\choose k}-{n-k-1\choose k}.

It was shown in [BBE⁺19] that Conjecture 1.5 holds whenever $G$ contains a Hamiltonian path, but other than this very little is known. By extending our proof of Theorem 1.1, we prove Conjecture 1.5 whenever $k$ is sufficiently small, as a function of the minimum degree of $G$ .

Proposition 1.6.

If $G$ is an $n$ -vertex graph with minimum degree $\delta\geq 3$ , then for all $k\leq(2\delta)^{-1/\delta}n^{1-1/\delta}$ we have $z(G;k)\leq z(P_{n};k)$ .

We additionally show that this implies Conjecture 1.5 whenever $G$ has sufficiently large minimum degree.

Corollary 1.7.

If $G$ is an $n$ -vertex graph with minimum degree $\delta\geq\log_{2}(n)+2\log_{2}\log_{2}(n)$ , then $z(G;k)\leq z(P_{n};k)$ for all $k$ .

1.2 Organization and Notation

This paper is organized as follows. In Section 2, we provide specific bounds on the threshold probability for several families of graphs and some graph operations. In Section 3, we provide a general bound on the probability that $B_{p}(G)$ is zero forcing given the minimum degree. In Section 4, we prove that the threshold probability for an $n$ -vertex graph $G$ is $\Omega(n^{-1/2})$ . In Section 5, we prove that amongst trees on sufficiently many vertices, paths have the largest probability of $B_{p}(G)$ being a zero forcing set. We conclude with some remarks and open questions in Section 6.

Throughout we use standard asymptotic notation. Let $f(n)$ and $g(n)$ be functions from the non-negative integers to the reals. We write $f(n)=o(g(n))$ if $\lim_{n\to\infty}{f(n)}/{g(n)}=0$ , and $f(n)=O(g(n))$ if there exists a $C>0$ such that $f(n)\leq Cg(n)$ for all sufficiently large $n$ . We write $f(n)=\Omega(g(n))$ if $g(n)=O(f(n))$ , and $f(n)=\Theta(g(n))$ if both $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ . We write, for example, $\Theta_{k}(g(n))$ if the implicit constants depend on $k$ .

2 Threshold Probabilities for Families of Graphs

In this section we analyze the threshold probability for some families of graphs. These results provide an introduction to the various probabilistic and zero forcing arguments made throughout this paper, and also highlight some of the interesting properties of random set zero forcing.

We make use of the following inequalities throughout this section. Recall that

1-x\leq e^{-x}

(3)

for all real values $x$ , and

\left(1-\frac{c}{n}\right)^{n}\geq 1-c

(4)

for $|c|\leq n$ and $n\geq 1$ .

Let $G$ be a graph on $n\geq 2$ vertices with no isolated vertices. It is well known that every subset of $V(G)$ of size $n-1$ is a zero forcing set of $G$ , and that $Z(G)=n-1$ if and only if $G=K_{n}$ , the complete graph on $n$ vertices (see, for example, [HLS22]). These observations imply the following.

Proposition 2.1.

If $G$ is a graph on $n$ vertices with no isolated vertices, then $p(G)\leq p(K_{n})$ . Moreover, $p(K_{n})=1-\Theta(n^{-1})$ .

Proof.

The result is immediate for $n=1$ , so assume $n\geq 2$ . Define

f(p)=n(1-p)p^{n-1}+p^{n},

which is the probability that $B_{p}(G)$ contains at least $n-1$ vertices. Since every subset of $V(G)$ of size $n-1$ is a zero forcing set, we have for $p\in[0,1]$ ,

\text{Pr}\left[B_{p}(G)\in\operatorname{ZFS}(G)\right]\geq f(p)=\text{Pr}\left[B_{p}(K_{n})\in\operatorname{ZFS}(K_{n})\right],

where this equality used that a set $S$ is a zero forcing set of $K_{n}$ if and only if $|S|\geq n-1$ . Since $\text{Pr}\left[B_{p}(G)\in\operatorname{ZFS}(G)\right]$ and $\text{Pr}\left[B_{p}(K_{n})\in\operatorname{ZFS}(K_{n})\right]$ are increasing functions of $p$ , we conclude that $p(G)\leq p(K_{n})$ .

We now prove the asymptotic result. Let $p=1-c/n$ , where $c\leq n$ is positive. By (4),

f(p)\geq p^{n}\geq 1-c,

which implies $f(p)>1/2$ if $p>1-\frac{1}{2n}$ . Similarly, by (3),

f(p)=c(1-c/n)^{n-1}+(1-c/n)^{n}\leq ce^{-c+c/n}+e^{-c}\leq ce^{-c/2}+e^{-c},

where the last inequality holds since $n\geq 2$ . Thus $f(p)<1/2$ for $n\geq 5$ and $p<1-\frac{5}{n}$ . We conclude $p(K_{n})=1-\Theta(n^{-1})$ . ∎

By allowing for isolated vertices, it is possible for an $n$ -vertex graph to have a higher threshold probability than $K_{n}$ . Indeed, it is easy to show that the largest threshold probability amongst all graphs on $n$ vertices is $p(nK_{1})$ , where $nK_{1}$ denotes the graph on $n$ isolated vertices. In fact, we can use Observation 2.2 stated below to give the exact result $p(nK_{1})=2^{-1/n}$ . Moreover, Observation 2.2 allows us to reduce our focus to connected graphs.

Observation 2.2.

Let $G$ be the disjoint union of the graphs $G_{1}$ and $G_{2}$ . Then

\text{Pr}\left[B_{p}(G)\in\operatorname{ZFS}(G)\right]=\text{Pr}\left[B_{p}(G_{1})\in\operatorname{ZFS}(G_{1})\right]\cdot\text{Pr}\left[B_{p}(G_{2})\in\operatorname{ZFS}(G_{2})\right].

While it is straightforward to determine the graphs with the largest threshold probabilities, the analogous problem for smallest thresholds appears much harder. Intuitively, the path graph $P_{n}$ is a natural candidate for the minimizer, since it is known that $P_{n}$ is the unique $n$ -vertex graph with zero forcing number 1.

Towards this end, we establish the order of magnitude of $p(P_{n})$ . By convention, we assume the vertices $v_{1},\ldots,v_{n}$ of $P_{n}$ are in path order, i.e., the edges of $P_{n}$ are $v_{i}v_{i+1}$ for $1\leq i\leq n-1$ . Note that $S\subseteq V(P_{n})$ is a zero forcing set if and only if $S$ contains an endpoint or $S$ contains two consecutive vertices (see Figure 3).

Refer to caption — Figure 3: Three zero forcing sets for $P_{5}$

Proposition 2.3.

The threshold probability of the path on $n$ vertices satisfies

p(P_{n})=\Theta(n^{-1/2}).

Proof.

Let $v_{1},\ldots,v_{n}$ denote the vertices of $P_{n}$ (in path order). Define the random variable $X$ to be the number of indices $i\in\{1,2,\cdots,n-1\}$ such that $v_{i},v_{i+1}\in B_{p}(P_{n})$ . Markov’s inequality yields

\text{Pr}\left[X\geq 1\right]\leq\mathbb{E}[X]=(n-1)p^{2}.

Since $B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})$ if and only if either $X\geq 1$ or at least one of $v_{1},v_{n}\in B_{p}(P_{n})$ , a union bound now implies

\text{Pr}\left[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})\right]\leq(n-1)p^{2}+2p.

This quantity is less than $1/2$ provided $p=cn^{-1/2}$ for any $c<1/4$ . Thus $p(P_{n})=\Omega(n^{-1/2})$ .

Next, for $i\in\{1,2,\ldots,n-1\}$ , let $A_{i}$ be the event that $v_{i},v_{i+1}\in B_{p}(P_{n})$ , and define $\displaystyle A=\bigcup_{i\text{ odd}}A_{i}$ . Then,

	$\displaystyle\text{Pr}\left[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})\right]$	$\displaystyle\geq\text{Pr}\left[A\right]=1-\prod_{i\text{ odd}}(1-\text{Pr}\left[A_{i}\right])$
		$\displaystyle=1-(1-p^{2})^{\lfloor(n-1)/2\rfloor}\geq 1-e^{-p^{2}\lfloor(n-1)/2\rfloor},$

where the first equality follows from the fact that these events are independent, and the last inequality follows from (3). This probability will be greater than $1/2$ for $p=Cn^{-1/2}$ with $C$ sufficiently large. We conclude that $p(P_{n})=\Theta(n^{-1/2})$ . ∎

A similar bound holds for the cycle graph $C_{n}$ .

Proposition 2.4.

The threshold probability of the cycle on $n$ vertices satisfies

p(C_{n})=\Theta(n^{-1/2}).

Proof.

Observe that $S$ is a zero forcing set of $C_{n}$ if and only if $S$ contains a pair of consecutive vertices. Thus, using an argument similar to the proof of Proposition 2.3, we find

1-(1-p^{2})^{\lfloor(n-1)/2\rfloor}\leq\text{Pr}\left[B_{p}(C_{n})\in\operatorname{ZFS}(C_{n})\right]\leq np^{2}.

We conclude that $p(C_{n})=\Theta(n^{-1/2})$ . ∎

It is perhaps intuitive that $p(C_{n})\approx p(P_{n})$ since $C_{n}$ can be formed from $P_{n}$ by adding a single edge. However, there are examples where this intuition fails. Indeed, let $v_{1},\ldots,v_{n}$ be the vertices of $P_{n}$ , and let $R_{n}$ denote the graph obtained from $P_{n}$ by adding the edge $v_{1}v_{3}$ (see Figure 4).

Proposition 2.5.

The threshold probability of the triangle with a pendant path on $n$ vertices satisfies

p(R_{n})=\Theta(1).

Proof.

Note that any zero forcing set of $R_{n}$ must contain either $v_{1}$ or $v_{2}$ . Thus,

\text{Pr}\left[B_{p}(R_{n})\in\operatorname{ZFS}(R_{n})\right]\leq\text{Pr}\left[v_{1}\in B_{p}(R_{n})\text{ or }v_{2}\in B_{p}(R_{n})\right]\leq 2p.

This implies $p(R_{n})\in[1/4,1]$ , and hence $p(R_{n})=\Theta(1)$ . ∎

Remark 2.6.

In the deterministic setting, it is well known that the zero forcing number $Z(G)$ of a graph $G$ changes by at most one if a single edge or vertex is removed from $G$ . This is far from true for $p(G)$ . Indeed, recall that $p(P_{n})=\Theta(n^{-1/2})$ . Let $P^{\prime}_{n}$ be obtained by deleting the edge $v_{1}v_{2}$ . Since $P^{\prime}_{n}$ has $K_{1}$ as a connected component, by Observation 2.2 we have $p(P^{\prime}_{n})\geq p(K_{1})=\frac{1}{2}$ . A similar result holds if one deletes $v_{2}$ .

We next show that deleting edges or vertices can dramatically decrease $p(G)$ . Consider the triangle with pendant path $R_{n}$ , which has $p(R_{n})=\Theta(1)$ . If one deletes $v_{1}$ , then the resulting graph is $P_{n-1}$ , which has $p(P_{n-1})=\Theta(n^{-1/2})$ . If one deletes the edge $v_{1}v_{3}$ , then the resulting graph is $P_{n}$ , which has $p(P_{n})=\Theta(n^{-1/2})$ .

We end with a table that summarizes our main results of this section and states (without proof) other results that can be obtained using our methods.

Table 1: Thresholds for graph families.

Family	Description	Threshold Probability
$K_{n}$	Complete graph on $n$ vertices: Proposition 2.1	$1-\Theta(n^{-1})$
$nK_{1}$	Graph on $n$ isolated vertices	$2^{-1/n}$
$K_{n_{1},\cdots,n_{k}}$	Complete multipartite graph	$1-\Theta_{k}(\min_{i}\{n_{i}^{-1}\})$
$P_{n}$	Path on $n$ vertices: Proposition 2.3	$\Theta(n^{-1/2})$
$C_{n}$	Cycle on $n$ vertices: Proposition 2.4	$\Theta(n^{-1/2})$
$W_{n}$	Wheel on $n$ vertices: $C_{n-1}+K_{1}$	$\Theta(n^{-1/3})$

3 Bounds Using Degrees

In this section we prove bounds on the probability that $B_{p}(G)$ is a zero forcing set in terms of the degree sequence of $G$ . Our most general bound of this form is the following, where here and throughout $d(v)$ denotes the degree of $v$ in the graph $G$ .

Lemma 3.1.

Let $G$ be an $n$ -vertex graph with at least one edge and $p\in[0,1]$ . Then

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\sum_{v\in V(G)}d(v)p^{d(v)}.

Proof.

Let $A$ be the event that $B_{p}(G)=V(G)$ . For any $v\in V(G)$ , let $F_{v}$ be the event that $v$ and exactly $d(v)-1$ of its neighbors are in $B_{p}(G)$ . We claim that for $B_{p}(G)$ to be a zero forcing set, either $A$ or $F_{v}$ for some $v$ must occur. Indeed, if $B_{p}(G)\neq V(G)$ and $B_{p}(G)$ is a zero forcing set, then there must be some blue vertex $v$ in $B_{p}(G)$ that forces a white vertex to be blue. In particular, if $v$ is the first vertex which performs such a force, then it and exactly $d(v)-1$ of its neighbors must be in $B_{p}(G)$ . This proves our claim. Thus by the union bound we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\Pr[A\cup\bigcup F_{v}]\leq\Pr[A]+\sum_{v\in V(G)}\Pr[F_{v}].

By definition, the event $F_{v}$ occurring means $v$ is included in $B_{p}(G)$ and exactly $d(v)-1$ of its $d(v)$ neighbors are included in $B_{p}(G)$ . As each vertex is included in $B_{p}(G)$ independently and with probability $p$ , we have

\Pr[F_{v}]=p\cdot{d(v)\choose d(v)-1}p^{d(v)-1}(1-p)=d(v)p^{d(v)}(1-p).

Plugging this into the bound above and using $\Pr[A]=p^{n}$ gives

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq p^{n}+\sum_{v\in V(G)}d(v)p^{d(v)}(1-p).

(5)

By assumption, $G$ contains a vertex $u$ with $d(u)\geq 1$ . For this vertex we have

d(u)p^{d(u)}(1-p)=d(u)p^{d(u)}-d(u)p^{d(u)+1}\leq d(u)p^{d(u)}-p^{n},

where this last step used $d(u)\geq 1$ and $d(u)+1\leq n$ (which always holds for $n$ -vertex graphs). Plugging this bound into (5), and using the bound $d(v)p^{d(v)}(1-p)\leq d(v)p^{d(v)}$ for every other term of the sum gives the desired result. ∎

We also make use of the following, which can be proven using calculus.

Observation 3.2.

If $d$ is a positive integer and $p\leq e^{-1/d}$ , then

\max_{x\geq d}xp^{x}=dp^{d}.

This result quickly gives Theorem 1.1, which we restate below.

Theorem 1.1.

Let $G$ be an $n$ -vertex graph with minimum degree at least $\delta\geq 1$ . For all $p$ , we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\delta np^{\delta}.

Proof.

When $G=K_{2}$ the theorem is equivalent to $2p(1-p)+p^{2}\leq 2p$ , i.e. that $-p^{2}\leq 0$ , so the result holds. From now on we assume $G$ has at least 3 vertices. For all $p$ and $n\geq 3$ , we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq e^{-1}\delta n

since $e^{-1}\delta n\geq 1$ . This implies the result when $p\geq e^{-1/\delta}$ .

Observation 3.2 together with Lemma 3.1 and the fact that $d(v)\geq\delta$ for all $v$ gives

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\sum_{v\in V(G)}d(v)p^{d(v)}\leq\delta np^{\delta}.\qed

We next prove a slightly stronger version of this theorem which holds for graphs with “few” vertices of degree less than a given degree $d$ .

Theorem 3.3.

Let $G$ be an $n$ -vertex graph without isolated vertices. Suppose that there exist integers $1\leq d\leq n$ and $N\geq 0$ such that $G$ contains at most $N^{k}$ vertices of degree $k$ for all $1\leq k<d$ . Then for all $p\leq e^{-1/d}$ , we have

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq 4pN+dnp^{d}.

Proof.

The result is trivial if $pN>\frac{1}{2}$ , so we can assume $pN\leq\frac{1}{2}$ . Using Observation 3.2 together with Lemma 3.1 and the assumptions on $G$ , we find

	$\displaystyle\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]$	$\displaystyle\leq\sum_{v\in V(G)}d(v)p^{d(v)}\leq\sum_{\begin{subarray}{c}v\in V(G)\\ d(v)<d\end{subarray}}d(v)p^{d(v)}+\sum_{\begin{subarray}{c}v\in V(G)\\ d(v)\geq d\end{subarray}}dp^{d}$
		$\displaystyle\leq\sum_{k=1}^{d-1}k(pN)^{k}+dnp^{d}\leq\sum_{k=1}^{\infty}k(pN)^{k}+dnp^{d}.$

Note that in general we have $\sum_{k=1}^{\infty}kc^{k}=\frac{c}{(c-1)^{2}}$ provided $|c|<1$ . Applying this with $c=pN\leq\frac{1}{2}$ gives the desired result. ∎

We now prove analogs of these results for $z(G;k)$ .

Lemma 3.4.

Let $G$ be an $n$ -vertex graph with at least one edge. Then for all non-negative integers $k$ ,

z(G;k)\leq\sum_{v\in V(G)}d(v){n-d(v)\choose k-d(v)}.

Proof.

The result is trivial if $k=n$ . For $k<n$ , every zero forcing set $S$ must contain some vertex $v$ of positive degree and exactly $d(v)-1$ of its neighbors in order to have a vertex force. Thus every zero forcing set of size $k$ can be constructed by first including a vertex $v$ , then including exactly $d(v)-1$ of its neighbors, then arbitrarily including $k-d(v)$ additional vertices. In total the number of ways to construct such a set is

\sum_{v\in V(G)}{d(v)\choose d(v)-1}{n-d(v)\choose k-d(v)}=\sum_{v\in V(G)}d(v){n-d(v)\choose k-d(v)},

so $G$ has at most this many zero forcing sets of size $k$ . ∎

We next need the following lower bound on $z(P_{n};k)$ .

Lemma 3.5.

For all non-negative integers $k$ we have

z(P_{n};k)\geq\frac{k^{2}}{n+k^{2}}{n\choose k}.

Proof.

Recall that (2) states $z(P_{n};k)={n\choose k}-{n-k-1\choose k}$ for all $k$ . Observe that

\begin{split}\frac{{n-k-1\choose k}}{{n\choose k}}=&\frac{(n-k-1)(n-k-2)\cdots(n-2k)}{n(n-1)\cdots(n-k+1)}=\prod_{i=0}^{k-1}\left(1-\frac{k+1}{n-i}\right)\\ \leq&\left(1-\frac{k}{n}\right)^{k}\leq\frac{1}{1+k^{2}/n}=\frac{n}{n+k^{2}},\end{split}

where this last inequality follows from the Bernoulli inequality; see e.g., [LY13, Equation $(r^{\prime}_{5})$ ]. This implies

z(P_{n};k)={n\choose k}-{n-k-1\choose k}\geq\left(1-\frac{n}{n+k^{2}}\right){n\choose k}=\frac{k^{2}}{n+k^{2}}{n\choose k}.\qed

We now prove Proposition 1.6, which we restate below.

Proposition 1.6.

Let $G$ be an $n$ -vertex graph with minimum degree $\delta\geq 3$ and $k\leq(2\delta)^{-1/\delta}n^{1-1/\delta}$ . Then $z(G;k)\leq z(P_{n};k)$ .

Proof.

By (2), for $k\geq n/2$ we have $z(P_{n};k)={n\choose k}$ . Thus we may assume throughout that $k\leq n/2$ .

Observe that for all $t$ ,

{n-t\choose k-t}/{n\choose k}=\frac{k(k-1)\cdots(k-t+1)}{n(n-1)\cdots(n-t+1)}\leq(k/n)^{t},

with this last step using that $(k-i)/(n-i)\leq k/n$ for $i\geq 1$ if and only if $k\leq n$ . Using this and Lemma 3.4 gives

z(G;k)\leq\sum_{v}d(v)(k/n)^{d(v)}{n\choose k}.

Because $\delta\geq 3$ , we have $k\leq e^{-1/\delta}n$ , so by Observation 3.2 we have

z(G;k)\leq\delta n(k/n)^{\delta}{n\choose k}.

(6)

First consider the case $k\leq\sqrt{n}$ . By (6) and Lemma 3.5, to prove $z(G;k)\leq z(P_{n};k)$ , it suffices to have $\delta n(k/n)^{\delta}\leq k^{2}/2n$ , or equivalently $n/k\geq(2\delta)^{1/(\delta-2)}$ . Since $k\leq\sqrt{n}$ , it suffices to prove $n\geq(2\delta)^{2/(\delta-2)}$ , and this is true for $3\leq\delta\leq n$ and $n\geq 5$ . Thus we may assume $k\geq\sqrt{n}$ . In this case (6) and Lemma 3.5 imply $z(G;k)\leq z(P_{n};k)$ provided

\delta n(k/n)^{\delta}\leq\frac{1}{2},

and this will hold precisely when $k\leq(2\delta)^{-1/\delta}n^{1-1/\delta}$ . ∎

With Proposition 1.6 we can prove Corollary 1.7, which we restate below.

Corollary 1.7.

Let $G$ be an $n$ -vertex graph with minimum degree $\delta\geq\log_{2}(n)+2\log_{2}\log_{2}(n)$ . Then $z(G;k)\leq z(P_{n};k)$ for all $k$ .

Proof.

The result trivially holds for $k\geq n/2$ , so it suffices to prove the result for $k\leq n/2$ . By Proposition 1.6, it suffices to show

n/2\leq(2\delta)^{-1/\delta}n^{1-1/\delta},

or equivalently $n\leq 2^{\delta}(2\delta)^{-1}$ . And indeed, for $n\geq 9$ the minimum degree condition implies

2^{\delta}(2\delta)^{-1}\geq n\frac{(\log_{2}(n))^{2}}{2(\log_{2}(n)+2\log_{2}\log_{2}(n))}\geq n.

For $n\leq 8$ one can check that $\lceil\log_{2}(n)+2\log_{2}\log_{2}(n)\rceil\geq n-1$ , so our hypothesis on $\delta$ implies $G$ is complete and the result is immediate. In either case we conclude the result. ∎

4 Bounds on Threshold Probabilities

In this section we prove that for any $n$ -vertex graph $G$ , the threshold probability $p(G)$ is asymptotically at least that of $P_{n}$ , i.e. $p(G)=\Omega(n^{-1/2})$ . At a high level, our proof revolves around finding a graph $\tilde{G}$ which has minimum degree 2 and $p(\tilde{G})\approx p(G)$ . Because $\tilde{G}$ has minimum degree 2, Theorem 1.1 implies $p(G)\approx p(\tilde{G})=\Omega(n^{-1/2})$ . We begin with a preliminary result regarding graphs containing pendant paths.

We say that a path $v_{1}\cdots v_{k}$ in a graph $G$ is a pendant path⁶⁶6Most authors do not impose any conditions on the degree of $v_{k}$ in the definition of a pendant path, but this formulation will be more useful to us. provided $k\geq 2$ , $d_{G}(v_{1})=1$ , $d_{G}(v_{i})=2$ for $1<i<k$ , and $d_{G}(v_{k})>2$ . We refer to the vertex $v_{1}$ , the vertex of degree one, as the pendant vertex, and to $v_{k}$ , the vertex of degree at least 3, as the anchor vertex. Observe that the only tree that does not contain a pendant path is the path graph.

Lemma 4.1.

Let $G$ be an $n$ -vertex graph. If there exists a vertex $w\in V(G)$ that is the anchor of two distinct pendant paths in $G$ , then $p(G)=\Omega(n^{-1/2})$ .

Proof.

Let $w\in V(G)$ and assume that $w$ is the anchor of two distinct pendant paths in $G$ , i.e., there exist distinct pendant paths $u_{1}\cdots u_{k}w$ and $u_{k+1}\cdots u_{\ell}w$ in $G$ . Let

I=\{j\in\mathbb{Z}:1<j<k\text{ or }k+1<j<\ell\}

and for each $i\in I$ , let $A_{i}$ be the event that $u_{i},u_{i+1}\in B_{p}(G)$ . Let $A^{\prime}$ be the event that $B_{p}(G)\cap\{u_{1},u_{k},u_{k+1},u_{\ell}\}\neq\emptyset$ . Observe that if $B_{p}(G)\in\operatorname{ZFS}(G)$ , then $A^{\prime}$ or some $A_{i}$ event occurs. Thus,

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\Pr\Big{[}\bigcup_{i\in I}A_{i}\cup A^{\prime}\Big{]}\leq\Pr[A^{\prime}]+\sum_{i\in I}\Pr[A_{i}]\leq 4p+np^{2}.

Thus to have $\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]=\frac{1}{2}$ , we must have $np^{2}+4p\geq\frac{1}{2}$ , which implies $p=\Omega(n^{-1/2})$ . ∎

With this lemma, we see that when proving Theorem 1.4 we may assume each vertex is the anchor of at most one pendant path. The next lemma allows us to assume that none of these paths are too long (unless $G$ consists of a single path). In order to prove the next lemma, we recall various definitions and notation related to forcing chains which can be found, for example, in [BBF⁺10].

Let $G$ be a graph and $B\subseteq V(G)$ . Using $B$ as the initial set of blue vertices, apply the color change rule and record the forces. If a vertex $v$ forces $u$ we write $v\to u$ . The chronological list of forces $\mathcal{F}$ is the ordered list of forces, written in the order they were performed, that produces the final coloring of $B$ in $G$ . We shall sometimes use $\mathcal{F}$ to denote the set of forces that produces the final coloring of $B$ in $G$ . A forcing chain of $\mathcal{F}$ is a sequence of vertices $(v_{1},\ldots,v_{k})$ such that $v_{i}\to v_{i+1}$ for $1\leq i\leq k-1$ . A maximal forcing chain of $\mathcal{F}$ is a forcing chain that is not a proper subsequence of another forcing chain of $\mathcal{F}$ . The reversal of $B$ for $\mathcal{F}$ is the set of all vertices that do not perform a force, i.e., the set of all vertices that are the last element in a maximal forcing chain of $\mathcal{F}$ .

Lemma 4.2.

Let $G$ be an $n$ -vertex graph and let $\{v_{1},\ldots,v_{M}\}$ denote a set of vertices of degree 1 in $G$ . Let $\tilde{G}$ be the graph obtained from $G$ by adding a clique on $\{v_{1},\ldots,v_{M}\}$ . Then

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]\leq\Pr[B_{p}(\tilde{G})\in\operatorname{ZFS}(\tilde{G})]+pM.

Proof.

We begin by showing that if $B\in\operatorname{ZFS}(G)$ and $B\notin\operatorname{ZFS}(\tilde{G})$ , then $v_{i}\in B$ for some $i=1,\ldots,M$ . Let $B\subseteq V(G)$ and suppose that $v_{i}\notin B$ for all $i$ . Assume that $B\in\operatorname{ZFS}(G)$ and let $\mathcal{F}$ be the set of forces for $B$ in $G$ . Since each $v_{i}$ is a pendant vertex in $G$ and each $v_{i}\notin B$ , the set $\{v_{1},\ldots,v_{M}\}$ is contained in the reversal of $B$ for $\mathcal{F}$ . This, and the fact that the neighborhood of each vertex in $V(G)\setminus\{v_{1},\ldots,v_{M}\}$ is unchanged by adding a clique to $\{v_{1},\ldots,v_{M}\}$ , implies $\mathcal{F}$ is a set of forces for $B$ in $\tilde{G}$ . Thus, $B\in\operatorname{ZFS}(\tilde{G})$ and hence we have shown that if $B\in\operatorname{ZFS}(G)$ and $B\notin\operatorname{ZFS}(\tilde{G})$ , then $v_{i}\in B$ for some $i=1,\ldots,M$ .

Let $A_{i}$ be the event that $v_{i}\in B_{p}(G)$ . By the preceding argument and the union bound,

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)\text{ and }B_{p}(G)\notin\operatorname{ZFS}(\tilde{G})]\leq\Pr\left[\cup_{i=1}^{M}A_{i}\right]\leq pM.

We also have

	$\displaystyle\Pr[$	$\displaystyle B_{p}(G)\in\operatorname{ZFS}(G)\text{ and }B_{p}(G)\notin\operatorname{ZFS}(\tilde{G})]$
	$\displaystyle=$	$\displaystyle\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]-\Pr[B_{p}(G)\in\operatorname{ZFS}(G)\text{ and }B_{p}(G)\in\operatorname{ZFS}(\tilde{G})]$
	$\displaystyle\geq$	$\displaystyle\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]-\Pr[B_{p}(G)\in\operatorname{ZFS}(\tilde{G})].$

Combining both inequalities gives the result. ∎

The $2$ -core of a graph $G$ , denoted $C_{2}(G)$ , is obtained from $G$ by repeatedly removing all isolated vertices and all vertices of degree 1 from $G$ until no further removals are possible. See [Bic10] for basic facts about $2$ -cores. We say that $T$ is a pendant tree of a graph $G$ if $T$ is a maximal induced subgraph of $G$ such that $T$ is a tree, and if there exists a unique vertex $w\in V(T)$ contained in $C_{2}(G)$ . The vertex $w$ is called the anchor vertex of $T$ . It is known that a vertex $v$ is in $C_{2}(G)$ if and only if $v$ is contained in a cycle or a path between cycles. Thus, the $2$ -core of $G$ can be obtained by removing all non-anchor vertices of each pendant tree and all components of $G$ that are trees.

Let $G$ be a graph and $B\subseteq V(G)$ . We define $C_{2}(B,G)$ to be the set of vertices that are either contained in $B\cap C_{2}(G)$ or are anchor vertices of a pendant tree $T$ such that $B\cap V(T)$ is a zero forcing set of $T$ . When $G$ is clear from context we simply write $C_{2}(B)$ . These definitions are illustrated in Figure 5. The motivation for these definitions is found in Lemma 4.4.

Before proving our next lemma, we note the following observation about zero forcing on graphs with a cut vertex. Observation 4.3 follows from some of the concepts introduced in [Row12]. We write $G[S]$ to denote the induced subgraph of the graph $G$ on $S\subseteq V(G)$ .

Observation 4.3.

Let $G$ be a graph with cut vertex $w$ , and let $W_{1}\cup W_{2}\cup\{w\}$ be a partition of $V(G)$ such that $W_{1}$ and $W_{2}$ are the disjoint union of connected components of $G-w$ . Let $G_{i}=G\big{[}V(W_{i})\cup\{w\}\big{]}$ for $i=1,2$ . Then $B\cap V(G_{i})\in\operatorname{ZFS}(G_{i})$ for some index $i$ , and $B\cap V(G_{i})\cup\{w\}$ is a zero forcing set of $G_{i}$ for each $i=1,2$ .

Lemma 4.4.

Let $G$ be a graph and $B\subseteq V(G)$ . If $B$ is a zero forcing set of $G$ , then $C_{2}(B)$ is a zero forcing set of $C_{2}(G)$ .

Proof.

Assume for contradiction that there exists a pair $(B,G)$ such that $B$ is a zero forcing set of $G$ and $C_{2}(B)$ is not a zero forcing set of $C_{2}(G)$ . Moreover, choose a minimal counterexample $(B,G)$ such that $G$ has as few vertices as possible.

We begin with a few observations to simplify the proof. The 2-core of $G$ is the disjoint union of the 2-cores of each connected component of $G$ . If $C_{2}(G)$ is the null graph, then it is vacuously true that $C_{2}(B)$ is a zero forcing set of $C_{2}(G)$ . If $C_{2}(G)=G$ , then $C_{2}(B)=B$ and hence $C_{2}(B)$ is a zero forcing set of $C_{2}(G)$ . We may therefore assume that $G$ is connected and that $G$ contains a pendant tree.

Let $T$ be a pendant tree of $G$ with anchor vertex $w$ , and let $G_{T}$ be the induced subgraph of $G$ on $(V(G)\setminus V(T))\cup\{w\}$ . Let

B_{T}=\begin{cases}B\cap V(G_{T})&\text{if }B\cap V(T)\notin\operatorname{ZFS}(T)\\ (B\cap V(G_{T}))\cup\{w\}&\text{if }B\cap V(T)\in\operatorname{ZFS}(T).\end{cases}

Since $w$ is a cut vertex, Observation 4.3 implies that $B_{T}$ is a zero forcing set of $G_{T}$ . By our assumption of $(B,G)$ being a vertex minimal counterexample, we have that $C_{2}(B_{T},G_{T})$ is a zero forcing set of $C_{2}(G_{T})$ since $G_{T}$ has strictly fewer vertices than $G$ . It is not difficult to check that $C_{2}(G_{T})=C_{2}(G)$ and $C_{2}(B_{T},G_{T})=C_{2}(B,G)$ , so $C_{2}(B,G)$ is a zero forcing set of $C_{2}(G)$ . This gives a contradiction, proving the result. ∎

We can now prove the main result of this section, which we restate below.

Theorem 1.4.

If $G$ is an $n$ -vertex graph, then

p(G)=\Omega(p(P_{n}))=\Omega(n^{-1/2}).

Proof.

Observe that if $H$ is a connected component of $G$ , then $p(G)\geq p(H)$ . Also, by Lemma 4.1, if $G$ is a tree that is not a path, or if $G$ has a pendant tree that is not a pendant path, then $p(G)=\Omega(n^{-1/2})$ . We may therefore assume that $G$ is connected, $G$ contains a cycle, and every pendant tree of $G$ is a pendant path. Note that the definition of pendant trees implies every vertex $v$ is the anchor of at most one pendant path in $G$ , and that every anchor vertex is contained in $C_{2}(G)$ . Let $p=cn^{-1/2}$ , where $c<1$ is a positive constant which we specify later.

Let $\{P_{1},\ldots,P_{M}\}$ be the set of all pendant paths in $G$ on at least $100n^{1/2}+1$ vertices, and let $v_{i}\in P_{i}$ denote the vertex of $P_{i}$ of degree 1. Let $\tilde{G}$ be the graph obtained from $G$ by adding a clique on $\{v_{1},\ldots,v_{M}\}$ . Observe that $M(100n^{1/2}+1)\leq n$ , and hence $M<n^{1/2}/100$ . Thus by Lemma 4.2,

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]<\Pr[B_{p}(\tilde{G})\in\operatorname{ZFS}(\tilde{G})]+.01.

Observe that $C_{2}(\tilde{G})$ is nonempty since $G$ contains a cycle, and by Lemma 4.4,

\Pr[B_{p}(\tilde{G})\in\operatorname{ZFS}(\tilde{G})]\leq\Pr[C_{2}(B_{p}(\tilde{G}))\in\operatorname{ZFS}(C_{2}(\tilde{G}))].

Thus it suffices to prove $\Pr[C_{2}(B_{p}(\tilde{G}))\in\operatorname{ZFS}(C_{2}(\tilde{G}))]<0.49$ for $n$ sufficiently large.

For $v\in V(C_{2}(\tilde{G}))$ , let $A_{v}$ denote the event that $v\in C_{2}(B_{p}(\tilde{G}))$ . We claim that

\Pr[A_{v}]\leq 2p+(100n^{1/2})p^{2}=(2c+100c^{2})n^{-1/2}:=q.

(7)

Indeed, $\Pr[A_{v}]=p$ if $v$ is not the anchor of some pendant path. If $v$ is the anchor of the pendant path $P$ , then for $A_{v}$ to occur, either an endpoint of $P$ or two consecutive vertices of $P$ must be in $B_{p}(\tilde{G})$ , and a union bound gives the result since $P$ is assumed to have length at most $100n^{1/2}+1$ .

Because the $A_{v}$ events are independent of each other, our bound above implies that

\Pr[C_{2}(B_{p}(\tilde{G}))\in\operatorname{ZFS}(C_{2}(\tilde{G}))]\leq\Pr[B_{q}(\tilde{G})\in\operatorname{ZFS}(C_{2}(\tilde{G})).

Since $C_{2}(\tilde{G})$ has at most $n$ vertices and minimum degree at least 2, Theorem 1.1 implies

\Pr[B_{q}(\tilde{G})\in\operatorname{ZFS}(C_{2}(\tilde{G}))]\leq 2nq^{2}.

Taking $c=1/17$ and recalling the definition of $q$ in (7) gives the desired result. ∎

5 Bounds for Trees

In this section we prove $\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})]$ whenever $T$ is an $n$ -vertex tree with $n$ sufficiently large. We will break our proof into two cases, namely when $p=\Omega(n^{-1})$ and $p=O(n^{-1})$ . The intuition for this choice is that when $p\ll n^{-1},$ the probability that $B_{p}(P_{n})$ is zero forcing is roughly the probability of choosing an endpoint, while for $p\gg n^{-1}$ it is roughly the probability of choosing two consecutive vertices. As such, we will need two different arguments for these two regimes.

5.1 Large $p$

The following provides a concrete statement agreeing with the intuition outlined above.

Lemma 5.1.

Let $v_{1},\ldots,v_{n}$ be vertices of a graph $G$ . If $\frac{8}{n}<p<1$ and $n\geq 16$ , then

\Pr[v_{1}\in B_{p}(G)\textrm{ or }v_{n}\in B_{p}(G)]<\Pr[v_{i},v_{i+1}\in B_{p}(G)\textrm{ for some }i].

Proof.

Define

p_{e}:=\Pr[v_{1}\in B_{p}(G)\textrm{ or }v_{n}\in B_{p}(G)]=1-(1-p)^{2},

p_{m}:=\Pr[v_{i},v_{i+1}\in B_{p}(G)\textrm{ for some }i]\geq 1-(1-p^{2})^{\lfloor\frac{n-1}{2}\rfloor},

where this last inequality holds because $p_{m}$ is strictly more than the probability of having at least one of the pairs $(v_{i},v_{i+1})$ with $i$ odd in $B_{p}(G)$ ; see the proof of Proposition 2.3 for a more formal argument.

We will show that when $n\geq\frac{4}{p-p^{2}}$ , we have $p_{m}>p_{e}$ . Indeed, $n\geq\frac{4}{p-p^{2}}$ is equivalent to $\frac{-2p}{(1-p)}\geq\frac{-p^{2}n}{2}$ . By looking at the Taylor series, it is easy to show $\frac{x}{1+x}<\ln(1+x)<x$ for $|x|<1$ , so we have

\frac{-2p}{(1-p)}<2\ln(1-p)\ \text{ and }\ \ln(1-p^{2})\cdot\left\lfloor\frac{n-1}{2}\right\rfloor<-p^{2}\left\lfloor\frac{n-1}{2}\right\rfloor<\frac{-p^{2}n}{2}.

Thus for this range of $n$ we have $2\ln(1-p)>\left\lfloor\frac{n-1}{2}\right\rfloor\ln(1-p^{2})$ , or equivalently,

1-(1-p)^{2}<1-(1-p^{2})^{\left\lfloor\frac{n-1}{2}\right\rfloor}.

Thus $p_{m}>p_{e}$ when $n\geq\frac{4}{p-p^{2}}$ . This bound on $n$ holds for all $p\in(\frac{8}{n},1-\frac{8}{n})$ , and for $p\in[1-\frac{8}{n},1)$ , this same bound holds for $n\geq 16$ , completing the proof. ∎

Analogous to Proposition 4.1, we can show that graphs with a vertex at the end of two short pendant paths are harder to zero force than paths.

Lemma 5.2.

Let $G$ be an $n$ -vertex graph that has a vertex $w$ which is the endpoint of two pendant paths $u_{1}\cdots u_{s}w$ and $v_{1}\cdots v_{t}w$ . If $p\geq 8/(n-s-t)$ and $n-s-t\geq 14$ , then

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]<\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})].

Proof.

Let $w_{1},\ldots,w_{r}$ be an arbitrary ordering of $V(G)\setminus\{u_{1},\ldots,u_{s},v_{1},\ldots,v_{t}\}$ . Relabel the vertices of $P_{n}$ so that its vertices along the path are $u_{1}\cdots u_{s}w_{1}\cdots w_{r}v_{t}\cdots v_{1}$ . Because $V(G)=V(P_{n})$ , we can couple our random variables so that $B_{p}:=B_{p}(G)=B_{p}(P_{n})$ . Let $F=B_{p}\cap\{u_{1},\ldots,u_{s-1},v_{1},\ldots,v_{t-1}\}$ . It suffices to show for all $S\subseteq\{u_{1},\ldots,u_{s-1},v_{1},\ldots,v_{t-1}\}$ that

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)|F=S]\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})|F=S],

with strict inequality for at least one such set. If $S$ contains two consecutive vertices $u_{i}$ and $u_{i+1}$ , two consecutive vertices $v_{j}$ and $v_{j+1}$ , or $u_{1}$ or $v_{1}$ , then $B_{p}\in\operatorname{ZFS}(P_{n})$ so the result holds trivially. Thus from now on we can assume this is not the case.

With this assumption, the vertex $u_{s}$ in $G$ can only be colored blue by $B_{p}$ if at least one of $u_{s}$ or $v_{t}$ is in $B_{p}$ (this is because $u_{s}$ is adjacent to $u_{s-1}$ , which does not enact any forces by assumption on $S$ , and to $w$ , which can only enact a force if at least one of $u_{s},v_{t}$ are colored blue at some point). On the other hand, $B_{p}$ will be a zero forcing set for $P_{n}$ provided $B_{p}$ contains two consecutive vertices from $\{u_{s},w_{1},\cdots,w_{r},v_{t}\}$ .

By applying Lemma 5.1 to the vertex set $\{u_{s},w_{1},\ldots,w_{r},v_{t}\}$ , we see that if $p>\frac{8}{n-s-t+2}$ and $n-s-t+2\geq 16$ , then

\Pr[B_{p}\text{ contains $u_{s}$ or $v_{t}$}]<\Pr[B_{p}\text{ contains a consecutive pair from }\{u_{s},w_{1},\cdots,w_{r},v_{t}\}].

As these two events are independent of the random set $F$ , we conclude that for $p\geq 8/(n-s-t)>8/(n-s-t+2)$ and $n-s-t+2\geq 16$ ,

\Pr[B_{p}(G)\in\operatorname{ZFS}(G)|F=S]<\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})|F=S],

and from this we conclude the result. ∎

With this we can solve Theorem 1.3 when $p=\Omega(n^{-1})$ .

Proposition 5.3.

If $T\neq P_{n}$ is an $n$ -vertex tree with $n\geq 42$ , and if $\frac{24}{n}<p<1$ , then

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]<\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})].

Proof.

Let $u,v$ be any two leaves of $T$ which are at a shortest distance from each other. Observe that the path between $u,v$ consists of two pendant paths, say $uu_{2},\cdots u_{s}w$ and $vv_{2},\cdots v_{t}w$ . Because $T$ is not a path, there either exists exactly one leaf $\ell\neq u,v$ , or at least two leaves $i,j\neq u,v$ .

Suppose for contradiction that $s+t>\frac{2n}{3}$ . If $T$ has exactly three leaves, then

d(\ell,u)=d(\ell,w)+s<n/3+s,

where this inequality used that none of the internal vertices along the path from $\ell$ to $w$ use any of the vertices along the path from $u$ to $v$ , of which there are more than $2n/3+1$ vertices. By a symmetric argument we have $d(\ell,v)<n/3+t$ . In particular, we must have

d(\ell,u)+d(\ell,v)<2n/3+s+t<2(s+t)=2d(u,v),

and hence at least one of $d(\ell,u),d(\ell,v)$ is smaller than $d(u,v)$ , a contradiction to our choice of $u,v$ . Similarly if $T$ has at least four leaves, then $d(i,j)<\frac{n}{3}$ , which again gives a contradiction. Thus we can assume $s+t\leq 2n/3$ . With this, our hypothesis implies $p\geq\frac{8}{n-s-t}$ and $n-s-t+2\geq 16$ , so we can apply Lemma 5.2 to give the desired result. ∎

5.2 Small $p$

We will prove our result for small $p$ by upper bounding $z(T;k)$ , which we recall is the number of zero forcing sets of $T$ of size $k$ .

Lemma 5.4.

If $T\neq P_{n}$ is an $n$ -vertex tree, then

z(T;k)\leq\frac{13k^{4}}{n^{2}}{n\choose k}.

Proof.

Let $\Delta$ denote the maximum degree of $T$ and $\ell$ the number of leaves of $T$ . Observe that the zero forcing number of a graph is always at least the minimum number of paths needed to cover the vertices of the graph. In particular, every zero forcing set for the tree $T$ has size at least $\ell/2$ . It is also known (see for example [Obo21]) that every zero forcing set for a tree $T$ has size at least $\Delta-1$ . Thus for $k<\max\{\Delta-1,\ell/2\}$ , we have $z(T;k)=0$ and the bound trivially holds. From now on we assume $\Delta-1,\ell/2\leq k$ . The bound is also trivial when $k=n$ , so we may assume $k<n$ . Lastly, we may also assume $\Delta\geq 3$ since $T$ is not a path.

We first count the number of zero forcing sets $S$ of size $k$ which have two pairs of vertices $u,v$ and $x,y$ with $u\sim v,\ x\sim y$ and $\{u,v\}\cap\{x,y\}=\emptyset$ . In this case the number of sets $S$ is at most

(n-1)^{2}{n-4\choose k-4},

since one can choose each pair (which is just an edge in $T$ ) in at most $n-1$ ways.

We next count the number of zero forcing sets $S$ of size $k$ which contain three vertices $u,v,w$ with $u\sim v\sim w$ . The number of such $S$ is at most

(n-1)(2\Delta-2){n-3\choose k-3},

since one can first choose two adjacent vertices in $n-1$ ways, then a third vertex which is adjacent to at least one of these in at most $2\Delta-2$ ways, and then the remaining vertices in ${n-3\choose k-3}$ ways.

We next count the number of $S$ that contain no two adjacent vertices. Because $k<n$ and $S$ is a zero forcing set, at least one vertex of $S$ must be able to force. Because $S$ contains no adjacent vertices, this is only possible if $S$ contains a leaf. Choose such a leaf $u_{1}$ to include in $S$ , which can be done in $\ell$ ways. Let $u_{1}u_{2}\cdots u_{s}$ be the unique path in $T$ with $\deg(u_{i})=2$ for $1<i<s$ and $\deg(u_{s})\neq 2$ .

Claim 5.5.

The set $S$ either contains a leaf $v\neq u_{1}$ , or a neighbor of $u_{s}$ other than $u_{s-1}$ .

Proof.

Assume this were not the case. Because $S$ contains no two adjacent vertices, no additional leaves, and no other neighbor of $u_{s}$ , it is not difficult to see that the only vertices that will be colored blue by $S$ are $S\cup\{u_{2},\ldots,u_{s}\}$ . Because $S$ is a zero forcing set, we must have $V(T)=S\cup\{u_{2},\ldots,u_{s}\}$ . However, by assumption the only leaves that could be in $S\cup\{u_{2},\ldots,u_{s}\}$ are $u_{1}$ and $u_{s}$ , but $T\neq P_{n}$ contains at least three leaves, so $V(T)\neq S\cup\{u_{2},\ldots,u_{s}\}$ , giving the desired contradiction. ∎

In total then, we see that the number of choices for such a set $S$ is at most

\ell(\ell+\Delta-1){n-2\choose k-2},

where the terms in the expression above count the number of choices for $u_{1}$ , followed by the number of choices for some additional leaf or neighbor of $u_{s}$ , followed by the number of arbitrary sets of $k-2$ vertices.

It remains to count $S$ that have exactly one pair of adjacent vertices. One can first choose the adjacent pair $u_{1},v_{1}\in S$ in at most $n-1$ ways. If $\deg(u_{1})=2$ , then let $u_{1}\cdots u_{s}$ be the unique path from $u_{1}$ with $u_{2}$ the neighbor of $u_{1}$ not equal to $v_{1}$ , and with $\deg(u_{i})=2$ for all $i<s$ and $\deg(u_{s})\neq 2$ . If $\deg(u_{1})\neq 2$ , then we simply consider the 1 vertex path $u_{1}$ . Analogously define the path $v_{1}\cdots v_{t}$ . As in the previous case, because $S$ contains no other pair of adjacent vertices, it must contain at least one leaf or one neighbor of either $u_{s}$ or $v_{t}$ that is not $u_{s-1}$ or $v_{t-1}$ . In total then the number of choices for such an $S$ is at most

(n-1)(\ell+2\Delta-2){n-3\choose k-3}.

In total, $z(T;k)$ is at most

	$\displaystyle(n-1)^{2}{n-4\choose k-4}+(n-1)(2\Delta-2){n-3\choose k-3}+\ell(\ell+\Delta-1){n-2\choose k-2}+(n-1)(\ell+2\Delta-2){n-3\choose k-3}$
	$\displaystyle\leq n^{2}\cdot\frac{k^{4}}{n^{4}}{n\choose k}+n(2\Delta-2)\cdot\frac{k^{3}}{n^{3}}{n\choose k}+\ell(\ell+\Delta-1)\cdot\frac{k^{2}}{n^{2}}{n\choose k}+n(\ell+2\Delta-2)\cdot\frac{k^{3}}{n^{3}}{n\choose k},$

where this last inequality used $n-1\leq n$ and that ${n-t\choose k-t}\leq(k/n)^{t}{n\choose k}$ for all integers $t\geq 0$ . Using our assumptions $\Delta-1\leq k$ and $\ell\leq 2k$ , we find that the above expression is at most $(1+2+6+4)\frac{k^{4}}{n^{2}}{n\choose k}$ as desired. ∎

With this we can prove the following.

Proposition 5.6.

For every $C>0$ , there exists an integer $n_{0}$ such that for all $n\geq n_{0}$ , if $T\neq P_{n}$ is an $n$ -vertex tree and $0<p\leq\frac{C}{n}$ , then

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]<\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})].

Proof.

By the previous lemma and the trivial bound ${n\choose k}\leq n^{k}/k!$ , we have

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]\leq\sum_{k}z(T;k)p^{k}\leq\sum_{k}\frac{13k^{4}n^{k-2}}{k!}p^{k}\leq p\cdot 13Cn^{-1}\sum_{k}\frac{k^{4}C^{k-2}}{k!}.

The above sum is convergent, so for $n$ sufficiently large we find

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]\leq\frac{1}{2}p\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})],

where this latter inequality is strict provided $p>0$ . ∎

With Propositions 5.3 and 5.6 we can prove Theorem 1.3, which we restate below.

Theorem 1.3.

If $T$ is an $n$ -vertex tree with $n$ sufficiently large, then for all $0\leq p\leq 1$ ,

\Pr[B_{p}(T)\in\operatorname{ZFS}(T)]\leq\Pr[B_{p}(P_{n})\in\operatorname{ZFS}(P_{n})],

with equality holding if and only if either $p\in\{0,1\}$ or $T=P_{n}$ .

Proof.

The equality of the result trivially holds for either $p\in\{0,1\}$ or $T=P_{n}$ . If $T\neq P_{n}$ with $n$ sufficiently large, by Proposition 5.3, the result holds for $24/n<p<1$ , and by Proposition 5.6 the result holds for $0<p\leq 24/n$ . ∎

6 Concluding Remarks

We have many open problems regarding the threshold probability $p(G)$ , which we recall is the unique $p\in[0,1]$ such that $\Pr[B_{p}(G)\in\operatorname{ZFS}(G)]=\frac{1}{2}$ . For example, we conjecture the following refinement of Theorem 1.4.

Conjecture 6.1.

If $G$ is an $n$ -vertex graph which contains a clique of size $k$ , then

p(G)=\Omega(\sqrt{k/n}).

This conjecture can be viewed as a probabilistic analog to the classical result that $Z(G)\geq k$ if $G$ has a clique of size $k$ , which was proved by Butler and Young [BY13]. The motivation for the bound $\Omega(\sqrt{k/n})$ comes from considering a graph $G$ which consists of a clique on $k$ vertices, with each of these vertices attached to a path of length roughly $n/k$ . For this graph, a given vertex of the clique will be forced by the path it is connected to with probability roughly $1-e^{-p^{2}n/k}$ , so if $p$ is much smaller than $\sqrt{k/n}$ , then almost none of the clique vertices in $G$ will be colored blue. Thus $p(G)=\Omega(\sqrt{k/n})$ in this case⁷⁷7In fact, a sharper analysis shows that $p(G)=\Omega(\sqrt{k\log(k)/n})$ for $k$ not too large in terms of $n$ . We suspect that Conjecture 6.1 can be strengthened to include this $\log(k)$ term, but for ease of presentation we have written the conjecture as is..

In Section 2, we determined the order of magnitude of $p(G)$ for many natural families of graphs. One case where we do not know how to do this is for the $n$ -dimensional hypercube $Q_{n}$ .

Problem 6.2.

Does there exist a constant $c$ such that $p(Q_{n})\sim c$ ? If so, what is this constant?

Because $Z(Q_{n})=2^{n-1}$ , we must have $c\geq.5$ if it exists, but beyond this we know nothing about $c$ . The empirical plot in Figure 2 of the probability that $B_{p}(Q_{8})$ is zero forcing suggests that $c$ might be at least .58. Another family of graphs which we do not understand are grid graphs.

Problem 6.3.

Determine the order of magnitude of $p(P_{m}\square P_{n})$ , where $P_{m}\square P_{n}$ denotes the $m\times n$ grid graph.

Assuming $2\leq m\leq n$ , we can apply Theorem 3.3 with $d=4$ and $N\approx n^{1/3}$ to show $p(P_{m}\square P_{n})=\Omega(\min\{n^{-1/3},(mn)^{-1/4}\})$ . The best general upper bound we have is $p(P_{m}\square P_{n})=O(n^{-1/2m})$ , since at this point it is fairly likely that $B_{p}(P_{m}\square P_{n})$ contains two consecutive $P_{m}$ paths, which forces the entire graph. For small $m$ we suspect that our upper bound is closer to the truth than our lower bound, but for large $m$ the situation is unclear.

Lastly, one could consider randomized versions of variants of the classical zero forcing number. For example, under skew zero forcing (which was originally introduced in [ABD⁺10]), one can easily generalize Theorem 1.1 to give an upper bound of roughly $\delta np^{\delta-1}$ , generalizing the classical result $Z_{-}(G)\geq\delta-1$ if $G$ has minimum degree $\delta$ . It would also be interesting to consider probabilistic zero forcing with a random set of vertices initially colored blue.

Acknowledgements

The authors would like to express their sincere gratitude to the organizers of the Mathematics Research Community on Finding Needles in Haystacks: Approaches to Inverse Problems Using Combinatorics and Linear Algebra, and the AMS for funding the program through NSF grant 1916439.

References

[ABD⁺10] Mary Allison, Elizabeth Bodine, Luz Maria DeAlba, Joyati Debnath, Laura DeLoss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, and Amy Wangsness Wehe. Minimum rank of skew-symmetric matrices described by a graph. Linear Algebra Appl., 432(10):2457–2472, 2010. IMA-ISU research group on minimum rank.
[BBE⁺19] Kirk Boyer, Boris Brimkov, Sean English, Daniela Ferrero, Ariel Keller, Rachel Kirsch, Michael Phillips, and Carolyn Reinhart. The zero forcing polynomial of a graph. Discret. Appl. Math., 258:35–48, 2019.
[BBF⁺10] Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, P. van den Driessche, and Hein van der Holst. Zero forcing parameters and minimum rank problems. Linear Algebra Appl., 433(2):401–411, 2010.
[BG07] Daniel Burgarth and Vittorio Giovannetti. Full control by locally induced relaxation. Phys. Rev. Lett., 99:100501, Sep 2007.
[Bic10] Allan Bickle. The k-Cores of a Graph. PhD thesis, Western Michigan University, Kalamazoo, Michigan, 2010.
[BY13] Steve Butler and Michael Young. Throttling zero forcing propagation speed on graphs. Australas. J. Combin., 57:65–71, 2013.
[CCG⁺20] Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, Kevin Liu, Issac Odegard, and Michael Ross. Using Markov chains to determine expected propagation time for probabilistic zero forcing. Electron. J. Linear Algebra, 36:318–333, 2020.
[EMPa21] Sean English, Calum MacRury, and PawełPrał at. Probabilistic zero forcing on random graphs. European J. Combin., 91:Paper No. 103207, 22, 2021.
[FK16] Alan Frieze and Michał Karoński. Introduction to random graphs. Cambridge University Press, Cambridge, 2016.
[GH18] Jesse Geneson and Leslie Hogben. Propagation time for probabilistic zero forcing, 2018.
[Gro08] AIM Minimum Rank-Special Graphs Work Group. Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl., 428(7):1628–1648, 2008.
[HLS22] Leslie Hogben, Jephian C-H Lin, and Bryan L Shader. Inverse Problems and Zero Forcing for Graphs, volume 270. American Mathematical Society, 2022.
[HS20] David Hu and Alec Sun. Probabilistic zero forcing on grid, regular, and hypercube graphs, 2020.
[KY13] Cong X. Kang and Eunjeong Yi. Probabilistic zero forcing in graphs. Bull. Inst. Combin. Appl., 67:9–16, 2013.
[LY13] Yuan-Chuan Li and Cheh-Chih Yeh. Some equivalent forms of Bernoulli’s inequality: a survey. Springer P. Math. Stat., 4(07):1070, 2013.
[NS21] Shyam Narayanan and Alec Sun. Bounds on expected propagation time of probabilistic zero forcing. European J. Combin., 98:Paper No. 103405, 16, 2021.
[Obo21] Mohammad Reza Oboudi. On the zero forcing number of trees. Iran. J. Sci. Technol. Trans. A Sci., 45(3):1065–1070, 2021.
[Row12] Darren D. Row. A technique for computing the zero forcing number of a graph with a cut-vertex. Linear Algebra and its Applications, 436(12):4423–4432, 2012.

Zero Forcing with Random Sets

Abstract

1 Introduction

1.1 Main Results

Theorem 1.1.

Conjecture 1.2.

Theorem 1.3.

Theorem 1.4.

Conjecture 1.5 ([BBE+19]).

Proposition 1.6.

Corollary 1.7.

1.2 Organization and Notation

2 Threshold Probabilities for Families of Graphs

Proposition 2.1.

Proof.

Observation 2.2.

Proposition 2.3.

Proof.

Proposition 2.4.

Proof.

Proposition 2.5.

Proof.

Remark 2.6.

3 Bounds Using Degrees

Lemma 3.1.

Proof.

Observation 3.2.

Theorem 1.1.

Proof.

Theorem 3.3.

Proof.

Lemma 3.4.

Proof.

Lemma 3.5.

Proof.

Proposition 1.6.

Proof.

Corollary 1.7.

Proof.

4 Bounds on Threshold Probabilities

Lemma 4.1.

Proof.

Lemma 4.2.

Proof.

Observation 4.3.

Lemma 4.4.

Proof.

Theorem 1.4.

Proof.

5 Bounds for Trees

5.1 Large pp

Lemma 5.1.

Proof.

Lemma 5.2.

Proof.

Proposition 5.3.

Proof.

5.2 Small pp

Lemma 5.4.

Proof.

Claim 5.5.

Proof.

Proposition 5.6.

Proof.

Theorem 1.3.

Proof.

6 Concluding Remarks

Conjecture 6.1.

Problem 6.2.

Problem 6.3.

Acknowledgements

References

Conjecture 1.5 ([BBE⁺19]).

5.1 Large $p$

5.2 Small $p$