Majority dynamics on finite trees

Georgii Zakharov; Itai Benjamini; Maksim Zhukovskii

REVIEW 2 major objections 4 minor 12 references

Majority dynamics on finite trees

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For any finite tree with odd degrees, the worst-case majority-dynamics stabilisation time equals the length of the longest active path, with one extra step when that path ends at a leaf.

desk verdict The exact worst-case result is clean and solid; the average-case upper bound has a genuine gap in Claim 4.14 that needs repair before Theorem 1.2 is fully proven. read the letter →

arxiv 2507.04714 v1 pith:K3AOUNUU submitted 2025-07-07 math.CO math.PR

Itai Benjamini , Georgii Zakharov , Maksim Zhukovskii This is my paper · ORCID

classification math.COmath.PR MSC 05C0505C8060C05

keywords majoritydynamicsfinitetreesworst-casestabilisationtimeperfectbinaryrandominitialopinionsweakstabilitystrongactivepaths

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how long majority dynamics—each vertex repeatedly adopting the opinion most of its neighbours currently hold—can take to settle on a finite tree. It gives an exact answer for the worst-case initial opinions on any tree with odd degrees: the stabilisation time is the length of the longest 'active' path, plus one extra step if that path ends at a leaf. In a perfect binary tree of diameter $D$, this worst-case time is exactly $D-3$, while for uniformly random initial opinions the process still takes linear time, between $D/4$ and $D/3$ with high probability. These results replace loose general bounds with a precise structural rule for trees.

What carries the argument

The carrying object is a classification of vertices by the number of leaf-neighbours. A vertex is active when fewer than $(\deg_T(v)-1)/2$ of its neighbours are leaves, balky when equality holds, and passive otherwise. Active vertices are the only ones that can transmit an opinion along a non-leaf path, and the maximum length of a directed path of active vertices, plus one for an end touching a leaf, gives $\tau(T)$ exactly. For random initial opinions, the proof uses two stability notions defined by the initial opinions inside a vertex's descendant subtree: strong $t$-stability, in which the vertex keeps its opinion for every outside configuration, and weak $t$-stability, in which some outside configuration locks it. The random upper bound is finished by a union bound over paths whose count is controlled by an external estimate on long paths in a perfect binary tree.

What would settle it

Count all paths of length $d=\lfloor 2h/3\rfloor$ in a perfect binary tree of height $h$; if for some sequence of $h$ this count exceeds $C\cdot 2^{h+d/2}$ for every constant $C$, the union bound in Lemma 4.8 collapses and the whp upper bound of Theorem 1.2 would need a different proof.

Watch

Extended reading notes

Core claim

Theorem 1.1 states that for every finite tree $T$ with all degrees odd and $|V(T)|\ge 5$, $\tau(T)=\max_{Q\in\mathcal{Q}} t(Q)$, where $\mathcal{Q}$ collects paths whose non-final vertices have fewer than $(\deg_T(v)-1)/2$ leaf-neighbours and whose final vertex has at most that many. The value $t(Q)$ is $|V(Q)|$, plus $1$ if the final vertex is adjacent to a leaf. For perfect trees of diameter $D$, this gives $\tau(T)=D-3$. The paper also proves that with uniformly random initial opinions on a perfect binary tree of diameter $D$, the stabilisation time lies between $c_-D$ and $c_+D$ with high probability for some $c_->1/4$ and $c_+<1/3$, and that for perfect $k$-ary trees with even $k\ge 4$ the time is whp at least a constant times $D^{1/2}(\log k/k)^{1/2}$ and at most $D-3$.

Load-bearing premise

The random-tree upper bound leans on the quoted estimate that a perfect binary tree of height $h$ contains at most about $C\cdot 2^{h+d/2}$ paths of length $d$; if that estimate is too small by an exponential factor, the union bound over long paths fails.

Editorial extensions

If this is right

For any odd-degree tree, $\tau(T)$ can be read off from the vertex classification, so finding the worst-case stabilisation time becomes a longest-path computation rather than a search over all $2^n$ initial opinion vectors.
Perfect trees of diameter $D$ always have worst-case stabilisation time $D-3$, so the earlier general bound $|E(T)|-|V(T)|/2$ is not tight for trees.
On a perfect binary tree with random opinions, stabilisation time is whp linear in the diameter, between $D/4$ and $D/3$; randomness does not push the time below linear.
On perfect $k$-ary trees with even $k\ge 4$, random stabilisation time is whp at least a constant multiple of $\sqrt{(\ln k)/k}\sqrt{D}$, and the true order is left open.
For the infinite 3-regular tree with iid uniform opinions, Claim 1.4 follows: with probability exceeding $1/2$, a fixed root's opinion at even times equals its initial opinion forever.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Not pursued in the paper: Theorem 1.1 reduces worst-case time to a longest-path problem on the active subgraph, so $\tau(T)$ can be computed in near-linear time by pruning leaf counts.
If the external path-count bound used for the random upper bound is close to sharp, lowering the constant $c_+$ below $1/3$ would require a new concentration argument rather than merely a sharper count.
The active/balky dichotomy may extend to odd-degree graphs with a bounded number of cycles, replacing 'leaf-neighbour' by 'neighbour in a dead-end branch'; this extension is not established in the paper.
Simulating exact stabilisation times on perfect binary trees up to moderate heights could bracket the constant $c$ that the authors suspect $\tau/D$ converges to inside $(1/4,1/3)$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The punchline: the worst-case result is the real thing and it holds up; the average-case upper bound has a genuine gap that needs repair before Theorem 1.2 is fully proven.

