Abstract
This study establishes new asymptotic bounds for the expected propagation time of probabilistic zero forcing (PZF), a stochastic coloring process on graphs. By analyzing grid graphs, $d$-regular graphs, and $n$-dimensional hypercubes, the authors bridge theoretical graph theory with randomized rumor-spreading models. Key findings include an optimal $\Theta(m+n)$ bound for grids and an $O(n \log n)$ bound for hypercubes.
Introduction
Zero forcing is a dynamic process where "blue" (active) vertices color their "white" (inactive) neighbors blue according to specific rules. While classical zero forcing is deterministic—a vertex forces its neighbor only if it is the unique white neighbor—probabilistic zero forcing (PZF) introduces a stochastic element: every blue vertex has a non-zero probability of forcing any white neighbor at each time step.
This process serves as a powerful model for real-world phenomena such as viral marketing and rumor propagation. The central challenge addressed in this research is determining the "expected propagation time"—the average number of steps required to color the entire graph—across various fundamental architectures.
Methodology
The researchers employed a combination of probabilistic analysis and combinatorial graph theory to derive their bounds:
- Coupling Arguments: Upper bounds were established by defining modified, demonstrably slower processes.
- Probabilistic Inequalities: Tools like Chernoff bounds and Chebyshev’s inequality were used to bound deviations from expected behavior.
- Edge Isoperimetric Inequalities: These were critical for hypercubes to estimate the connectivity between blue and white vertex sets.
- Simulations: Theoretical proofs were validated using 1000 trials per configuration for grid graphs ($m, n \in [2, 14]$) and hypercubes ($n \in [1, 16]$).
Key Insights
The study reveals that propagation speed is heavily influenced by graph "density" and connectivity. In $d$-regular graphs, propagation time is inversely proportional to the degree $d$; higher connectivity provides more opportunities for the blue color to spread. Conversely, hypercubes demonstrate remarkable efficiency; despite having $2^n$ vertices, the expected propagation time is only $O(n \log n)$, reflecting their high connectivity and small diameter. For grid graphs, the process behaves like a wave front, scaling linearly with the dimensions ($\Theta(m+n)$).
Results and Discussion
The theoretical bounds were supported by extensive simulation data. For grid graphs, the linear relationship with $m$ and $n$ is clearly visible in the experimental results.
Summary of Bounds
- Grid Graphs ($G_{m \times n}$): $\Theta(m+n)$.
- $d$-Regular Graphs: Upper bound of $O(n \cdot \frac{\log d}{d})$ and lower bound of $\Omega(n \cdot \frac{\log \log d}{d})$.
- Hypercube Graphs: $O(n \log n)$.
While the $O(n \log n)$ bound for hypercubes is mathematically proven, simulations suggest a tighter linear fit of approximately $n + 0.8$ for small $n$. This discrepancy highlights an opportunity for future work to prove a linear $O(n)$ bound. Additionally, narrowing the gap between the $\log \log d$ and $\log d$ terms for $d$-regular graphs remains an open theoretical challenge.
Summary updated