TY - UNPB
T1 - Majority Model on Random Regular Graphs
AU - Gärtner, Bernd
AU - Zehmakan, Ahad N.
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2017
Y1 - 2017
N2 - Consider a graph G = (V,E) and an initial random coloring where each vertex v ∈ V is blue with probability Pb and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random d-regular graph Gn,d. It is shown that for all ǫ > 0, Pb ≤ 1/2 −ǫ results in final complete occupancy by red in O(logd logn) rounds with high probability, provided that d ≥ c/ǫ2 for a suitable constant c. Furthermore, we show that with high probability, Gn,d is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can “take over” in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg [21].
AB - Consider a graph G = (V,E) and an initial random coloring where each vertex v ∈ V is blue with probability Pb and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. The main goal of the present paper is to analyze the behavior of this basic and natural process on the random d-regular graph Gn,d. It is shown that for all ǫ > 0, Pb ≤ 1/2 −ǫ results in final complete occupancy by red in O(logd logn) rounds with high probability, provided that d ≥ c/ǫ2 for a suitable constant c. Furthermore, we show that with high probability, Gn,d is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can “take over” in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg [21].
M3 - Working paper
BT - Majority Model on Random Regular Graphs
ER -