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 = na, where a = Q ((log log n)-1). We prove that if initially each vertex is red with probability greater than 1/2 + 8, and blue otherwise, where 8 > (log d) -c for some C > 0, then with high probability this dynamic reaches a final state where all vertices are red within 0 (log log n) + 0 (log (6-1) steps.