REVIEW 2 major objections 4 minor 25 references
Majority Dynamics on Resampled Sparse Erd\H{o}s--R\'enyi Graphs: Gaussian Winner Selection and Pace to Unanimity
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read On a sparse random graph redrawn every day, majority dynamics picks the eventual winner with Gaussian probability in the critical window and reaches unanimity in about log N / log log N updates.
desk verdict Substantial resampled-graph variant with clean Gaussian winner-selection results; the main risk is load-bearing large-deviation estimates imported from an unpublished companion. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the one-step advantage update. For a vertex in the current blue or red camp, the difference between the number of opposite-color and same-color neighbors is a difference of two independent binomials; the probability that this difference is positive is the flip probability $p_t^R$ or $p_t^B$. The paper approximates these flip probabilities in two ways: in the Gaussian window by a continuity-corrected normal distribution with $O(1/\log N)$ error obtained through Poisson coupling, and in the tail by a large-deviation rate $I(x,y)=(\max\{0,\sqrt{x}-\sqrt{y}\})^2$ that makes a sublinear red camp vanish at a power-law rate. Together with the exact identity $\mathbb E[\Delta_{t+1}\mid y_t]=N(p_t^R-p_t^B)+\Delta_t(1-p_t^R-p_t^B)$, a read-2 concentration bound upgrades the conditional mean into a two-sided amplification estimate $\Delta_{t+1}\approx c\sqrt{\log N}\,\Delta_t$. A one-step central limit theorem, uniform over the critical window, supplies the Gaussian winner selection.
What would settle it
Simulate $10^5$ vertices with $b=2$ from a deterministic initial configuration with $x_0=1$ and record the fraction of runs where blue reaches unanimity by $T_N+3$; Theorem 1.7 requires this fraction to converge to $\Phi(1)\approx 0.8413$, with red winning the remaining mass and unanimity time concentrated near $\log N/\log\log N$, so a limiting deviation from those values would refute the central claim.
Extended reading notes
Core claim
The central claim is a sharp winner-selection law for the resampled sparse regime. Working with $p=b\log N/N$ for fixed $b>1$, and uniformly over deterministic initial configurations satisfying $x_0=\sqrt{2/\pi}\,\Delta_0\sqrt{p}=O(1)$, the paper proves that blue unanimity by time $T_N+3$ holds with probability $\Phi(x_0)+o(1)$, red unanimity with probability $\Phi(-x_0)+o(1)$, and $T_N+3=(1+o(1))\log N/\log\log N$. The mechanism is two-stage: the first update converts the normalized initial advantage into a Gaussian random variable of unit variance, so its sign is a Gaussian coin flip, and each later update multiplies the selected advantage by a factor of order $\sqrt{\log N}$ until the constant-day completion threshold $N/\sqrt{\log N}$ is crossed. The same estimates give a two-day consensus threshold above an explicit constant multiple of $N/\sqrt{\log N}$ and, in the intermediate regime, high-probability upper and lower bounds on the time to blue unanimity.
Load-bearing premise
The load-bearing premise is that the large-deviation flip-probability formulas and the read-2 concentration bound imported from the companion preprint cited as [9] are correct; the paper does not prove them here, and if they were wrong the thresholds and amplification factor would change.
Editorial extensions
If this is right
- In the critical window, the eventual winner is decided by the first update: blue wins with probability $\Phi(x_0)$ and red with $\Phi(-x_0)$, and the rest of the process changes that probability by only $o(1)$.
- For initial advantages in the critical and intermediate scales, the time to unanimity is $(1+o(1))\log N/\log\log N$ with high probability.
- An initial advantage of order $N/\sqrt{\log N}$ with a coefficient above the explicit threshold $K_{\mathrm{ER}}^{(2)}(b)$ is enough for blue unanimity within two updates.
- At exactly zero initial advantage the process is asymptotically a fair coin: blue and red each win with probability $1/2-o(1)$.
- The graph density enters the winner-selection law only through the normalization $\sqrt{2/\pi}\,\Delta_0\sqrt{p}$, so the same Gaussian curve describes every fixed $b>1$ in the critical window.
Reading between the lines
- A natural testable extension, not pursued in the paper, is the static-graph version of the 'optimal power of few' conjecture: the same first-update Gaussian selection may persist, but the correlation between a fixed graph and the evolving opinions could change both the normalization and the unanimity time.
- The two-stage picture suggests that if the update rule includes a self-opinion weight or inertia, the critical window should remain $\Delta_0=O(\sqrt{N/\log N})$ while the Gaussian mean shifts; this could be checked numerically before attempting a proof.
- The imported flip-probability large-deviation estimates are the fragile component; a direct Monte Carlo estimate of $p_t^R$ and $p_t^B$ at a balanced configuration would give a cheap check of the rate function $I$ and hence of the two-day threshold.
- Below $b=1$, isolated vertices make unanimity impossible on typical resampled graphs, so the phase diagram must change qualitatively there; a version allowing abstention or self-weight might still exhibit Gaussian selection on the non-isolated component.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies synchronous majority dynamics on N vertices where, at each time step, a fresh graph G(N,p) with p=b log N/N and b>1 is resampled. For an initial blue advantage Δ0, it claims three regimes: (i) if Δ0 ≥ K N/√log N with K>K_ER2(b), blue unanimity is reached within two updates with probability 1-O(N^{-ξ}); (ii) in the intermediate regime √(N/log N) ≪ Δ0 ≲ N/√log N, the blue-unanimity time is bounded above and below by explicit horizons, of order (1+o(1)) log N/log log N when Δ0 is at the lower scale; (iii) in the critical window Δ0√p=O(1), the blue-winning probability is Φ(√(2/π)Δ0√p)+o(1) and unanimity occurs within (1+o(1)) log N/log log N updates. The proofs introduce one-vertex flip probabilities, a Poisson-coupling continuity correction for Gaussian estimates of the one-step advantage, a large-deviation rate function I(x,y)=(ReLU(√x-√y))^2 that defines the two-day threshold, and a stepwise amplification lemma; the critical-window result additionally uses the Berkowitz–Devlin one-step central limit theorem.
Significance. If the results are correct, the paper resolves the resampled version of the Tran–Vu optimal-power-of-few conjecture and provides a strikingly clean Gaussian winner-selection rule with an explicit coefficient √(2/π). The main constants r*, K_ER2(b), c1 and C2 are explicit, and Theorem 1.7 gives a concrete, falsifiable prediction that agrees with the reported simulations. The Poisson-coupling continuity correction in Appendix A and the constant-time arguments in Section 3 are explicit and appear sound. The modular proof strategy is a strength, but a substantial part of the large-deviation and concentration machinery is imported from the authors' unpublished companion [9], and the present ER setting is the boundary case a=b of that companion's assortative SBM. Until those inputs are independently verifiable, the central theorems rest on an external verification gap.
major comments (2)
- [Appendix H; Lemmas 3.1, 3.2, 4.1] The large-deviation estimates Corollaries H.2–H.4, especially H.4, are load-bearing but are not proved in this manuscript; they are stated as ER specializations of the unpublished companion [9]. Corollary H.4 is used in Lemma 3.1 to obtain the flip-probability exponents N^{-I(b_B,b_R)+o(1)} that define the extinction threshold r*, and Corollary H.2 is used in Lemma 3.2; through Lemma 4.1 these estimates propagate to Theorems 1.4, 1.5, and 1.7. The specialization sets both edge probabilities and both logarithmic density constants equal, i.e. a=b, which is the boundary of the strictly assortative regime a>b described for [9]. If the proofs in [9] require strict assortativity, or if the rate function differs at a=b, then r*, K_ER2(b), and the amplification constants c1,C2 would change. Please either provide self-contained proofs of H.3/H.4, or give a precise statement of the theorem in [9] covering the boundary case with the required uniformity; as written, the central claims are not independently verifiable from this manuscript.
- [Appendix G; Lemmas 3.2 and 4.1] Corollary G.3 and Lemma G.4 are also cited to the unpublished companion [9] rather than proved. Lemma G.4 is used to prove the high-probability amplification in Lemma 4.1 and the reduction in Lemma 3.2, so it is a load-bearing concentration input. Since Lemma G.2 states the read-k Chernoff bound, the missing step is short: Corollary G.3 follows from DKL(u∥v) ≥ 2(u−v)^2, and Lemma G.4 then follows by observing that the next-color indicators form a read-2 family. Please include this derivation or a published reference so that the proof of Theorem 1.5 and the two-day result does not depend on an unpublished source.
minor comments (4)
- [Section 1.1, Eq. (1.14)] The two horizons denoted by T and T are typographically easy to confuse; using \underline{T} and \overline{T} or T_low and T_up would improve readability.
- [Corollary 1.6] The display for the lower and upper hitting-time bounds has malformed floor and ceiling brackets in the rendered text; please fix the typesetting so that the assertion is unambiguous.
- [Appendix F] Theorem F.1 is restated from the arXiv preprint [3]; if a published version now exists, please update the citation, and if not, please state explicitly that the critical-window proof relies on an external unpublished theorem.
- [Abstract and Section 1] The abstract says the paper resolves the resampled version of Conjecture 1.1; it would be helpful to state in the introduction that the original static-graph conjecture remains open, to avoid any impression that the static conjecture has been settled.
Circularity Check
No circular reduction; the Gaussian winner-selection probability is derived, but load-bearing flip-probability estimates are imported from the authors' unpublished companion preprint.
full rationale
I walked the derivation chain. The critical-window result Theorem 1.7 is assembled from Lemma 5.1 (the one-step conditional mean, proved from the self-contained continuity-corrected Gaussian estimates in Lemma 2.4), Lemma 5.2 (the uniform one-step CLT, resting on the external Berkowitz–Devlin theorem and on a sparse-binomial approximation), Lemma 5.3 (anti-concentration), and the time-shifted amplification Theorem 1.5. The amplification Lemma 4.1 uses Lemma 2.4 together with the read-2 concentration inequality whose proof is given in Appendix G. No equation in this chain has the target event, P(R_{T_N+3}=∅ | y0), as an input; x0 and the constant √(2/π) come from the first-update Gaussian law, not from fitting. The numerical experiments are illustrative and do not supply any parameter to the theorems. The one genuinely load-bearing dependence on the authors' own work is Appendix H: Corollaries H.2 and H.4 state flip-probability asymptotics and are 'obtained by specializing [9]', the same authors' unpublished companion preprint, 'without repeating their proofs.' These estimates feed Lemma 3.1 and Lemma 3.2 and therefore determine the two-day threshold r* and K_ER2(b); an error in [9] at the a=b boundary would shift Theorem 1.4 and the amplification constants downstream. This is a verification gap and a self-citation burden, not a circular reduction: the cited companion results are estimates for the same process family, not restatements of the present theorems, and the central winner-selection probability is not equivalent to any fitted or assumed input by construction. Accordingly I find no significant circularity.
Assumptions & free parameters
assumptions (5)
- domain assumption p = b log N / N for fixed b > 0 (Assumption 1.2)
- domain assumption b > 1 (Assumption 1.3)
- domain assumption Berkowitz-Devlin one-step CLT (Theorem F.1)
- domain assumption Read-2 concentration and sparse-binomial large-deviation estimates from the companion work [9] (Lemma G.4 and Corollaries H.2, H.4)
- standard math Standard tools: Berry-Esseen theorem, Le Cam's inequality, read-k Chernoff bound
Cite this review
Pith. "Pith review of Majority Dynamics on Resampled Sparse Erd\H{o}s--R\'enyi Graphs: Gaussian Winner Selection and Pace to Unanimity." pith.science (2026). https://pith.science/paper/LQFHD364
@misc{pith2026260806159,
author = {Pith},
title = {Pith review of: Majority Dynamics on Resampled Sparse Erd\Hos--R\'enyi Graphs: Gaussian Winner Selection and Pace to Unanimity},
year = {2026},
howpublished = {\url{https://pith.science/paper/LQFHD364}},
note = {Machine review of arXiv:2608.06159}
}
abstract
We study the two-opinion majority dynamics process: at each time step, every vertex adopts the majority opinion among its neighbors, retaining its current opinion if there is a tie. Independently at each step, the interaction graph is resampled from the sparse Erd\H{o}s--R\'enyi model $\mathbb G(N,p)$ with $p=b\log N/N$ and fixed $b>1$. Our results identify three regimes governed by the initial advantage $\Delta_0=|B_0|-|R_0|$, where $|B_0|$ and $|R_0|$ denote the initial blue and red camps, respectively. First, an initial blue advantage above an explicit constant multiple of $N/\sqrt{\log N}$ leads to blue unanimity within two updates with high probability. Second, throughout the intermediate regime $\sqrt{N/\log N}\ll\Delta_0\lesssim N/\sqrt{\log N}$, we obtain explicit high-probability upper and lower bounds on the blue-unanimity time. Finally, uniformly in the critical window $\Delta_0\sqrt p=O(1)$, the blue- and red-unanimity probabilities equal $\Phi(\sqrt{2/\pi}\,\Delta_0\sqrt p)+o(1)$ and $\Phi(-\sqrt{2/\pi}\,\Delta_0\sqrt p)+o(1)$, respectively, and unanimity is reached within $(1+o(1))\log N/\log\log N$ many updates with high probability. This resolves the resampled version of the \emph{optimal power-of-few} conjecture raised by Tran and Vu (2025).
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[9]
Majority Dynamics on Assortative Sparse Stochastic Block Models
Ioana Dumitriu, Muchen Ju, and Hai-Xiao Wang. “Majority Dynamics on Assortative Sparse Stochastic Block Models”. In:arXiv preprint arXiv:2607.24652(2026) (cit. on pp. 11, 41, 42)
work page Pith review arXiv 2026
-
[1]
Fast and Exact Majority in Popula- tion Protocols
Dan Alistarh, Rati Gelashvili, and Milan Vojnovi´ c. “Fast and Exact Majority in Popula- tion Protocols”. In:Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. PODC’15. Donostia-San Sebasti´ an, Spain: Association for Computing Machin- ery, 2015, 47–56.isbn: 9781450336178.doi:10.1145/2767386.2767429.url:https://doi. org/10.1145/...
-
[2]
Itai Benjamini, Siu-On Chan, Ryan O’Donnell, Omer Tamuz, and Li-Yang Tan. “Conver- gence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs”. In:Stochastic Processes and their Applications126.9 (2016), pp. 2719–2733 (cit. on p. 10)
work page 2016
-
[3]
Central Limit Theorem for Majority Dynamics: Bribing Three Voters Suffices
Ross Berkowitz and Pat Devlin. “Central limit theorem for majority dynamics: Bribing three voters suffices”. In:arXiv preprint arXiv:2010.08172(2020) (cit. on pp. 10, 20, 39)
work page Pith review arXiv 2020
-
[4]
Phase transitions for detecting la- tent geometry in random graphs
Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj. “Phase transitions for detecting la- tent geometry in random graphs”. In:Probability Theory and Related Fields178.3 (2020), pp. 1215–1289 (cit. on p. 23)
work page 2020
-
[5]
Testing for high-dimensional geometry in random graphs
S´ ebastien Bubeck, Jian Ding, Ronen Eldan, and Mikl´ os Z R´ acz. “Testing for high-dimensional geometry in random graphs”. In:Random Structures & Algorithms49.3 (2016), pp. 503–532 (cit. on p. 23)
work page 2016
-
[6]
Spectra of high-dimensional sparse random geometric graphs
Yifan Cao and Yizhe Zhu. “Spectra of high-dimensional sparse random geometric graphs”. In:arXiv preprint arXiv:2507.06556(2025) (cit. on p. 23)
arXiv 2025
-
[7]
Majority dynam- ics on sparse random graphs
Debsoumya Chakraborti, Jeong Han Kim, Joonkyung Lee, and Tuan Tran. “Majority dynam- ics on sparse random graphs”. In:Random Structures & Algorithms63.1 (2023), pp. 171–191 (cit. on p. 10)
work page 2023
Show all 25 references
-
[8]
Spectral Distribution of Adjacency and Laplace Matrices of Random Graphs
Xue Ding and Tiefeng Jiang. “Spectral Distribution of Adjacency and Laplace Matrices of Random Graphs”. In:The Annals of Applied Probability20.6 (2010), pp. 2086–2117 (cit. on p. 23)
2010
-
[10]
A moment inequality with an application to the central limit theorem
Carl-Gustav Esseen. “A moment inequality with an application to the central limit theorem”. In:Scandinavian Actuarial Journal1956.2 (1956), pp. 160–170.doi:10.1080/03461238. 1956.10414946.url:https://doi.org/10.1080/03461238.1956.10414946(cit. on p. 13)
1956
-
[11]
Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
Nikolaos Fountoulakis, Mihyun Kang, and Tam´ as Makai. “Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs”. In:Random Structures & Algorithms57.4 (2020), pp. 1134–1156 (cit. on p. 10)
2020
-
[12]
A Tail Bound for Read-kFamilies of Functions
Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, and Srikanth Srinivasan. “A Tail Bound for Read-kFamilies of Functions”. In:Random Structures & Algorithms47.1 (2015), pp. 99 –108.doi:10.1002/rsa.20532.url:https://doi.org/10.1002/rsa.20532(cit. on p. 40). 24
2015 doi
-
[13]
A new bound in Majority Dynamics on Random Graphs
Sean Jaffe. “A new bound in Majority Dynamics on Random Graphs”. In:arXiv preprint arXiv:2503.14401(2025) (cit. on p. 10)
2025 arXiv
-
[14]
A new density limit for unanimity in majority dynamics on random graphs
Jeong Han Kim and BaoLinh Tran. “A new density limit for unanimity in majority dynamics on random graphs”. In:arXiv preprint arXiv:2503.07447(2025) (cit. on p. 10)
2025 arXiv
-
[15]
An approximation theorem for the Poisson binomial distribution
Lucien Le Cam. “An approximation theorem for the Poisson binomial distribution”. In:Pa- cific Journal of Mathematics10.4 (1960), pp. 1181–1197.doi:10.2140/pjm.1960.10.1181 (cit. on p. 26)
1960 doi
-
[16]
Testing thresholds for high-dimensional sparse random geometric graphs
Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang. “Testing thresholds for high-dimensional sparse random geometric graphs”. In:Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022, pp. 672–677 (cit. on p. 23)
2022
-
[17]
Opinion exchange dynamics
Elchanan Mossel and Omer Tamuz. “Opinion exchange dynamics”. In:Probability Surveys 14 (2017), pp. 155–204 (cit. on p. 3)
2017
-
[18]
A model of opinion dynamics evolving via a preferential attachment mechanism involving multiple extractions
Sooraj M Moumanti Podder and Archi Roy. “A model of opinion dynamics evolving via a preferential attachment mechanism involving multiple extractions”. In: (2026). arXiv:2608. 01419 [math.PR].url:https://arxiv.org/abs/2608.01419(cit. on pp. 11, 23)
2026 arXiv
-
[19]
Majority dynamics: The power of one
Ashwin Sah and Mehtaab Sawhney. “Majority dynamics: The power of one”. In:Israel Journal of Mathematics(2024), pp. 1–49 (cit. on pp. 3, 10)
2024
-
[20]
Le Cam’s Inequality and Poisson Approximations
J. Michael Steele. “Le Cam’s Inequality and Poisson Approximations”. In:The American Mathematical Monthly101.1 (1994), pp. 48–54 (cit. on p. 26)
1994
-
[21]
The “Power of Few
BaoLinh Tran and Van Vu. “The “Power of Few” Phenomenon: The Sparse Case”. In:Random Structures & Algorithms66.1 (2025), e21260 (cit. on pp. 1, 3, 10)
2025
-
[22]
Reaching a Consensus on Random Networks: The Power of Few
Linh Tran and Van Vu. “Reaching a Consensus on Random Networks: The Power of Few”. In:Theory of Computing19.6 (2023), pp. 1–21.doi:10.4086/toc.2023.v019a006.url: https://theoryofcomputing.org/articles/v019a006(cit. on pp. 3, 10)
2023 doi
-
[23]
Consensus on dynamic stochastic block models: Fast convergence and phase transitions
Haoyu Wang, Jiaheng Wei, and Zhenyuan Zhang. “Consensus on dynamic stochastic block models: Fast convergence and phase transitions”. In: (2022). arXiv:2209.03999 [math.PR]. url:https://arxiv.org/abs/2209.03999(cit. on p. 11)
2022 arXiv
-
[24]
Opinion forming in Erd˝ os–R´ enyi random graph and expanders
Ahad N Zehmakan. “Opinion forming in Erd˝ os–R´ enyi random graph and expanders”. In: Discrete Applied Mathematics277 (2020), pp. 280–290 (cit. on p. 10)
2020
-
[25]
Clus- tering in co-evolving opinion dynamics: reduced SPDE models
Sebastian Zimper, Nataˇ sa Djurdjevac Conrad, Federico Cornalba, and Ana Djurdjevac. “Clus- tering in co-evolving opinion dynamics: reduced SPDE models”. In:arXiv preprint 2604.27961 (2026) (cit. on pp. 11, 23). 25 A Continuity-Corrected Gaussian Estimates Via Poisson Approx- ...
2026 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.