26 problems

Consider majority dynamics on $\mathbb{Z}^2$ with i.i.d. initial opinions of density $p\in[0,1]$, and let $\eta_t(0)$ denote the opinion at the origin at time $t$. Exponential fixa…

Tran–Vu conjecture. This result should hold whenever

Let $G\sim G(n,p)$ carry a random initial $1/2$ coloring, and let the initial majority side be the color class with more vertices. Chakraborti–Kim–Lee–Tran conjecture. If … for a c…

Let $G\sim G(n,p)$ be a random graph on $n$ vertices with a random initial $1/2$ coloring, and let the initially larger color class be the initially larger side. Benjamini–Chan–O'D…

Let $G\sim G(n,p)$ be an Erdős–Rényi random graph, and let the initial coloring have a fixed red advantage of $\Delta$ vertices. For a target error probability $\varepsilon$, write…

Majority Dynamics conjecture. For every $varepsilon>0$, with high probability the number of oscillating vertices lies in

Let $G(n,p)$ be the binomial random graph on $V_n=\{1,\ldots,n\}$, where each pair of vertices is an edge independently with probability $p=p(n)$. Consider two-state majority dynam…

Sharp phase-transition conjecture. For any sufficiently large constant $L(p,q)>0$, if

Let $\mathbb{G}(2n+\Delta,1/2)$ be the random graph with vertex sets initially colored red and blue as … A color wins when all vertices eventually have that color. Tran–Vu's conjec…

Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture. With probability $1-\varepsilon$, the vertices in $G(n,p)$ have an $(1-\varepsilon)$-proportion agreement after sufficiently many day…

Let $G(n,p)$ be a random graph, let $P_t$ and $N_t$ denote the sets of vertices playing the two strategies at time $t$, and let $d$ be the parameter in the condition $p\geq d/n$. C…

Let $G_{n,p}$ be a random graph sampled independently of an arbitrary initial red-blue coloring of its vertices, and let $\varepsilon>0$. Assume … After the first step of majority…

Let $G_{n,p}$ be a random graph on $n$ vertices, and consider majority dynamics from an initial red-blue coloring with more red vertices than blue. For fixed $p\in(0,1)$, let…

Let $c1(k,n)$ be the probability that Red wins when Red's camp initially has size $n/2+k$, with $p=.5$, and define the value of the $i$th defector by … with $c1(n,0)=1/2$. Values o…

Let $\rho(k,n)$ be the probability that Red wins when Red's camp initially has size $n/2+k$, with edge probability $p=.5$. The power of one conjecture. There is a constant $b4>0$ s…

Let $\operatorname{MD}_{\mathrm{coins}}$ denote the coin-valued median dynamics process on $\mathbb{Z}^d$, and let $\eta_t(\underline{0})$ be the opinion at the origin. Coin-median…

Let $\operatorname{MD}_{\mathrm{coins}}$ denote the coin-valued median dynamics process on $\mathbb{Z}^d$, and let $\eta_t(\underline{0})$ be the opinion at the origin. Coin-median…

Let $(\eta_t)_{t\geq0}$ be median dynamics and, for an initial density $p\in[0,1]$, let $(\xi_t^p)_{t\geq0}$ be the coupled majority-dynamics process. Say that majority dynamics fi…

Let $p_c(G)$ be the infimum of the densities $p\in[0,1]$ for which zero-temperature Glauber dynamics on $G$, started from i.i.d. $\operatorname{Bernoulli}(p)$ opinions, converges a…

Let $G(n,p)$ be a random graph with vertex set $V_n$, let $d=np$, and let $S_t(v)\in\{-1,+1\}$ be the state of vertex $v$ after $t$ rounds of synchronous majority dynamics. Benjami…

Benjamini–Chan–O'Donnell–Tamuz conjecture. If $d\to\infty$, then the quantities $(\mu_t^2)_{t\geq0}$ increase with high probability by a factor of $d$. This conjecture concerns the…

Majority dynamics assigns each vertex a state in a finite state set and updates states synchronously according to the majority of its neighbors. A trajectory stabilises to periodic…

For majority dynamics on $\mathbb{Z}^2$, let $p_c(t)$ denote the critical probability for percolation at time $t$. At time zero, the critical probability is $\frac12$. Constant cri…

For majority dynamics on $\mathbb{Z}^2$, let $\eta_\infty$ be the pointwise limiting configuration and define … Let $p_c(t)$ be the critical percolation probability at time $t$. Li…

Let $G$ be drawn from the Erdős–Rényi random graph $G(n,d_n/n)$, and let $X_t(i)$ denote the opinion of vertex $i$ at time $t$ under majority dynamics. Write $\lim_t X_{2t}(i)$ for…