Scaling of distances in a random hierarchical graph

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G_0$ be an oriented source--sink edge. At each step select an edge uniformly from the current graph and replace it by one edge in series with two parallel edges, preserving its two endpoints and orientation. Let $D_n$ be unit-edge shortest-path distance between the marked source and sink after $n$ replacements. The source establishes existence of \[\gamma=\lim_{n\to\infty}\frac{\log\mathbb E D_n}{\log n}.\] Gromov--Hausdorff convergence compares compact metric spaces by embedding them isometrically in a common metric space and taking their Hausdorff distance, with infimum over such embeddings.

Statement recorded in the supplied source.

Determine $\gamma$. Find deterministic rescalings $a_n>0$ such that $D_n/a_n$ converges in distribution to a nondegenerate limit, and establish the corresponding Gromov--Hausdorff scaling limit of the graphs $G_n$. [S2]

Short English statement

Find the distance exponent and metric scaling limit of a hierarchy grown by replacing one random edge at a time.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 10000068 (AMR-099-0068). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Itai Benjamini, Euclidean vs. Graph Metric, version dated 16 July 2012; original author manuscript preserved in Arquivo.pt capture of 31 December 2020, Section 9.4, Figure 3 and Question 9.5, pp. 17--18. https://arquivo.pt/noFrame/replay/20201231041538id_/http://www.wisdom.weizmann.ac.il/~itai/erd100.pdf.