What is new: Theorem 1.1 gives an exact formula for the worst-case stabilization time on any finite odd-degree tree, stated in terms of paths with leaf-neighbor constraints, with the corollary for perfect trees. The proof via the active/balky/passive classification is complete and convincing. The lower-bound construction is explicit and checks out. This alone is a solid, citable contribution.

The paper also introduces strong and weak stability, uses them to prove lower bounds for random initial opinions on perfect binary trees, and proves a weaker lower bound for k-ary trees. Those parts read as genuinely new, and the lower-bound arguments appear sound.

The soft spot: the stress-test is right. In Claim 4.14, the proof wants to conclude that two weakly (s−2)-stable grandchildren of v make v strongly s-stable with opinion −1. But weak stability is an existential property: it says there exists an extension under which the vertex is stable. Claim 4.3 and Claim 4.11 only give stability within a fixed process, not for every extension. Strong stability requires exactly the universal quantification, and that is not delivered. So the lower bound on P(Q2 | ...) is not justified. Since Lemma 4.8 uses that bound through inequality (9) to get the constant below 1/3, the upper bound in Theorem 1.2 is unproven as written. This is a load-bearing step for that theorem, not a cosmetic gap. I do not see a similar problem in the lower-bound sections or in Theorem 1.1.

The reliance on the external path-count bound from [4] is fine; it is a standard cited bound and not the issue.

Who this is for: anyone working on majority dynamics or discrete dynamical systems. Theorem 1.1 is a neat exact result worth having.

Recommendation: send it to peer review. The authors need to either fix Claim 4.14 or find another route to the upper bound. If the gap cannot be closed, the paper still deserves publication for Theorem 1.1, with Theorem 1.2's upper bound reported as a conjecture. But as it stands, that upper bound should not be stated as proven.

Referee Report

2 major / 4 minor

Summary. The paper studies majority dynamics on finite trees with all vertex degrees odd. Theorem 1.1 gives an exact formula for the worst-case stabilization time in terms of the longest admissible path of 'active' vertices. Thematic results for average-case dynamics are then proved for perfect binary trees (Theorems 1.2, linear stabilization with high probability) and for perfect k-ary trees (Theorem 1.3, a square-root lower bound). The proof of the worst-case theorem is constructive and self-contained. The average-case lower bound for binary trees uses a new notion of strong stability, and the upper bound uses weak stability together with a union bound over travel paths. The main concern in this report is the proof of Claim 4.14, which is load-bearing for the upper bound in Theorem 1.2.

Significance. If the results are correct, Theorem 1.1 is a clean and nontrivial exact characterization of worst-case majority dynamics on trees, and Theorem 1.2 provides the first average-case linear bounds for perfect binary trees with explicit constants. The paper introduces useful stability notions and contains detailed, non-circular probability estimates; constants are chosen to satisfy inequalities rather than fitted to the conclusions. However, the upper-bound proof for Theorem 1.2 has a genuine gap in Claim 4.14, and the result therefore cannot currently be regarded as established.

major comments (2)

[Claim 4.14] The lower bound P(Q2 | {τ = s} ∧ Q1) ≥ 0.5(1 − (1 − pw(0))^2)^2 is not justified. The proof derives weak (s−2)-stability of the grandchildren of v via Claim 4.10, but weak stability only asserts the existence of one extension of ξ0|V(Tv) that makes a vertex 0-stable; it does not quantify over all extensions. Claims 4.3 and 4.11 act inside a fixed process and do not upgrade weak stability to stability for every extension, which is exactly what Q2 requires. The sentence 'if at least two non-sibling grandchildren of v are (s−2)-stable, then v is strongly s-stable, by Claim 4.3 and Claim 4.11' is therefore unsupported. This estimate feeds through inequality (9) and the union bound into the choice of c_+ < 2/3 in Lemma 4.8, so the upper bound of Theorem 1.2 is not proven.
[Lemma 4.8] The union bound in Lemma 4.8 relies on the external path-count estimate 2^{h+d/2}·C1 from [4, Lemma 5.7]. Because the margin in inequality (8) is narrow, the manuscript should state the exact form of this bound or give a self-contained derivation for perfect binary trees. As written, the validity of (8) is imported without supporting detail.

