𝟐 \boldsymbol{2} -Neighbor Bootstrap Percolation on Odd Graphs

Ali Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie, [email protected], [email protected] · 2026

Read 𝟐 \boldsymbol{2} -Neighbor Bootstrap Percolation on Odd Graphs by Ali Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie, [email protected], [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03687.txt.

Introduction

Mohammadian, Rezaie Zareie, and Tayfeh-Rezaie solve minimum seed problems for bootstrap percolation on odd graphs. In this process, vertices start active in a chosen seed set. Each round, an inactive vertex with at least r active neighbors turns active. The question asks for the smallest seed set that ends up activating the whole graph. Two graphs are studied, the odd graph and the bipartite odd graph, both on a ground set of size 2k plus 1.

Exact formulas are proven for the two-neighbor rule. The odd graph needs the ceiling of (k squared plus 3k plus 2) over 4 seeds. The bipartite odd graph needs the ceiling of (k squared plus 2k plus 3) over 2. The first formula confirms a conjecture posed in 2021 by Grippo and co-authors. Combinatorics readers get sharp thresholds for a classic spread process.

Catalog record

CREATORAli Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie, [email protected], [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03687

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

𝟐 \boldsymbol{2} -Neighbor Bootstrap Percolation on Odd Graphs Ali Mohammadian, Sina Rezaie Zareie, Behruz Tayfeh-Rezaie, [email protected], [email protected] Abstract The r r -neighbor bootstrap percolation process on a graph G G is a vertex-activation process that begins with a set of initially active vertices. In each subsequent round, every inactive vertex having at least r r active neighbors becomes active. Denote by m ⁡ ( G , r ) m(G,r) the minimum number of initially active vertices whose activation eventually spreads to all vertices of G G . In this article, among other results, we prove that ( k 2 + 2 ​ k + 3 ) / 4 ⩽ m ⁡ ( O k , 2 ) ⩽ ( k 2 + 5 ​ k + 3 ) / 3 (k^{2}+2k+3)/4\leqslant m(\mathbbmsl{O}_{k},2)\leqslant(k^{2}+5k+3)/3 , where O k \mathbbmsl{O}_{k} is the odd graph on a ground set of size 2 ​ k + 1 2k+1 . This confirms a conjecture posed in 2021 by Grippo, Pastine, Torres, Valencia-Pabon, and Vera. Keywords: bipartite odd graph, r r -neighbor bootstrap percolation, odd graph, percolating set. AMS 2020 Mathematics Subject Classification: 05C35, 60K35. 1 Introduction Bootstrap percolation processes on graphs constitute a class of cellular automata, a concept introduced in 1966 by von Neumann [ 12 ] . One of the most extensively studied examples is the r -neighbor bootstrap percolation process which was introduced in 1979 by Chalupa, Leath, and Reich [ 6 ] in the context of ferromagnetism. This process is closely connected to several areas of graph theory, including weak saturation and P_{3} -convexity. It has also appeared in the literature under various names such as irreversible threshold process, influence propagation, and dynamic monopoly. Throughout this article, all graphs are assumed to be finite, undirected, and without multiple edges or loops. For a graph G , let V(G) and E(G) denote vertex set and edge set of G , respectively. Given a nonnegative integer r , the r - neighbor bootstrap percolation process on a graph G begins with a set V_{0}\subseteq V(G) of initially active vertices. For each integer i\geqslant 1 , the set of active vertices at round i is defined by V_{i}=V_{i-1}\cup\Big\{v\in V(G)\,\Big|\,\text{$v$ is adjacent to at least $r$ vertices in $V_{i-1}$}\Big\}. The set V_{0} is called a percolating set if V_{t}=V(G) for some integer t\geqslant 0 . We denote by m(G,r) the minimum cardinality of a percolating set in the r -neighbor bootstrap percolation process on G . Percolating sets are sometimes referred to as ‘contagious sets’. The case r=2 is indeed the most heavily studied in the literature. In the context of graph convexity, the parameter m(G,2) is called the ‘ P_{3} -hull number’ of G . An edge analogue of the r -neighbor bootstrap percolation process is known as the r -edge bootstrap percolation process. Given a nonnegative integer r , the r - edge bootstrap percolation process on a graph G begins with a set E_{0}\subseteq E(G) of initially active edges. For each integer i\geqslant 1 , the set of active edges at round i is defined by E_{i}=E_{i-1}\cup\Big\{e\in E(G)\,\Big|\,\text{at least one endpoint of $e$ is incident to at least $r$ edges in $E_{i-1}$}\Big\}. The set E_{0} is called a percolating set if E_{t}=E(G) for some integer t\geqslant 0 . Let m_{e}(G,r) denote the minimum cardinality of a percolating set in the r -edge bootstrap percolation process on G . The case r=2 was studied by Lenormand and Zarcone [ 10 ] in 1984 under a different name. From a result of [ 8 ] , we have \mathchoice{\vbox{\hbox{\small$\displaystyle\frac{m_{e}(G,r)}{r}$}}}{\textstyle\frac{m_{e}(G,r)}{r}}{\scriptstyle\frac{m_{e}(G,r)}{r}}{\scriptscriptstyle\frac{m_{e}(G,r)}{r}}\leqslant m(G,r)\leqslant m_{e}(G,r)+\Big|\big\{v\in V(G)\,\big|\,\deg(v)<r\big\}\Big|, (1) where \deg(v)=|\{x\in V(G)\,|\,x\text{ is adjacent to }v\}| . Determining the extremal parameters m(G,r) and m_{e}(G,r) is one of the fundamental problems in bootstrap percolation theory. These parameters have been studied extensively for numerous graph classes, including grids, tori, and Hamming graphs, see for example [ 1 ] , [ 11 ] , and [ 13 ] . They have also been investigated for random graphs, see for example [ 9 ] . We next recall some standard notation and terminology. Let k be a positive integer and set M=\{1,\ldots,2k+1\} . The odd graph \mathbbmsl{O}_{k} is the graph whose vertices are the k -subsets of M in which two vertices S and T are adjacent if S\cap T=\varnothing . The term “odd graph” is due to Biggs and Gardiner [ 5 ] who observe that each edge can be labeled by the unique element of M not contained in either endpoint, representing the “odd man out”. Odd graphs form a highly symmetric subclass of Kneser graphs and exhibit remarkable algebraic and geometric properties not shared by general members of the Kneser family. The bipartite odd graph \mathbbmsl{B}_{k} is the graph whose vertex set consists of all k -subsets and all (k+1) -subsets of M in which two vertices S and T are adjacent if S\subsetneqq T . In fact, \mathbbmsl{B}_{k} is the bipartite double cover of \mathbbmsl{O}_{k} . Recall that the bipartite double cover of a graph G with vertex set \{v_{1},\ldots,v_{n}\} is the bipartite graph with vertex bipartition \{v_{1}^{\prime},\ldots,v_{n}^{\prime}\}\cup\{v_{1}^{\prime\prime},\ldots,v_{n}^{\prime\prime}\} in which v_{i}^{\prime} is adjacent to v_{j}^{\prime\prime} if v_{i} is adjacent to v_{j} in G . Equivalently, the bipartite double cover of G is isomorphic to the direct product G\times K_{2} , where K_{2} is the complete graph on two vertices. It is well known that odd graphs and bipartite odd graphs are distance-regular [ 3 ] . In this article, we focus on the case where r=2 and study the parameters m(\mathbbmsl{O}_{k},2) , m(\mathbbmsl{B}_{k},2) , and m_{e}(\mathbbmsl{B}_{k},2) . Specifically, we employ the polynomial method introduced by Hambardzumyan, Hatami, and Qian [ 8 ] to determine the exact values of m(\mathbbmsl{B}_{k},2) and m_{e}(\mathbbmsl{B}_{k},2) , as presented in the following theorem. Theorem 1.1 . For every positive integer k , m_{e}(\mathbbmsl{B}_{k},2)=k^{2}+2k+3\quad\text{ and }\quad m(\mathbbmsl{B}_{k},2)=\left\lceil\mathchoice{\vbox{\hbox{\small$\displaystyle\frac{k^{2}+2k+3}{2}$}}}{\textstyle\frac{k^{2}+2k+3}{2}}{\scriptstyle\frac{k^{2}+2k+3}{2}}{\scriptscriptstyle\frac{k^{2}+2k+3}{2}}\right\rceil. Moreover, Grippo, Pastine, Torres, Valencia-Pabon, and Vera [ 7 ] conjectured that m(\mathbbmsl{O}_{k},2)=\mathnormal{\Theta}(k^{2}) . We resolve this conjecture affirmatively by proving the following theorem. Theorem 1.2 . For every positive integer k , \mathchoice{\vbox{\hbox{\small$\displaystyle\frac{k^{2}+2k+3}{4}$}}}{\textstyle\frac{k^{2}+2k+3}{4}}{\scriptstyle\frac{k^{2}+2k+3}{4}}{\scriptscriptstyle\frac{k^{2}+2k+3}{4}}\leqslant m(\mathbbmsl{O}_{k},2)\leqslant\mathchoice{\vbox{\hbox{\small$\displaystyle\frac{k^{2}+5k+3}{3}$}}}{\textstyle\frac{k^{2}+5k+3}{3}}{\scriptstyle\frac{k^{2}+5k+3}{3}}{\scriptscriptstyle\frac{k^{2}+5k+3}{3}}. The article is organized as follows. In Section 2 , we present the necessary preliminaries and introduce equivalent definitions for odd graphs and bipartite odd graphs. In Section 3 , we determine the exact values of m(\mathbbmsl{B}_{k},2) and m_{e}(\mathbbmsl{B}_{k},2) for all k . Finally, in Section 4 , we establish upper and lower bounds on m(\mathbbmsl{O}_{k},2) , thereby resolving a conjecture posed in [ 7 ] . 2 Preliminaries In this section, we provide the necessary preliminaries and background for the rest of the article. We begin by presenting equivalent definitions for odd graphs and bipartite odd graphs that are essential for our subsequent proofs. As usual, for two adjacent vertices u and v , the notation uv or u\sim v represents the edge joining them. Recall that k is a positive integer and let M=\{1,\ldots,2k+1\} . We fix the partition \{X,Y\} of M with X=\{1,\ldots,k\} and Y=\{k+1,\ldots,2k+1\} . For each subset S\subseteq M , we write S_{X}=S\cap X and S_{Y}=S\cap Y to simplify the notation. Set \mathcal{F}=\Big\{S\subseteq M\,\Big|\,|S_{X}|=|S_{Y}|\ \text{or}\ |S_{Y}|=|S_{X}|+1\Big\}. We show that \mathbbmsl{B}_{k} is isomorphic to the graph with vertex set \mathcal{F} in which two vertices S and T are adjacent if |S\triangle

Read the complete text