Majority dynamics on finite trees
Majority dynamics on finite trees
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 $Ï\in(D/4,D/3)$ with high probability.
Itai Benjamini、Georgii Zakharov、Maksim Zhukovskii
数学
Itai Benjamini,Georgii Zakharov,Maksim Zhukovskii.Majority dynamics on finite trees[EB/OL].(2025-07-07)[2025-07-16].https://arxiv.org/abs/2507.04714.点此复制
评论