Best-of-Three Voting on Dense Graphs

Abstract

Given a graph G of n vertices, where each vertex is initially attached an opinion of either red or blue. We investigate a random process known as the Best-of-three voting. In this process, at each time step, every vertex chooses three neighbours at random and adopts the majority colour. We study this process for a class of graphs with minimum degree d = nα, where α = Ømega((łog łog n)-1). We prove that if initially each vertex is red with probability greater than $1/2+δ, and blue otherwise, where δ ≥ (łog d)-C for some C>0, then with high probability this dynamic reaches a final state where all vertices are red within O(łog łog n) + O(łog(δ-1)) steps.