skip to main content

Title: Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs

We study majority dynamics on the binomial random graphG(n, p) withp = d/nand, for some large. 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 neighbors, 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 et al.

more » « less
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
Page Range / eLocation ID:
p. 1134-1156
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Letbe the random directed graph onnvertices where each of thepossible arcs is present independently with probabilityp. A celebrated result of Frieze shows that ifthentypically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles inis typically. We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typicallydirected Hamilton cycles.

    more » « less
  2. We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in(n, p) for nearly optimalp(up to afactor). In particular, we show that givent = (1 − o(1))npHamilton cyclesC1,…,Ct, each of which is oriented arbitrarily, a digraph(n, p) w.h.p. contains edge disjoint copies ofC1,…,Ct, provided. We also show that given an arbitrarily orientedn‐vertex cycleC, a random digraph(n, p) w.h.p. contains (1 ± o(1))n!pncopies ofC, provided.

    more » « less
  3. Abstract

    Letbe integers with, and set. Erdős proved that when, eachn‐vertex nonhamiltonian graphGwith minimum degreehas at mostedges. He also provides a sharpness examplefor all such pairs. Previously, we showed a stability version of this result: fornlarge enough, every nonhamiltonian graphGonnvertices withand more thanedges is a subgraph of. In this article, we show that not only does the graphmaximize the number of edges among nonhamiltonian graphs withnvertices and minimum degree at leastd, but in fact it maximizes the number of copies of any fixed graphFwhennis sufficiently large in comparison withdand. We also show a stronger stability theorem, that is, we classify all nonhamiltoniann‐vertex graphs withand more thanedges. We show this by proving a more general theorem: we describe all such graphs with more thancopies offor anyk.

    more » « less
  4. Letdenote the power set of [n], ordered by inclusion, and letdenote the random poset obtained fromby retaining each element fromindependently at random with probabilitypand discarding it otherwise. Givenanyfixed posetFwe determine the threshold for the property thatcontainsFas an induced subposet. We also asymptotically determine the number of copies of a fixed posetFin. Finally, we obtain a number of results on the Ramsey properties of the random poset.

    more » « less
  5. Motivated by the celebrated Beck‐Fiala conjecture, we consider the random setting where there arenelements andmsets and each element lies intrandomly chosen sets. In this setting, Ezra and Lovett showed andiscrepancy bound whenn ≤ mand anO(1) bound whenn ≫ mt. In this paper, we give a tightbound for the entire range ofnandm, under a mild assumption that. The result is based on two steps. First, applying the partial coloring method to the case whenand using the properties of the random set system we show that the overall discrepancy incurred is at most. Second, we reduce the general case to that ofusing LP duality and a careful counting argument.

    more » « less