Wednesday, October 5, 2022
Time | Items |
---|---|
All day |
|
4:00pm |
10/05/2022 - 4:15pm Majority dynamics on a graph G is a deterministic process such that every vertex updates its ±1-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erd˝os–R´enyi random graph G(n, 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 ≥ λn−1/2 for a large constant λ 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 for p < λn−1/2 . We break this Ω(n −1/2 )-barrier by proving the conjecture for sparser random graphs G(n, p) with λn − 2/3 log2/3 n ≤ p ≤ λn − 1/2 for a large constant λ > 0. Joint work with D. Chakraborti, J. Lee, & T. Tran, and with L. Tran. Location:
LOM 206
|