Global majority consensus by local majority polling on graphs of a given degree sequence

Suppose in a graph GG vertices can be either red or blue. Let kk be odd. At each time step, each vertex vv in GG polls kk random neighbours and takes the majority colour. If it does not have kk neighbours, it simply polls all of them, or all less one if the degree of vv is even. We study this protocol on graphs of a given degree sequence, in the following setting: initially each vertex of GG is red independently with probability α<12, and is otherwise blue. We show that if αα is sufficiently biased, then with high probability consensus is reached on the initial global majority within O(logklogkn)O(logklogkn) steps if 5≤k≤d5≤k≤d, and O(logdlogdn)O(logdlogdn) steps if k>dk>d. Here, d≥5d≥5 is the effective minimum degree, the smallest integer which occurs Θ(n)Θ(n) times in the degree sequence. We further show that on such graphs, any local protocol in which a vertex does not change colour if all its neighbours have that same colour, takes time at least Ω(logdlogdn)Ω(logdlogdn), with high probability. Additionally, we demonstrate how the technique for the above sparse graphs can be applied in a straightforward manner to get bounds for the Erdős–Rényi random graphs in the connected regime.