Research output: Contribution to journal › Article

Original language | English |
---|---|

Journal | Journal of Discrete Algorithms |

Early online date | 12 Oct 2018 |

DOIs | |

Publication status | E-pub ahead of print - 12 Oct 2018 |

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=Θ(nlogn), 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=Θ(nlogn) to ET=Θ(2n). In terms of β, the transition from Θ(nlogn) 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(logn/n) for which ET=Θ(na). When β>1/2 constant, there is an explicit value a(β) such that ET=Θ(an).

King's College London - Homepage

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