2026/07/27 by Ioana Dumitriu, Muchen Ju, Hai-Xiao Wang
#math.PR #cs.DM #cs.IT #math.CO #math.IT
Majority dynamics is a two-opinion process in which each vertex repeatedly updates to the majority opinion among its neighbors. We study this process on a resampled sparse binary stochastic block model in the assortative regime. At each time step, a graph is sampled from the current opinion partition: vertices with the same opinion are joined with probability α=alog N/N, while vertices with differing opinions are joined with probability β=blog N/N, where a>b>1. Let Bt and Rt denote the blue and red camps at time t. We show that the weighted advantage \widetildeΔt =b|Bt|-a|Rt|, rather than the unweighted advantage Δt=|Bt|-|Rt| alone, governs the pace to unanimity. Our results, which hold with high probability as \(N→∞\), identify three regimes for blue unanimity under the initial blue advantage, i.e., Δ0>0: constant time, subpolynomial time, and polynomial time. First, when \widetildeΔ0 \gtrsim -N/√(log N), blue unanimity occurs within three updates. Second, when \widetildeΔ0 < 0 and |\widetildeΔ0| = o(N), blue unanimity occurs within No(1) updates. Furthermore, when \widetildeΔ0 < 0, |\widetildeΔ0| = O(N), and Δ0≫√(N/log N), blue unanimity still occurs within NI0+o(1) updates, where I0= (ReLU(√(a(|R0|)/(N))-√(b(|B0|)/(N))))2, and ReLU(x)=max\x,0\. Conversely, away from the weighted threshold, when |B0|/|R0|≤ a/b-κ and Δ0>0, NI0 - o(1) updates are necessary for blue unanimity. Our analysis relies on detailed estimates for one-vertex flip probabilities in sparse binomial differences, which could be of independent interest.