Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Majority dynamics on sparse random graphs   Majority dynamics on a graph $G$ is a deterministic process such that every
vertex updates its $\pm 1$-assignment according to the majority assignment on
its neighbor simultaneously at each step. Benjamini, Chan, O'Donnel, Tamuz and
Tan conjectured that, in the Erd\H{o}s--R\'enyi random graph $G(n,p)$, the
random initial $\pm 1$-assignment converges to a $99\%$-agreement with high
probability whenever $p=\omega(1/n)$.
  This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large
constant $\lambda$ 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 \leq p \leq \lambda n^{-1/2}$ with a
large constant $\lambda'>0$.

24
The categories of this paper are: dg-ga
34
The categories of this paper are: chem-ph
20
The categories of this paper are: acc-phys
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
10
The categories of this paper are: q-bio
17
The categories of this paper are: q-fin
26
The categories of this paper are: bayes-an
21
The categories of this paper are: adap-org
11
The categories of this paper are: hep-lat
1
The categories of this paper are: cs
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
19
The categories of this paper are: eess
3
The categories of this paper are: physics