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

Research output: Contribution to journalArticlepeer-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 journalArticlepeer-review

Harvard

APA

Vancouver

Author

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 -