论文标题
快速收敛到密集的Erdős-rényi图中的一致性
Fast Convergence to Unanimity in Dense Erdős-Rényi Graphs
论文作者
论文摘要
研究了二项式Erdős-rényi图$ \ Mathsf {g}（n，p）$的多数动力学，并研究了$ p =λ/\ sqrt {n} $。在此过程中，每个顶点在$ \ {0,1 \} $中都有一个状态，并且在每个回合中，每个顶点都采用大多数邻居的状态，并在平局的情况下保留其状态。它由Benjamini等人猜想。并由Fountoulakis等人证明。这个过程在最多四轮比赛中具有很高的可能性。通过添加一些额外的随机性，并允许在每个通信中重新绘制基础图，我们可以改善它们的结果，并证明此过程仅在仅在三个通信中达成共识，而概率却接近$ 1 $，因为$ n $ a $ a $ a $生长到无限。我们还提供了相反的结果，表明三轮不仅足够，而且还必须必要。
Majority dynamics on the binomial Erdős-Rényi graph $\mathsf{G}(n,p)$ with $p=λ/\sqrt{n}$ 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.
