Some Questions — Question 13

Definitions and mathematical statement

Consider sequences $\mathcal G=(G_n)$ of finite simple graphs with uniformly bounded degrees and $|V(G_n)|\to\infty$. Local convergence means that, for every radius $r$ and finite rooted graph $B$, the proportion of vertices whose rooted radius-$r$ neighborhood is isomorphic to $B$ converges. The resulting probabilities specify a law of rooted graphs.

Write $\mathcal H\sim\mathcal G$ if $V(H_n)=V(G_n)$ for each $n$ and some $L\geq1$ satisfies \[ L^{-1}d_{G_n}(u,v)\leq d_{H_n}(u,v)\leq Ld_{G_n}(u,v) \] for all $n,u,v$. Distances between different components are infinite; equivalence therefore preserves the component partition. The constant may depend on the two sequences but not on $n$. Define \[ e(\mathcal G)=\liminf_n\frac{|E(G_n)|}{|V(G_n)|}, \qquad c(\mathcal G)=\inf_{\mathcal H\sim\mathcal G}e(\mathcal H). \] The equivalent sequences are bounded-degree graph sequences on these fixed vertex sets; their edges may be changed.

If $\mathcal G$ and another sequence $\mathcal G'$ converge locally to the same rooted-graph law, must $c(\mathcal G)=c(\mathcal G')$? The two original sequences need not have the same sizes or corresponding vertices. Rewiring is defined internally for each one. The infimum ranges over uniform metric comparisons, so distortion cannot grow with the sequence index. Equality of local statistics is the hypothesis, whereas the cost permits global changes constrained by a common distance bound.

Short English statement

Is combinatorial cost determined entirely by the local limit of a bounded-degree graph sequence?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200013 (AMR-011-0013), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 13. Original source indexed by AMR-011-0013. https://www.renyi.hu/~abert/questions.pdf.