Majority dynamics on random graphs: The multiple states case

We study the evolution of majority dynamics with more than two states on the binomial random graph G(n,p). In this process, each vertex has a state in {1,..., k}, with k ≥ 2, and at each round every vertex adopts state i if it has more neighbours in state i than in any other state. Ties are resolved randomly. We show that with high probability the process reaches unanimity in at most three rounds, if np>> n^2/3.