Majority dynamics in the dense binomial random graph

Abstract: Majority dynamics is a deterministic process on a graph which evolves in the following manner. Initially every vertex is coloured either red or blue. In each step of the process every vertex adopts the colour of the majority of its neighbours, or retains its colour if no majority exists. We analyse the behaviour of this process in the dense binomial random graph when the initial colour of every vertex is chosen independently and uniformly at random. We show that with high probability the process reaches complete unanimity, partially proving a conjecture of Benjamini, Chan, O'Donnel, Tamuz and Tan. This is joint work with N. Fountoulakis and M. Kang.

discrete mathematicscombinatoricsprobability

Audience: researchers in the discipline

Australasian Combinatorics Seminar

Series comments: Please note that we vary between 5pm and 11am (AEST) time slots