BROWSE

Related Scientist

chakraborti,debsoumya's photo.

chakraborti,debsoumya
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

Majority dynamics on sparse random graphs

Cited 0 time in webofscience Cited 0 time in scopus
191 Viewed 0 Downloaded
Title
Majority dynamics on sparse random graphs
Author(s)
Debsoumya Chakraborti; Kim, Jeong Han; Lee, Joonkyung; Tran, Tuan
Publication Date
2023-08
Journal
RANDOM STRUCTURES & ALGORITHMS, v.63, no.1, pp.171 - 191
Publisher
WILEY
Abstract
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 & oacute;s-R & eacute;nyi random graph G(n,p), the random initial +/- 1-assignment converges to a 99%-agreement with high probability whenever p = w(1/n). This conjecture was first confirmed for p > lambda n(-1/2) for a large constant A 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 < lambda n(-1/2) . We break this omega(n(-1/2))-barrier by proving the conjecture for sparser random graphs G(n,p), where lambda ' n(-3/5) log n < p < lambda n(-1/2) with a large constant A ' > 0.
URI
https://pr.ibs.re.kr/handle/8788114/13567
DOI
10.1002/rsa.21139
ISSN
1042-9832
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse