On $K_{2,t}$-Bootstrap Percolation

Abstract

Given two graphs G and H, it is said that G percolates in H-bootstrap process if one could join all the nonadjacent pairs of vertices of G in some order such that a new copy of H is created at each step. Balogh, Bollobás and Morris in 2012 investigated the threshold of H-bootstrap percolation in the Erdős–Rényi model for the complete graph H and proposed the similar problem for $H=K_{s,t}$, the complete bipartite graph. In this paper, we provide lower and upper bounds on the threshold of $K_{2, t}$-bootstrap percolation. In addition, a threshold function is derived for $K_{2,4}$-bootstrap percolation.

1 Introduction

Bootstrap percolation on graphs has been extensively investigated in several diverse fields such as combinatorics, probability theory, statistical physics and social sciences. Many different models of bootstrap percolation have been defined and studied in the literature including the r-neighbor bootstrap percolation and the majority bootstrap percolation. In this paper, we deal with the H-bootstrap percolation whose study was initiated in 2012 by Balogh, Bollobás, and Morris [1]. Roughly speaking, for two given graphs G and H, we say that G percolates in the H-bootstrap process if it is possible to join all the nonadjacent pairs of vertices of G in some order such that a new copy of H is created at each step. The concept is closely related to the notion of ‘weak saturation’ that was introduced in 1968 by Bollobás [2]. The H-bootstrap percolation has been studied by many researches [3,4,5,6].

Throughout this paper, all graphs are assumed to be finite, undirected, and without loops or multiple edges. For a graph G, we denote the vertex set and the edge set of G by V(G) and E(G), respectively. For given graphs G and H, we associate the graph $\widehat{G}_H$ obtained from the following process: Let $G_0=G$ and for $i=1, 2, \ldots$ define $G_i$ as the graph with vertex set V(G) and edge set $E(G_{i-1})\cup E_i$, where $E_i$ is the set of all edges in the complement of $G_{i-1}$ such that adding each of them to $G_{i-1}$ creates a new copy of H. Define $\widehat{G}_H$ as the graph with vertex set V(G) and edge set ${\bigcup }_{i\geqslant 0}E(G_i)$. We say that G percolates in the H -bootstrap process if $\widehat{G}_H$ is a complete graph.

For two positive real valued functions f and g defined on positive integers, we write $f=\mathrm {O}(g)$ (respectively, $f=\Omega (g)$) if there exists a positive constant c such that $f(n)\leqslant cg(n)$ (respectively, $f(n)\geqslant cg(n)$) for any n large enough. Further, we write $f=\Theta (g)$ if $f=\mathrm {O}(g)$ and $f=\Omega (g)$. Finally, we write $f\ll g$ (respectively, $f\gg g$) if $\lim _{n\rightarrow \infty }\tfrac{f(n)}{g(n)}$ equals 0 (respectively, $\infty$). For a positive integer n and a function p defined on positive integers with values in [0, 1], we denote by the probability space of all graphs on a fixed vertex set of size n where every two distinct vertices are adjacent independently with probability p(n). In the literature, is known as the Erdős–Rényi model for random graphs. A function is a threshold for a sequence $\mathscr {E}_n$ of events in if

We say that $\mathscr {E}_n$ holds with high probability if . As a consequence of Theorem 4 in [7], we know for any graph H that

is a threshold function for H-bootstrap percolation.

Denote the complete graph on r vertices and the complete bipartite graph with part sizes s and t by $K_r$ and $K_{s, t}$, respectively. Balogh, Bollobás and Morris in [1] studied H-bootstrap percolation on . They proved that, for any fixed integer $r\geqslant 4$ and any sufficiently large n,

$$\begin{aligned} \frac{n^{-\lambda }}{2\!\text { e}\!\log n}\leqslant p_c(n; K_r)\leqslant n^{-\lambda }\log n, \end{aligned}$$

where $\lambda =\tfrac{2r-4}{r^2-r-4}$ and $\log$ is the logarithm function with base the Neperian number e. One of the open problems posed in [1] is the determination of $p_c(n; K_{s, t})$. We know from Proposition 26 of [1] that

