Local Weak Limits of Surface-Embedded Random Graphs

Definitions and mathematical statement

Let $g\in{\mathbb{Z}}_{\geq 0}$ be fixed, and let $\Sigma_g$ be the closed orientable surface of genus $g$. The supplied interpretation of $S_g(n,m)$ is a uniformly chosen labelled graph with vertex set $[n]=\{1,\ldots,n\}$, exactly $m$ edges, and an embedding in $\Sigma_g$. Here embeddability means that the graph admits a drawing on the surface with distinct edge interiors disjoint from one another and from the vertices. The supplied record does not specify whether graphs are simple, whether loops or parallel edges are allowed, or whether an embedding is part of the sampled object. Consequently, these conventions must be resolved before the finite probability space is uniquely determined. In particular, sampling graphs that admit embeddings and sampling graphs together with embeddings need not give the same distribution.

Once the graph and sampling conventions are fixed, write $\mathcal S_g(n,m)$ for the resulting finite class and interpret uniformity as \[ \Pr\left(S_g(n,m)=G\right)=\frac{1}{|\mathcal S_g(n,m)|},\qquad G\in\mathcal S_g(n,m), \] whenever $\mathcal S_g(n,m)\neq\varnothing$. Let $m=m(n)\in{\mathbb{Z}}_{\geq0}$ satisfy this nonemptiness condition for all sufficiently large $n$, and put $G_n=S_g(n,m(n))$. Conditionally on $G_n$, choose a vertex $\rho_n$ uniformly from $[n]$.

For a graph $G$, a vertex $v$, and an integer $r\geq0$, let $B_r(G,v)$ be the rooted subgraph induced by the vertices at graph distance at most $r$ from $v$, with root $v$. Isomorphism of these neighborhoods forgets vertex labels and preserves the root. A distributional local weak limit is a random rooted, connected, locally finite graph $(\mathcal G,\rho)$ such that, for every $r\geq0$ and every finite rooted graph $(H,o)$, \[ \lim_{n\to\infty}\Pr\left(B_r(G_n,\rho_n)\cong(H,o)\right) =\Pr\left(B_r(\mathcal G,\rho)\cong(H,o)\right). \] The rooted limit describes the component seen from the sampled vertex; the finite graphs are not assumed connected.

Requested determination. Identify the Benjamini--Schramm local weak limit of $S_g(n,m(n))$ in the intended asymptotic regimes as $n\to\infty$. The record calls these regimes "natural" but supplies no conditions on $m(n)$, so it does not specify a complete family of sequences for which existence or identification is requested. Existence of a locally finite limit is not assumed here.

There is also an unresolved convergence qualification. The displayed condition averages over both the random graph and its uniform root. A stronger possible formulation asks that, for every $r$ and $(H,o)$, \[ \frac{1}{n}\sum_{v\in[n]}\mathbf 1\{B_r(G_n,v)\cong(H,o)\} \xrightarrow{\Pr} \Pr\left(B_r(\mathcal G,\rho)\cong(H,o)\right). \] The supplied record does not distinguish these formulations. The model conventions, asymptotic regimes, and intended mode of convergence therefore remain qualifications requiring mathematical review.

Short English statement

For a fixed orientable genus, sample a labelled graph uniformly subject to its vertex count, edge count, and surface embeddability, then inspect neighborhoods of a uniformly chosen vertex. Determine their limiting distribution as the vertex count grows in the intended edge-count regimes. The source leaves the graph conventions, sampling of embeddings, edge-count regimes, and precise mode of convergence unresolved.

Sources

• Supplied local problem registry record: permanent UnsolvedMath ID $30003812$, source problem code catalogue entry, title Local Weak Limits of Surface-Embedded Random Graphs, in the Oberwolfach Reports Open Problems collection. The supplied proposed year is $2018$; no individual proposer is identified.
• Supplied report citation: Enumerative Combinatorics (2019), Oberwolfach Reports, DOI 10.4171/owr/2018/23, pp. 1381--1464. https://doi.org/10.4171/owr/2018/23. The record describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. Its citation year $2019$ and the $2018$ year in the DOI and proposed-year field are retained without reconciliation; no exact problem page or individual attribution is supplied.
• Supplied literature source: Local limit of sparse random planar graphs. https://arxiv.org/abs/2101.11910.
• Supplied literature source: Evolution of random graphs on surfaces. https://doi.org/10.1137/17M113383X.
• Supplied literature assessment, checked on 2026-08-21: the notation is described as uniform labelled graphs embeddable on a fixed-genus surface; later work is said to determine sparse planar local limits, while no general Benjamini--Schramm limit for the extracted $S_g$ model and regimes is said to be known. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The record labels the problem open and its statement corrected_verified; its verification note describes repairs to notation, typography, and sentence structure while preserving mathematical content. These are supplied registry labels, not independent mathematical verification. The source itself requests independent verification of time-sensitive status and cited claims.