View PDF HTML (experimental)

Abstract:We introduce and analyze a competitive extension of classical bootstrap percolation on the Erdős--Rényi random graph $G(n,p_n)$. Nodes can be red, black, or white, with red and black representing two competing active states. Starting from two sets of initially active seeds, white nodes activate according to independent Poisson clocks and become permanently red or black whenever the number of active neighbors of one color exceeds that of the competing color by at least a fixed threshold $r\geq2$.
We characterize the asymptotic dynamics and final sizes of the two competing activation processes over all relevant seed-density scales. Our results reveal a sharp qualitative dichotomy. In the sub-critical regime, competition is asymptotically negligible at first order: each process reaches the same normalized final size as it would in the absence of the competing process. In the super-critical regime, instead, the initial advantage of the process with the larger seed density is amplified: the dominant process activates $n-o(n)$ nodes, while the competing process is suppressed and remains confined to a much smaller scale.
Beyond final-size asymptotics, we derive a fluid-limit description of the joint activation trajectories and characterize the relevant activation time scales. The analysis combines uniform concentration estimates, deterministic limiting Cauchy problems, stochastic coupling, and multiscale arguments.

Submission history

From: Emilio Leonardi [view email]
[v1] Wed, 1 May 2024 07:38:52 UTC (179 KB)
[v2] Mon, 6 May 2024 10:14:05 UTC (180 KB)
[v3] Wed, 8 May 2024 13:09:48 UTC (180 KB)
[v4] Thu, 2 Oct 2025 09:32:01 UTC (189 KB)
[v5] Tue, 8 Sep 2026 11:21:33 UTC (182 KB)