Majority Dynamics on Finite Trees

Random Structures and Algorithms 2026 Open access

Read full text
Authors: Itaï Benjamini, Georgii Zakharov, Maksim Evgen'evich Zhukovskii
DOI: 10.1002/rsa.70092
Cited by: 0

Abstract

ABSTRACT For an arbitrary finite tree , we find the exact value of the worst‐case stabilization time of majority dynamics on . We also prove that for a perfect rooted cubic tree with diameter and uniformly random initial opinions, the dynamics stabilizes in time with high probability.

Fields of Study & Subjects

Advanced Graph Theory Research Game Theory and Applications

Publication details

Journal / source
Random Structures and Algorithms
Volume
69
Issue
2
Publication date
1 September 2026
Language
EN