Majority dynamics on a graph is a deterministic process where every vertex updates its +1- assignment according to the majority assignment on its neighbor simultaneously at each step. This model has been studied in various areas, including combinatorics, psychology, and biophysics, since the 1940s.
We will talk about how majority dynamics behave on the Erdos-Renyi random graph Gn,p, which is a graph on n vertices where each edge appears independently with probability p. Benjamini, Chan, O'Donnell, Tamuz, and Tan conjectured that in the random graph Gn,p, the random initial +1- assignment converges to a 99%-agreement with high probability whenever p>> 1/n.
This conjecture was first confirmed for p>> 1/(n^1/2) by Fountoulakis, Kang, and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds beyond this threshold. We break this 1/(n^1/2) -barrier by proving the conjecture for sparser random graphs G(n,p) with p>>(log n)/(n^3/5). This talk will be based on joint work with Jeong Han Kim, Joonkyung Lee, and Tuan Tran.
Zoom link: https://icts-res-in.zoom.us/j/88150977956?pwd=TjRkR2EzZGRoWm1tUFYyV2VFL1V2Zz09
Meeting ID: 881 5097 7956
Passcode: 313122