Consensus Times on Erdős–Rényi Random Graphs

Definitions and mathematical statement

For each integer $n\geq 1$, let $p_n$ satisfy $0\leq p_n/n\leq 1$, and let $G_n\sim G(n,p_n/n)$ be the Erdős--Rényi graph on $V_n=\{1,\ldots,n\}$, with each unordered pair of distinct vertices independently joined with probability $p_n/n$. The source does not specify a further regime for $p_n$.

Let $X_t(v)$ denote the opinion at vertex $v$. Following the supplied reconstructed statement, take the initial opinions to be pairwise distinct, represented by $X_0(v)=v$. A voter update replaces the opinion at a vertex by the opinion at a neighboring vertex. The rule for selecting updates, the clock rates, and the treatment of isolated vertices must be specified to determine the stochastic process; these are absent from the supplied extract.

For a specified discrete-time voter dynamics $X^{\mathrm d}$, define \[ T_n^{\mathrm d}=\inf\left\{k\in{\mathbb{Z}}_{\geq0}:\exists i\in V_n\ \forall v\in V_n,\ X_k^{\mathrm d}(v)=i\right\}. \] For a specified continuous-time voter dynamics $X^{\mathrm c}$, define \[ T_n^{\mathrm c}=\inf\left\{t\in[0,\infty):\exists i\in V_n\ \forall v\in V_n,\ X_t^{\mathrm c}(v)=i\right\}. \] In both definitions, $\inf\varnothing=+\infty$. Equivalently, if $V_i(t)=\{v\in V_n:X_t(v)=i\}$, consensus means that $V_i(t)=V_n$ for some $i$. This gives a precise reading of the consensus event in the original extract.

Requested asymptotic problem. Determine, as $n\to\infty$, the asymptotic consensus times $T_n^{\mathrm d}$ and $T_n^{\mathrm c}$ as functions of the sequence $p_n$, with pairwise distinct initial opinions.

Unresolved qualifications. This request is a family of incompletely specified asymptotic questions. The source does not identify the update conventions, time normalization, density regimes, or whether the desired result concerns expectations, typical orders, limiting distributions, or another asymptotic criterion. It also does not specify whether graph randomness is averaged over or conditioned upon. With neighbor-copying dynamics and distinct initial opinions, disconnected components cannot exchange opinions, so consensus on all of $V_n$ is impossible on a disconnected graph. The source does not state whether to retain this infinite consensus time, condition on connectivity, or study a specified component. No such choice is made here.

Short English statement

Starting with a different opinion at every vertex of $G(n,p_n/n)$, determine how the time until every vertex has the same opinion scales with $n$ and $p_n$, in discrete and continuous time. A precise asymptotic target requires additional choices about update rules, clock normalization, disconnected graphs, and the probabilistic meaning of the asymptotics. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005043$, title "Consensus Times on Erdős--Rényi Random Graphs," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection.
• Supplied report citation: Population Dynamics and Statistical Physics in Synergy (2023), Oberwolfach Reports, pp. 577--656, DOI 10.4171/owr/2022/12. https://doi.org/10.4171/owr/2022/12. The original extract identifies p. 617 and the contribution "Consensus time in the voter model on the Erdős--Rényi random graph: A spectral approach," by Anton Klimovsky, joint work with Thomas van Belle. The registry separately supplies proposed year 2022 and no named proposer.
• Supplied literature source: "Oberwolfach report." https://doi.org/10.4171/owr/2022/12.
• Supplied literature source: "Meeting and coalescence times on Erdos Renyi components." https://arxiv.org/abs/2607.13183.
• Literature assessment checked at 2026-08-22: supplied dated curation, not independently verified. It labels the problem open and states that consensus times are known in several dense and random graph regimes, while no single general asymptotic answer covers the stated question. It also says that the extract specifies neither graph density nor initial condition. The reconstructed statement does specify distinct initial opinions; this difference is retained as a source qualification.
• The registry labels the statement corrected_verified and says it was reconstructed and checked against the official report. These are supplied provenance claims; no source visit or independent verification is asserted here.