Sparse Random Graph Convergence Notions

Definitions and mathematical statement

For an integer $n\geq 1$ and a real parameter $c$ satisfying $0\leq c/n\leq 1$, let $G(n,c/n)$ denote the random simple undirected graph on $[n]=\{1,\ldots,n\}$ in which each unordered pair of distinct vertices is an edge independently with probability $c/n$. A sequence of events $(A_n)$ holds with high probability if $\Pr(A_n)\to 1$ as $n\to\infty$.

Source question. Determine conditions under which a sequence of random graphs converges with respect to each of the following notions: left-convergence, right-convergence, and convergence in the Bollobás--Riordan partition metric. In particular, determine whether the sparse random graphs $G(n,c/n)$, as $n\to\infty$, converge with high probability under each notion.

Unresolved formulation qualifications. The supplied record does not define these three convergence notions. In particular, it does not specify the test graphs and normalization for left-convergence, the target graphs and normalized quantities for right-convergence, or the partition data and metric normalization for partition convergence. These choices must be recovered from the cited source before a fully quantified mathematical statement can be given. The record also does not explicitly state the range of $c$, whether $c$ is held fixed as $n\to\infty$, or the probabilistic meaning of convergence of a random graph sequence. The definition of high probability above concerns events and does not by itself specify that meaning. No coupling across different values of $n$, limit object, or mode of convergence is supplied.

The supplied curation labels the problem partially solved and reports left-convergence with high probability and right-convergence for a restricted class of targets, while describing the full question as open. The target restriction is not stated, and the assessment does not separately resolve the partition-metric question. These are supplied literature qualifications, not independently verified mathematical conclusions.

Short English statement

The problem asks when random graph sequences converge under three named notions, especially for sparse Erdős--Rényi graphs $G(n,c/n)$. The supplied record omits definitions, normalizations, parameter quantifiers, and the precise probabilistic interpretation, so the formulation remains conditional on clarification from the cited report. Its partially solved status is supplied dated curation.

Sources

• Supplied local problem registry record, permanent UnsolvedMath ID $30001664$, title Sparse Random Graph Convergence Notions, exact source problem code catalogue entry. The record places the problem in the Oberwolfach Reports Open Problems collection and gives proposed year 2011; no proposer is named.
• Combinatorics (2011), Oberwolfach Reports, pp. 5--83, DOI 10.4171/owr/2011/01. Supplied source report and literature reference labeled "Oberwolfach Report 01/2011": https://doi.org/10.4171/owr/2011/01. The registry labels the statement corrected_verified and says that the official report confirms the three convergence questions and their sparse random-graph specialization. This verification claim is supplied metadata; the report has not been independently consulted for this draft.
• Supplied literature reference labeled "Gamarnik": https://arxiv.org/abs/1202.3123. No title, full author information, or precise supporting result is supplied.
• Literature assessment checked at 2026-08-21: supplied dated curation, not independently verified. It labels the problem partially solved and reports that sparse Erdős--Rényi graphs are left-convergent with high probability and right-convergent for a restricted class of targets, while the full convergence question remains open. The background describes this as literature triage derived from the supplied Oberwolfach Reports curation and calls for independent verification of time-sensitive status and cited claims.