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.

This is a seminar of the Combinatorial Mathematics Society of Australasia. To attend email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]