Tran–Vu conjecture on one-voter bias in majority dynamics

Let $\mathbb{G}(2n+\Delta,1/2)$ be the random graph with vertex sets initially colored red and blue as

$$R_0=\{v_1,\ldots,v_{n+\Delta}\},\qquad B_0=\{v_1',\ldots,v_n'\}.$$

A color wins when all vertices eventually have that color. Tran–Vu's conjecture. For a function $f(\Delta)>0$, majority dynamics on $\mathbb{G}(2n+\Delta,1/2)$ converges to the all-red state $R_k=R_0\cup B_0$ with probability at least

$$\frac12+f(\Delta),$$

as $n\to\infty$. This formalizes the claim that a bias of $\Delta$ extra red voters, in particular a single extra voter, influences the final state with positive probability. The paper presents this as a conjecture of Tran and Vu and notes an essentially equivalent formulation in subsequent work; the supplied text does not establish its resolution.