$$\begin{aligned} p_c(n; K_{1, t})=\Theta \left( n^{-\frac{t}{t-1}}\right) \end{aligned}$$

for any $t\geqslant 2$ and also that

$$\begin{aligned} p_c(n; K_{2, 2})=p_c(n; K_{2, 3})=\frac{\log n}{n}+\Theta \left( \frac{1}{n}\right) \end{aligned}$$

by Proposition 24 of [1]. In this paper, we examine $p_c(n; K_{2, t})$ for $t\geqslant 4$. We present lower and upper bounds on $p_c(n; K_{2, t})$, and moreover, we prove that $p_c(n; K_{2, 4})=\Theta (n^{-10/13})$. After our work, in Theorem 1.1 of [8], Bayraktar and Chakraborty proved that, for every fixed integers $s\geqslant 4$ and $t\geqslant 3$ satisfying $t\leqslant s\leqslant t^2-3t+4$ and any sufficiently large n,

$$\begin{aligned} c_1\frac{n^{-\mu }}{\log n}\leqslant p_c(n; K_{s, t})\leqslant c_2\left( \frac{\log n}{\log \log n}\right) ^{2\mu }n^{-\mu }, \end{aligned}$$

where $\mu =\tfrac{s+t-2}{st-2}$ and $c_1, c_2$ do not depend on n. We also refer to [9] for some related results.

Let us fix some notation and terminology. For a graph G and a subset S of V(G), we denote the induced subgraph of G on S by G[S]. For a vertex v of G, we set $N_G(v)=\{x\in V(G) \, | \, v \text { is adjacent to } x\}$ and $N_G[v]=N_G(v)\cup \{v\}$. The degree of a vertex v of G, denoted by $\mathrm{deg} _G(v)$, is defined as $|N_G(v)|$. A graph G is a complete split graph if one can partition V(G) into an independent set I and a clique C such that each vertex in I is adjacent to each vertex in C.

2 The Upper Bound

In this section, we assume that t is an integer at least 4 and we reserve $\widehat{G}$ for the graph obtained from a graph G in $K_{2,t}$-bootstrap process. We will obtain an upper bound on $p_c(n; K_{2, t})$. More precisely, we will establish that

$$\begin{aligned} p_c(n; K_{2,t})=\mathrm {O}\left( n^{-\frac{1}{\eta (t)}}\right) , \end{aligned}$$

where

