King's College London

Research portal

Threshold behaviour of discordant voting on the complete graph

Research output: Contribution to journalArticle

Original languageEnglish
JournalJournal of Discrete Algorithms
Early online date12 Oct 2018
StateE-pub ahead of print - 12 Oct 2018

King's Authors


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 β vertex u adopts the colour of vertex v and with probability 1−β vertex v adopts the colour of vertex u. Let T be the number of steps needed to reach consensus. For the complete graph Kn with an initial colouring where half the vertices are red and half blue, then when β=0, ET=Θ(nlog⁡n), whereas when β=1 then ET=Θ(2n). The case β=1/2 corresponds to a simple random walk on a path with vertex set {0,1,...,n} and has ET=n2/4. We study the effect of varying β from zero to one, thus revealing the detailed transition from ET=Θ(nlog⁡n) to ET=Θ(2n). In terms of β, the transition from Θ(nlog⁡n) to Θ(n2) occurs in a scaling window of width O(1/n) around β=1/2. For any a>1, there is an explicit value of β=1/2+O(log⁡n/n) for which ET=Θ(na). When β>1/2 constant, there is an explicit value a(β) such that ET=Θ(an).

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454