Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

Research output: Contribution to journal › Article › peer-review

Standard

Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs. / Fountoulakis, Nikolaos; Kang, Mihyun; Makai, Tamas.

In: Random Structures and Algorithms, 10.07.2020.

Research output: Contribution to journal › Article › peer-review

Harvard

Fountoulakis, N, Kang, M & Makai, T 2020, 'Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs', Random Structures and Algorithms. https://doi.org/10.1002/rsa.20970

APA

Fountoulakis, N., Kang, M., & Makai, T. (2020). Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs. Random Structures and Algorithms. https://doi.org/10.1002/rsa.20970

Vancouver

Fountoulakis N, Kang M, Makai T. Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs. Random Structures and Algorithms. 2020 Jul 10. https://doi.org/10.1002/rsa.20970

Author

Fountoulakis, Nikolaos ; Kang, Mihyun ; Makai, Tamas. / Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs. In: Random Structures and Algorithms. 2020.

Bibtex

@article{cba4a1971cdc42ee80176e617ec994ab,
title = "Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs",
abstract = "We study majority dynamics on the binomial random graph G(n,p) with p = d/n and d > c n^{1/2}, for some large c>0. In this process, each vertex has a state in {-1,+1 } and at each round every vertex adopts the state of the majority of its neighbours, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini, Chan, O'Donnel, Tamuz and Tan. ",
keywords = "majority dynamics, random graphs, unanimity",
author = "Nikolaos Fountoulakis and Mihyun Kang and Tamas Makai",
year = "2020",
month = jul,
day = "10",
doi = "10.1002/rsa.20970",
language = "English",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "Wiley",

}

RIS

TY - JOUR

T1 - Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

AU - Fountoulakis, Nikolaos

AU - Kang, Mihyun

AU - Makai, Tamas

PY - 2020/7/10

Y1 - 2020/7/10

N2 - We study majority dynamics on the binomial random graph G(n,p) with p = d/n and d > c n^{1/2}, for some large c>0. In this process, each vertex has a state in {-1,+1 } and at each round every vertex adopts the state of the majority of its neighbours, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini, Chan, O'Donnel, Tamuz and Tan.

AB - We study majority dynamics on the binomial random graph G(n,p) with p = d/n and d > c n^{1/2}, for some large c>0. In this process, each vertex has a state in {-1,+1 } and at each round every vertex adopts the state of the majority of its neighbours, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini, Chan, O'Donnel, Tamuz and Tan.

KW - majority dynamics

KW - random graphs

KW - unanimity

U2 - 10.1002/rsa.20970

DO - 10.1002/rsa.20970

M3 - Article

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

ER -