Fast Convergence to Unanimity in Dense Erd\H{o}s-R\'enyi Graphs

MaRDI QIDQ6413664zbMATH OpenFDO

Authors Ran Tamir

Publication date 12 October 2022

Abstract: Majority dynamics on the binomial ErdH{o}s-R'enyi graph $mathsfG(n,p)$ with $p=lambda/sqrtn$ is studied. In this process, each vertex has a state in $0,1$ and at each round, every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. It was conjectured by Benjamini et al. and proved by Fountoulakis et al. that this process reaches unanimity with high probability in at most four rounds. By adding some extra randomness and allowing the underlying graph to be drawn anew in each communication round, we improve on their result and prove that this process reaches consensus in only three communication rounds with probability approaching $1$ as $n$ grows to infinity. We also provide a converse result, showing that three rounds are not only sufficient, but also necessary.

This page was built for publication: Fast Convergence to Unanimity in Dense Erd\H{o}s-R\'enyi Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413664)