minor comments (4)

[Abstract] The abstract contains a typo: 'wort-case' should be 'worst-case'.
[Claim 4.14] In the final sentence of Claim 4.14, 'the probability ... is at least' should read 'is at most': the proof bounds an upper tail and the displayed expression is an upper bound, not a lower bound.
[Proof of (9)] In the paragraph bounding q2, the text says 'a fixed vertex u ∈ Ui is weakly 0-stable'; the context and the application of Claim 4.14 require 'is not weakly 0-stable'.
[Throughout] Minor grammatical issues include 'less then' for 'less than' and a few sentence fragments; these do not affect the mathematics.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's derivations are self-contained; the flagged Claim 4.14 issue is a proof gap, not a circular reduction.

full rationale

The paper's worst-case result (Theorem 1.1) is derived from explicit path-switching arguments: Claim 3.2 gives the upper bound by showing that a change at an active vertex forces a long path of active vertices, and Claim 3.3 constructs initial opinions realizing the lower bound. The quantity t(Q) is not fitted to tau(T) but is shown by independent upper and lower bound constructions. The average-case lower bound (Lemma 4.7) uses freshly defined strong-stability events whose probabilities are computed directly in Claim 4.6; no parameter is calibrated to the target stabilization time. The average-case upper bound (Lemma 4.8) uses a union bound over paths, with per-path probability estimates obtained from the authors' Claims 4.13 and 4.14 and independent subsets of vertices; the only external input is a path-counting bound from [4], which is not authored by the present authors and does not encode the stabilization-time conclusion. The citation to [2], which includes a co-author of the present paper, is used only as background and refinement context, not as justification of any central claim. The possible gap flagged in Claim 4.14, concerning the upgrade from weak stability of descendants to strong s-stability of v via Claim 4.3 and Claim 4.11, is a mathematical correctness concern rather than circularity: it does not reduce the claim to its own assumptions, to a fitted parameter, or to a self-citation chain. Thus no circular step is present, and the derivation is self-contained apart from the genuinely external counting bound.

Assumptions & free parameters 4 free parameters · 3 assumptions · 0 invented entities

The paper introduces no fitted parameters or invented entities; constants c_-, c_+, p_+, p_- are chosen in the proof to satisfy inequalities, not fitted to data. It relies on standard background results: the Goles-Olivos period-two theorem, the odd-degree domain assumption, and an external path-count bound.

free parameters (4)

c_- = >1/4 (exists)
Existential lower-bound constant in Theorem 1.2; chosen in Lemma 4.7 to satisfy 0.25003h < d < (log2(4/0.2501))^{-1} h. Not fitted to data.
c_+ = <1/3 relative to D (exists)
Existential upper-bound constant; chosen so that the union bound (8) is o(1). Not fitted to data.
p_+ = 0.01
Chosen for the path-probability bound in Lemma 4.8; no data involved.
p_- = 0.0513
Chosen similarly to p_+; no data involved.

assumptions (3)

standard math Goles-Olivos period-two theorem
Cited as [6]; used to justify the definition of stabilization time as the onset of period-two behavior.
domain assumption All vertices of considered trees have odd degree
Stated in the introduction; avoids ties in the majority rule and is essential for Claim 3.1 and Claim 3.2.
standard math Path-count bound from [4, Lemma 5.7]
External combinatorial bound used in the union bound for Lemma 4.8; not proved in the paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Majority dynamics on finite trees." pith.science (2026). https://pith.science/paper/K3AOUNUU

@misc{pith2026250704714,
  author       = {Pith},
  title        = {Pith review of: Majority dynamics on finite trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K3AOUNUU}},
  note         = {Machine review of arXiv:2507.04714}
}

abstract

For an arbitrary finite tree $T$, we find the exact value of the wort-case stabilisation time of majority dynamics on $T$. We also prove that for a perfect rooted cubic tree $T$ with diameter $D$ and uniformly random initial opinions, the dynamics stabilises in time $\tau\in(D/4,D/3)$ with high probability.

Figures

Figures reproduced from arXiv: 2507.04714 by the authors.

**Figure 1.** Structure of the tree T ∗ . 2. there exists a path P4 ⊂ Tv4 from v4 to some vertex u4 at distance 2 from a leaf such that • ξ ∗ 0 (v) = 1 for every v ∈ V (P4) at even distance from a leaf; • E(u) holds for the child u /∈ V (P4) of every vertex v ∈ V (P4) \ {u4}; • ξ ∗ 0 (u) = −1 for all grandchildren u of u4. 3. there exists a path P5 ⊂ Tv5 from v5 to some vertex u5 at distance 2 from a leaf such that • ξ ∗ 0 (v) = … view at source ↗

