18.05.2026 16:30 Alan Sergeev:
Majority Dynamics on GraphsB 252 (Theresienstr. 39, 80333 Theresienstr. 39)

Given a simple graph G = (V, E) and a map l0 : V → {+1, −1}, the majority dynamics on G with initial assignment of states l0 is a process that begins on day 0, and for each t ≥ 0 produces a new assignment of states lt+1 where each vertex takes the state of the majority of its neighbours, and remains at its previous state in the case of a tie. Specifically, for each v ∈ V , lt+1(v) = ( +1 if P u∈N (v) lt(u) > 0, or P u∈N (v) lt(u) = 0 and lt(v) = +1, −1 otherwise. (1) This process is a model for opinion exchange dynamics, with applications in many areas, such as politics, sociology, biophysics. While there exist results about the process even- tually reaching a 2-periodic stable state on all graphs, a natural question to study would be under which initial conditions is unanimity reached, and how quickly. When considering the question specifically in the case of Binomial Random Graphs, a longstanding conjecture, due to Benjamini, Chan, O’Donnel, Tamuz and Tan (2016) is the following: Conjecture. Let G ∼ G(n, p) be the binomial random graph with p = ω(1/n) and l0(v) be sampled uniformly at random from {+1, −1} for each v ∈ V . Then w.h.p. the majority dynamics process reaches unanimity after sufficiently many steps t. Steps towards proving the conjecture have been taken taken by gradually improving the range densities d = np for which the conjecture is known to be true, with the current best bound being d ≫ n1/3 log2/3 n due to Kim and Tran. Our work aims to prove the conjecture for the range n1/4 ≪ d ≤ O(n1/3), and lays the groundwork for proving the conjecture in the general case n1/(k+1) ≪ d ≤ O(n1/k). This is based on joint work with Nikolaos Fountoulakis, University of Birmingham.