论文标题
多数动态的中央限制定理：贿赂三个选民就足够了
Central Limit Theorem for Majority Dynamics: Bribing Three Voters Suffices
论文作者
论文摘要
Given a graph $G$ and some initial labelling $σ: V(G) \to \{Red, Blue\}$ of its vertices, the \textit{majority dynamics model} is the deterministic process where at each stage, every vertex simultaneously replaces its label with the majority label among its neighbors (remaining unchanged in the case of a tie).我们证明---对于广泛的参数---如果初始分配是固定的，并且我们独立采样了erdős--rényi随机图，$ g_ {n，p} $，则在多数动态的一步之后，每个标签的顶点数量遵循了中心限制定律。作为推论，我们提供了Benjamini，Chan，O'Donnell，Tamuz和Tan定理的加强，内容涉及该过程所需的步骤数量，即当也随机选择初始分配时，该过程达到一致性所需的步骤。此外，假设最初比蓝色多三个红色顶点。在这种情况下，我们证明，如果我们独立采样了图$ g_ {n，1/2} $，则概率至少$ 51 \％$，大多数动态过程将收敛到每个顶点是红色的。这改善了Tran和Vu的结果，他们解决了初始铅至少10个案例。
Given a graph $G$ and some initial labelling $σ: V(G) \to \{Red, Blue\}$ of its vertices, the \textit{majority dynamics model} is the deterministic process where at each stage, every vertex simultaneously replaces its label with the majority label among its neighbors (remaining unchanged in the case of a tie). We prove---for a wide range of parameters---that if an initial assignment is fixed and we independently sample an Erdős--Rényi random graph, $G_{n,p}$, then after one step of majority dynamics, the number of vertices of each label follows a central limit law. As a corollary, we provide a strengthening of a theorem of Benjamini, Chan, O'Donnell, Tamuz, and Tan about the number of steps required for the process to reach unanimity when the initial assignment is also chosen randomly. Moreover, suppose there are initially three more red vertices than blue. In this setting, we prove that if we independently sample the graph $G_{n,1/2}$, then with probability at least $51\%$, the majority dynamics process will converge to every vertex being red. This improves a result of Tran and Vu who addressed the case that the initial lead is at least 10.