**Figure 2.** The structure of sets Ai and Ui We denote the number of vertices u ∈ V (P) at even distance from v0 such that ξ0(u) equals 1 and −1 by m+ and m−, respectively. Fix an even i ∈ [d−4] such that Ai ∈ I. Denote the number of vertices u ∈ {vi , vi+2} such that ξ0(u) equals 1 and −1 by k+(i) and k−(i), respectively. Let the random variable Ξi := Ξi(ξ0|V (P)) be the set of vectors of initial opinions of vertices from Ai su… view at source ↗

**Figure 3.** Descendants of u The required condition that D is defined by ξ0|V (Tu1 )\{u1} and the inequality P(D) ≥ 1 − 1 − 1 − q 2 t−4 4 2 are immediate. Now, suppose that Cj ∩ D holds. We have to derive the weak 0-stability of u. Let us recall that ξ0(u) = ξ0(u2) = ˆξ, so ξ1(v1) = ˆξ as u, u2 are neighbours of v1. In addition, at time 1, the parent z1 of w1 and w2 holds the opinion ˆξ. Since u1 is adjacent to z1 and to v1,… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[4]

J. V. de Jong, J. C. McLeod, and M. Steel. Neighborhoods of phylogenetic trees: exact and asymptotic counts. SIAM J. Discrete Math. , 30(4):2265–2287, 2016

work page 2016
[1]

Alistarh, J

D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 2560–2579. SIAM, 2017

work page 2017
[2]

Benjamini, S.-O

I. Benjamini, S.-O. Chan, R. O’Donnell, O. Tamuz, and L.-Y. Tan. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Processes and their Applications , 126(9):2719–2733, 2016

work page 2016
[3]

Chakraborti, J

D. Chakraborti, J. H. Kim, L. Joonkyung, and T. Tran. Majority dynamics on sparse random graphs. Random Structures & Algorithms , 63:171–191, 2023

work page 2023
[5]

Fountoulakis, M

N. Fountoulakis, M. Kang, and T. Makai. Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs. Random Structures & Algorithms, 57:1134–1156, 2020

work page 2020
[6]

Goles and J

E. Goles and J. Olivos. Periodic behaviour of generalised threshold functions. Discrete Math- ematics, 30:187–189, 1980

work page 1980
[7]

W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biology , 52(1–2):99–115, 1990

work page 1990
[8]

Mossel and O

E. Mossel and O. Tamuz. Opinion exchange dynamics. Probability Surveys, 14:155–204, 2017

work page 2017

Show all 12 references

[9]

Poljak and D

S. Poljak and D. Turz ´ ık. On pre-periods of discrete influence systems. Discrete Applied Mathematics, 13(1):33–39, 1986

1986
[10]

Tamuz and R

O. Tamuz and R. J. Tessler. Majority dynamics and the retention of information. Israel Journal of Mathematics , 206:483–507, 2015

2015
[11]

X. Yin, H. Wang, P. Yin, and H. Zhu. Agent-based opinion formation modeling in social network: A perspective of social psychology. Physica A: Statistical Mechanics and its Appli- cations, 532:121786, 2019

2019
[12]

A. N. Zehmakan. Random majority opinion diffusion: Stabilization time, absorbing states, and influential nodes. Proc. of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023) , pages 2179–2187, 2023. 41

2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [4]

J. V. de Jong, J. C. McLeod, and M. Steel. Neighborhoods of phylogenetic trees: exact and asymptotic counts. SIAM J. Discrete Math. , 30(4):2265–2287, 2016

work page 2016

[2] [1]

Alistarh, J

D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 2560–2579. SIAM, 2017

work page 2017

[3] [2]

Benjamini, S.-O

I. Benjamini, S.-O. Chan, R. O’Donnell, O. Tamuz, and L.-Y. Tan. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Processes and their Applications , 126(9):2719–2733, 2016

work page 2016

[4] [3]

Chakraborti, J

D. Chakraborti, J. H. Kim, L. Joonkyung, and T. Tran. Majority dynamics on sparse random graphs. Random Structures & Algorithms , 63:171–191, 2023

work page 2023

[5] [5]

Fountoulakis, M

N. Fountoulakis, M. Kang, and T. Makai. Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs. Random Structures & Algorithms, 57:1134–1156, 2020

work page 2020

[6] [6]

Goles and J

E. Goles and J. Olivos. Periodic behaviour of generalised threshold functions. Discrete Math- ematics, 30:187–189, 1980

work page 1980

[7] [7]

W. S. McCulloch and W. Pitts. A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biology , 52(1–2):99–115, 1990

work page 1990

[8] [8]

Mossel and O

E. Mossel and O. Tamuz. Opinion exchange dynamics. Probability Surveys, 14:155–204, 2017

work page 2017