$$\begin{aligned} \eta (t)=\left\{ \begin{array}{ll} {\frac{6t^2-14t+12}{3t^2-4t+8}} &{} \text { if} \, t \, \text { is even,}\\ \\ {\frac{2t^2-4t+2}{t^2-t+2}} &{} \text { if}\, t \, \text {is odd.} \end{array}\right. \end{aligned}$$

Recall that the density of a graph G is defined as

$$\begin{aligned}d(G)=\frac{|E(G)|}{|V(G)|},\end{aligned}$$

and the maximum subgraph density of G as

$$\begin{aligned}m(G)=\max \Big \{d(H) \, \Big | \, H \text{ is} \text{ a} \text{ subgraph} \text{ of } G\Big \}.\end{aligned}$$

In our proofs, we frequently use the following theorem which also appears as Theorem 5.3 in [10].

Theorem 2.1

(Bollobás [11]) Let H be a fixed graph with at least one edge. Then $n^{-1/m(H)}$ is a threshold for the property that contains a copy of H as a subgraph.

The following lemma is easily obtained from the definition of $K_{2, t}$-bootstrap process.

Lemma 2.2

Let G be a graph and let $x,y \in V(G)$ with $|N_G(x) \cap N_G(y)| \geqslant t-1$. Then $N_{\widehat{G}}(x){\setminus }\{y\}=N_{\widehat{G}}(y){\setminus }\{x\}$.

Lemma 2.3

Let G be a connected graph containing a copy of $K_{t-1, t-1}$ as a subgraph. Then $\widehat{G}$ is either a complete graph, a complete bipartite graph or a complete split graph with the clique part of size $t-1$.

Proof

We consider the relation $\approx$ on $V(\widehat{G})$ as follows:

$$\begin{aligned} x\approx y \,\,\text {if}\,\, N_{\widehat{G}}(x){\setminus }\{y\}=N_{\widehat{G}}(y){\setminus }\{x\}. \end{aligned}$$

(1)

It is straightforward to check that $\approx$ is an equivalence relation. Further, it is obvious from (1) that each equivalence class is either an independent set or a clique and, more generally, between every two equivalence classes either there is no edge or all possible edges are present.

Let H be a copy of $K_{t-1,t-1}$ in G with bipartition $V(H)=A\cup B$. It follows from Lemma 2.2 that A, and similarly B, is contained in some equivalence class. Let [A] and [B] be the equivalence classes containing A and B, respectively. Note that [A] and [B] are not necessary distinct. We show that $V(G)=[A]\cup [B]$ which implies the assertion of the lemma. By contradiction, suppose that $V(G)\ne [A]\cup [B]$. As G is connected, there is a vertex $v\notin [A]\cup [B]$ with a neighbor in [A] or [B], say [A]. Note that v is adjacent to the whole [A]. Therefore, $|N_G(v)\cap N_G(w)|\geqslant t-1$ for arbitrarily chosen vertex $w\in B$. Using Lemma 2.2, $v\approx w$ and hence $v\in [B]$, a contradiction.

Now, assume that $\widehat{G}$ is a complete split graph with the independent part I and the clique part C. Note that I and C are the equivalence classes of $\approx$. If $|C|\geqslant t$, then every two vertices $x\in I$ and $y\in C$ have at least $t-1$ common neighbors in C. Hence, Lemma 2.2 yields that $x\approx y$, a contradiction. $\square$

Definition 2.4

For two positive integers r and s, consider s copies of $K_{2,r}$ and let $\{u_i, u'_i\}$ be a part of size 2 in the ith copy. We denote by the graph obtained by identifying all $u'_1, \ldots , u'_s$ to a single vertex u. For instance, the graph is depicted in Fig. 1. For an integer $t\geqslant 4$, let $r=\lfloor (t-1)/2\rfloor$ and $s=t-1-r$. We define as the graph made of the vertex disjoint graphs , and by joining u to $v, v_1, \ldots , v_s$ and v to $w, w_1, \ldots , w_{t-2}$. For example, the graph is shown in Fig. 2.

Fig. 1

The graph

Fig. 2

The graph

Theorem 2.5

For any $t\geqslant 4$, .

Proof

For convenience, let and $m=m(G)$. Assume that H is a subgraph of G with minimum possible number of vertices satisfying $d(H)=m$. We need to prove the following facts about H.

Fact 1   The minimum degree of H is 2.

Since $t\geqslant 4$ and G contains a copy of $K_{2,t-1}$, we find that $m>1$. For each vertex $v\in V(H)$, it follows from $d(H-v)\leqslant d(H)$ that $\mathrm{deg} _H(v)\geqslant m$. Therefore, the minimum degree of H is at least 2. On the other hand, it is easily seen that G has no subgraph with the minimum degree more than 2, implying the desired property.

Fact 2    For every two distinct vertices $x,y \in V(H)$, $N_G(x)\cap N_G(y)\subseteq V(H)$.

For a vertex $v\in V(H)$ with $\mathrm{deg} _H(v)=2$, it follows from the minimality of |V(H)| that $d(H-v)<d(H)$ which in turn implies that $m<2$. Now, if a vertex $x\in V(G){\setminus } V(H)$ is adjacent to at least two vertices in V(H), then it follows from $m<2$ that $d(G[\{x\}\cup V(H)])>d(H)$, a contradiction. This shows the correctness of Fact 2.

Fact 3    If $u_{i_0}\in V(H)$ for some $i_0$, then u and all $u_i$ are contained in V(H). Similar statements hold for $v_i$ and $w_i$.

By contradiction, without loss of generality, assume that $u_1\in V(H)$ and $u_2\notin V(H)$. Facts 1 and 2 imply that $\{u\}\cup N_G(u_1)\subseteq V(H)$ and $N_G(u_2)\cap V(H)=\varnothing$. The minimality of |V(H)| forces that $d(H-N_G[u_1])<d(H)$ which in turn yields that $m<2(t-1)/t$. This shows that $d(G[N_G[u_2]\cup V(H)])>d(H)$, a contradiction. The proofs for $v_i$ and $w_i$ are similar.

Applying Facts 1–3 and noting that H is an induced subgraph of G, we are left with only seven candidates for V(H) as described below. Letting

$$\begin{aligned}A=\bigcup _{i=1}^rN_G[u_i], \; \, B=\bigcup _{i=1}^sN_G[v_i] \; \, \text { and } \; \, C=\bigcup _{i=1}^{t-2}N_G[w_i],\end{aligned}$$

where r, s are as defined in Definition 2.4, V(H) is equal to one of the subsets

$$\begin{aligned}\{u\}\cup A, \{v\}\cup B, \{w\}\cup C, \{v\}\cup A \cup B, \{w\}\cup B\cup C, \{u, w\}\cup A\cup C, \{w\}\cup A\cup B\cup C.\end{aligned}$$

It is a matter of straightforward calculation to show that, among the subgraphs of G induced on these seven subsets, the maximum density occurs in $G[\{u\}\cup A]$ if t is odd and in $G[\{v\}\cup A\cup B]$, otherwise. Since

$$\begin{aligned}d\big (G[\{u\}\cup A]\big )=\frac{2t^2-4t+2}{t^2-t+2} \, \, \text{ and } \, \, d\big (G[\{v\}\cup A\cup B]\big )=\frac{6t^2-14t+12}{3t^2-4t+8},\end{aligned}$$

the proof is complete. $\square$

Now we are ready to prove our upper bound on $p_c(n; K_{2,t})$.

Theorem 2.6

For any fixed integer $t\geqslant 4$,

$$\begin{aligned}p_c(n; K_{2,t})=\mathrm {O}\left( n^{-\frac{1}{\eta (t)}}\right) .\end{aligned}$$

Proof

Let and $p\gg n^{-1/\eta (t)}$. Using Theorems 2.1 and 2.5, G with high probability contains a copy of , say H. Applying Lemma 2.2, $N_{\widehat{H}}(u){\setminus }\{u_i\}=N_{\widehat{H}}(u_i){\setminus }\{u\}$ for $i=1, \ldots , r$, where r is as defined in Definition 2.4. This shows that $u_i$ is adjacent to $v, v_1, \ldots , v_s$ for any i. Hence, $|N_{\widehat{H}}(v)\cap N_{\widehat{H}}(v_j)|\geqslant t-1$ for $j=1, \ldots , s$, where s is as defined in Definition 2.4. Again, it follows from Lemma 2.2 that $N_{\widehat{H}}(v){\setminus }\{v_j\}=N_{\widehat{H}}(v_j){\setminus }\{v\}$ for any j. This shows that $v_j$ is adjacent to $w, w_1, \ldots , w_{t-2}$ for any j. Therefore, for any k, $|N_{\widehat{H}}(w) \cap N_{\widehat{H}}(w_k)|\geqslant t-1$ which implies that $N_{\widehat{H}}(w){\setminus }\{w_k\}=N_{\widehat{H}}(w_k){\setminus }\{w\}$ by Lemma 2.2. This shows that $\widehat{H}$ contains a copy of $K_{t-1, t-1}$ and so is $\widehat{G}$, since $\widehat{H}$ is a subgraph of $\widehat{G}$. As $p\gg \log n/n$, by Theorem 4.1 of [10] and Theorem 2.1, G is connected and nonbipartite with high probability. So, Lemma 2.3 yields that $\widehat{G}$ is either a complete split graph or a complete graph. If $\widehat{G}$ is a complete split graph with the independent part I and the clique part C, then, by Theorem 3.4 of [10], each vertex in I has at least np/2 neighbors in C with high probability. Thus, $|C|\geqslant t$ which contradicts Lemma 2.3. Consequently, $\widehat{G}$ is complete and the result follows. $\square$

It is natural to ask whether the upper bound given in Theorem 2.6 is in fact a threshold. For $t=4$, we give an affirmative answer to this question in the following theorem. Although a similar proof might works also for $t=5$, but it seems when $t\geqslant 6$ a different kind of argument is needed to find a threshold. So, the question remains widely open. Anyway, we will provide a lower bound on $p_c(n; K_{2,t})$ for any $t\geqslant 4$ in Sect. 3.

Theorem 2.7

$p_c(n; K_{2,4})=\Theta \left( n^{-{10}/{13}}\right)$.

Proof

By Theorem 2.6, it suffices to prove that $p_c(n; K_{2,4})=\Omega (n^{-{10}/{13}})$. If with $p\ll n^{-{10}/{13}}$, then Theorem 2.1 and the union bound theorem imply that G contains no subgraph H with $|V(H)|\leqslant 36$ and $m(H)\geqslant \frac{13}{10}$ with high probability. So, in order to prove $p_c(n; K_{2,4})=\Omega (n^{-{10}/{13}})$, it is enough to show that any graph with no subgraph H satisfying $|V(H)|\leqslant 36$ and $m(H)\geqslant \frac{13}{10}$ does not percolate in $K_{2,4}$-bootstrap process.

Fix a graph G without any subgraph H with $|V(H)|\leqslant 36$ and $m(H)\geqslant \frac{13}{10}$. We define a sequence $F_1, F_2, \ldots$ of vertex disjoint subgraphs of G by the following procedure. At each step i, we look for a copy of $K_{2,3}$ in $H_i=G-{\bigcup }_{k=1}^{i-1}V(F_k)$. If there is no such a copy, we finish the procedure. Otherwise, we choose a copy L of $K_{2,3}$ in $H_i$ with bipartition A and B, where $|A|=2$. At the beginning of step i, we set $F_i=G[V(L)]$, $\mathscr {A}_i=\{A\}$, $\mathscr {B}_i=B$, $\ell _i=\ell '_i=0$.

If there exist two adjacent vertices $u, v\in V(H_i){\setminus } V(F_i)$ such that $N_G(u)\cap A\ne \varnothing$ and $N_G(v)\cap B\ne \varnothing$, then we do the following: First choose a vertex $w\in N_G(v)\cap B$. Then, update $F_i$, $\mathscr {A}_i$, $\mathscr {B}_i$ to $G[V(F_i)\cup \{u, v\}]$, $\mathscr {A}_i\cup \{\{u, w\}\}$, $(\mathscr {B}_i\cup \{v\}){\setminus }\{w\}$, respectively, and increment $\ell _i$.

Otherwise, perform the following iterative subprocedure as long as possible: Find three distinct vertices $u, v, w\in V(H_i) {\setminus } V(F_i)$ such that $w\in N_G(u)\cap N_G(v)$ and both $N_G(u), N_G(v)$ intersect an element $P\in \mathscr {A}_i$. Add $\{u, v\}$ to $\mathscr {A}_i$ and w to $\mathscr {B}_i$. In addition, update $F_i$ to $G[V(F_i)\cup \{u, v, w\}]$ and increment $\ell '_i$.

We now state some properties of $F_i$. According to the procedure, $|V(F_i)|=2\ell _i+3\ell '_i+5$ and $|E(F_i)|\geqslant 3\ell _i+4\ell '_i+6$. As soon as $4\ell _i+\ell _i'$ surpasses 4, then $|V(F_i)|\in \{9, 10, 13, 16, 19, 20\}$ and $d(F_i)\geqslant \frac{13}{10}$ which contradicts our assumption on G. Therefore, $4\ell _i+\ell _i'\leqslant 4$ and so $|V(F_i)|\leqslant 17$. Similarly, the following properties of $F_i$ are proved using the density arguments.

Fact 1    $|E(F_i)|=3\ell _i+4\ell '_i+6$.

If not, then $|E(F_i)|\geqslant 3\ell _i+4\ell '_i+7$ and so $d(F_i)>\tfrac{13}{10}$ which is a contradiction in view of $|V(F_i)|\leqslant 17$.

Fact 2    There is no edge between $V(F_i)$ and $V(F_j)$ whenever $i\ne j$.

If not, then, since $G[V(F_i)\cup V(F_j)]$ has at most 34 vertices, it follows from $d(G[V(F_i)\cup V(F_j)])<\tfrac{13}{10}$ that $4(\ell _i+\ell _j)+(\ell '_i+\ell '_j)<0$, a contradiction.

Fact 3   There exists at most one vertex x such that $N_G(x)$ intersects both $V(F_i)$ and $V(F_j)$ whenever $i\ne j$.

If there are two distinct vertices x, y such that $N_G(x)$ and $N_G(y)$ intersect both $V(F_i)$ and $V(F_j)$, then, as $G[V(F_i)\cup V(F_j)\cup \{x, y\}]$ has at most 36 vertices, we derive that $d(G[V(F_i)\cup V(F_j)\cup \{x, y\}])<\tfrac{13}{10}$ which means that $4(\ell _i+\ell _j)+(\ell '_i+\ell '_j)+4<0$, a contradiction.

For the rest of the proof, we consider an auxiliary graph $G'$ obtained from G as follows: For every integer i and every element $\{a,b\}\in \mathscr {A}_i$, join a to all vertices in $N_G(b){\setminus } N_G(a)$ and b to all vertices in $N_G(a){\setminus } N_G(b)$. We claim that $\widehat{G}=G'$. Since any pair in $\mathscr {P}={\bigcup }_{i\geqslant 0}\mathscr {A}_i$ is an independent set in $G'$ by Fact 1, the claim concludes that G does not percolate in $K_{2,4}$-bootstrap process.

In order to prove the claim, it is enough to show that there is no pair $\{x, y\}\notin \mathscr {P}$ with $|N_{G'}(x)\cap N_{G'}(y)|\geqslant 3$. Towards a contradiction, suppose that there exists such a pair $\{x, y\}$. Let $S_1=\{x, y\}$ and fix a subset $S_2\subseteq N_{G'}(x)\cap N_{G'}(y)$ such that $|S_2|\in \{3, 4\}$ and $|P\cap S_2|\in \{0, 2\}$ for each $P\in \mathscr {P}$. Put $S=S_1\cup S_2$. By Facts 2 and 3, $V(F_i)\cap S=\varnothing$ for all i except one, say $i_0$. We drop the subscript $i_0$ from $F_{i_0}, \mathscr {A}_{i_0}, \mathscr {B}_{i_0}, \ell _{i_0}, \ell '_{i_0}$ in what follows.

First we assume that $S{\setminus } V(F)\ne \varnothing$. Set $\alpha =|S_1{\setminus } V(F)|$, $\beta =|S_2 {\setminus } V(F)|$, $\gamma =|S_2\cap \mathscr {B_1}|$ and $\delta =|\{P\in \mathscr {A} \, | \, \, |P\cap S_2|=2\}|$. Clearly, $\beta +\gamma +2\delta =|S_2|$. Letting $Z=G[S\cup V(F)]$, we have $|V(Z)|=\alpha +\beta +2\ell +3\ell '+5$ and $|E(Z)|\geqslant \alpha \gamma +\alpha \delta +2\beta +3\ell +4\ell '+6$. It follows from $d(Z)<\tfrac{13}{10}$ that

$$\begin{aligned} 7(\alpha +\beta -1)+10\alpha (\gamma +\delta -2)+4\ell +\ell '+2<0.\end{aligned}$$

(2)

In view of $\alpha +\beta \geqslant 1$, it follows from (2) that $\gamma +\delta \leqslant 1$, or equivalently, $(\gamma , \delta )\in \{(0, 0), (0, 1), (1, 0)\}$. Since $\alpha +\beta \leqslant 4$ and $\beta +\gamma +2\delta =|S_2|$, one can easily deduce from (2) that $\beta =\delta =1$, $\gamma =\ell =0$ and $\alpha \in \{1, 2\}$. Moreover, if $\alpha =1$, then it follows from (2) that $\ell '=0$ and hence $|S_1\cap \mathscr {B}|=1$. Now, in both cases $\alpha =1$ and $\alpha =2$, the structure of Z forces F to be updated to Z during the procedure, a contradiction.

We next assume that $S\subseteq V(F)$. From our procedure and Fact 1, we observe that $N_F(v)\in \mathscr {A}$ for any $v\in \mathscr {B}$. This yields $S\cap \mathscr {B}=\varnothing$. Hence, there are $A_1, A_2, A_3, A_4\in \mathscr {A}$ such that $x\in A_1$, $y\in A_2$ and $S_2=A_3\cup A_4$. Note that there exist two edges between P and Q for any $(P, Q)\in \{(A_1, A_3), (A_1, A_4), (A_2, A_3), (A_2, A_4)\}$. According to the procedure, each $X\in \mathscr {A}$ is connected to exactly one of the elements of $\mathscr {A}$ generated prior to X. This property contradicts the cyclic connection between $A_1,A_2,A_3,A_4$.

We have established the claim and so the theorem is concluded. $\square$

Remark 2.8

An easy but weak upper bound on $p_c(n; K_{2,t})$ can be found as follows. If a graph G has a copy of as a subgraph, then one can easily see that a copy of $K_{t-1,t-1}$ is contained in $\widehat{G}$. Therefore, a threshold for the existence of in gives an upper bound on $p_c(n; K_{2,t})$. This shows that $p_c(n; K_{2,t})=\mathrm {O}(n^{-(t-1)/(2t-4)})$ using Theorem 2.1.

3 The Lower Bound

In this section, we give a lower bound on $p_c(n; K_{2,t})$. In Proposition 25 of [1], Balogh, Bollobás and Morris provided a lower bound on $p_c(n; H)$ for any H. According to their result, $p_c(n; K_{2,t})=\Omega (n^{-(t+1)/(2t-2)})$. An improvement is given in the following theorem.

Theorem 3.1

For any fixed integer $t\geqslant 4$,

$$\begin{aligned}p_c(n; K_{2,t})=\Omega \left( n^{-\frac{t}{2t-3}}\right) .\end{aligned}$$

Proof

If with $p\ll n^{-{t}/(2t-3)}$, then Theorems 2.1 together with the union bound theorem yield that G contains no subgraph H with $|V(H)|\leqslant (t+2)^2$ and $m(H)\geqslant (2t-3)/t$ with high probability. So, in order to prove the theorem, it suffices to show that any graph with no subgraph H satisfying $|V(H)|\leqslant (t+2)^2$ and $m(H)\geqslant (2t-3)/t$ does not percolate in $K_{2,t}$-bootstrap process.

Fix a graph G without any subgraph H with $|V(H)|\leqslant (t+2)^2$ and $m(H)\geqslant (2t-3)/t$. Consider a maximal family $\mathscr {F}=\{F_1, \ldots , F_\ell \}$ of vertex disjoint copies of $K_{2,t-1}$ in G. Denote the vertex bipartition of $F_i$ by $\{a_{i1}, a_{i2}\}$ and $\{b_{i1}, \ldots , b_{i, t-1}\}$. Denote by $G'$ the graph obtained from G by joining $a_{i1}$ to all vertices in $N_G(a_{i2}){\setminus } N_G(a_{i1})$ and $a_{i2}$ to all vertices in $N_G(a_{i1}){\setminus } N_G(a_{i2})$ for $i=1, \ldots , \ell$. We claim that $\widehat{G}=G'$. Since the graph obtained from $K_{2,t-1}$ by adding one edge has density $(2t-1)/(t+1)>(2t-3)/t$, our assumption on G concludes that $G'$ is not a complete graph. So, the claim yields that G does not percolate in $K_{2,t}$-bootstrap process.

In order to prove the claim, it is sufficient to show that there exists no pair $\{x, y\}\notin \{\{a_{11}, a_{12}\}, \ldots , \{a_{\ell 1}, a_{\ell 2}\}\}$ so that $|N_{G'}(x) \cap N_{G'}(y)|\geqslant t-1$. By contrary, suppose that there exists such a pair $\{x, y\}$. Let $S_1=\{x, y\}$ and $p_i=|\{a_{i1},a_{i2}\}\cap S_1|$ for any i. By the assumption, $p_i\in \{0,1\}$. Further, fix a subset $S_2\subseteq N_{G'}(x)\cap N_{G'}(y)$ such that $|S_2|\in \{t-1, t\}$ and $q_i=|\{a_{i1},a_{i2}\}\cap S_2|\in \{0, 2\}$ for any i. Put $S=S_1\cup S_2$ and $k=|S|$. Assume that

$$\begin{aligned}&\alpha =|\{i \, | \, p_i=1\}|, \\&\beta =|\{i \, | \, q_i=2\}|, \\&\gamma =\big |\big \{i \, \big | \, p_i=q_i=0 \text { and there exists}\,\, j \,\,\text {with } b_{ij}\in S\big \}\big |,\\&\lambda =\big |\big \{b_{ij} \, \big | \, b_{ij}\in S_1 \text { and } p_i=1\big \}\cup \big \{b_{ij} \, \big | \, b_{ij}\in S_2 \text { and } q_i=2\big \}\big |,\\&\mu =\big |\big \{b_{ij} \, \big | \, b_{ij}\in S_1 \text { and } q_i=2\big \}\cup \big \{b_{ij} \, \big | \, b_{ij}\in S_2 \text { and } p_i=1\big \}\big |,\\&\nu =\big |\big \{b_{ij} \, \big | \, p_i=q_i=0 \text { and } b_{ij}\in S\big \}\big |. \end{aligned}$$

Based on the above definitions, one may find that $1\leqslant \alpha +\beta +\gamma \leqslant k$ and $\gamma \leqslant \nu$. The inequality $\gamma \leqslant \nu$ is clear. To prove $1\leqslant \alpha +\beta +\gamma \leqslant k$, note that the subsets $\{i \, | \, p_i=1\}$, $\{i \, | \, q_i=2\}$ and $\{i \, | \, p_i=q_i=0 \text { and there exists} j \text {with } b_{ij}\in S\}$ are mutually distinct and thus their union, say U, is of size $\alpha +\beta +\gamma$. It follows from the maximality of $\mathscr {F}$ that $U\ne \varnothing$ and hence $\alpha +\beta +\gamma \geqslant 1$. Moreover, one may naturally assign to each $i\in U$ a subset $R_i\subseteq S$ with $|R_i|\leqslant 2$. The subsets $R_i$ are mutually distinct and so $|U|\leqslant \sum _{i\in U}|R_i|\leqslant |S|$. This means that $\alpha +\beta +\gamma \leqslant k$. Let

$$\begin{aligned}H=G\left[ S\cup \bigcup _{S\cap V(F_i)\ne \varnothing }V(F_i)\right] .\end{aligned}$$

It is easy to see that

$$\begin{aligned}|V(H)|=(\alpha +\beta +\gamma )(t+1)+k-\alpha -2\beta -\lambda -\mu -\nu \end{aligned}$$

and

$$\begin{aligned}|E(H)|\geqslant 2(\alpha +\beta +\gamma )(t-1)+2(k-\beta -2)-\mu .\end{aligned}$$

Therefore, the condition $k\leqslant t+2$ implies that $|V(H)|\leqslant (t+2)(t+1)+(t+2)=(t+2)^2$ and so $m(H)<(2t-3)/t$ by the assumption on G. It follows from $d(H)<(2t-3)/t$ that

$$\begin{aligned}t(\alpha +\beta -\gamma +2\lambda +\mu +2\nu -4)<3(\beta -\gamma +\lambda +\mu +\nu -k),\end{aligned}$$

which can be rewritten as

$$\begin{aligned}(t-3)\big ((\alpha +\beta +\gamma -1)+\mu \big )+(2t-3)\big ((\nu -\gamma )+\lambda \big )+3\big (\alpha +\gamma +\big (k-(t+1)\big )\big )<0.\end{aligned}$$

We have reached a contradiction, since the left hand side of the inequality above is nonnegative. This establishes the claim, as required. $\square$

4 Concluding Remarks

In this paper, we have determined an upper bound for the threshold of $K_{2,t}$-bootstrap percolation by proposing a subgraph whose existence forces the graph to percolate. Note that if the upper bound given in Theorem 2.6 is tight for any t, then Theorem 5.4 of [10] implies that $K_{2, t}$-bootstrap percolation has a coarse threshold. It means that the threshold given in Theorem 2.7 is coarse. As it has mentioned before, the determination of $p_c(n; K_{2, t})$ remains open for $t\geqslant 5$.