Abstract

Given a connected graph G whose vertices are coloured in some way, a discordant voting process on G is as follows. At each step a pair of adjacent vertices with different colours interact, and one of the vertices changes its colour to match the other one. If eventually all vertices have the same colour, we say a consensus has been reached. A vertex is discordant if it has a discordant edge, i.e. a neighbour of a different colour. In the general discordant voting process, at each step a discordant vertex u is chosen uniformly at random, and then a discordant edge (u, v) is chosen from among the discordant edges of u, also uniformly at random. With probability beta vertex u adopts the colour of vertex v and with probability 1 - beta vertex v adopts the colour of vertex u. Let T be the number of steps needed to reach consensus. For the complete graph K-n with an initial colouring where half the vertices are red and half blue, then when beta = 0, ET = circle dot(n logn), whereas when beta = 1 then ET = circle dot(2(n)). The case beta = 1/2 corresponds to a simple random walk on a path with vertex set {0, 1,...,n} and has ET = n(2) / 4. We study the effect of varying beta from zero to one, thus revealing the detailed transition from ET = circle dot(n logn) to ET = circle dot(2(n)). In terms of beta, the transition from circle dot(n logn) to circle dot(n(2)) occurs in a scaling window of width O(1/n) around beta = 1/2. For any a > 1, there is an explicit value of beta = 1/2 + O(logn/n) for which ET = circle dot(n(a)). When beta > 1/2 constant, there is an explicit value a(beta) such that ET = circle dot(a(n)). (C) 2018 Elsevier B.V. All rights reserved.