Distance exponent of random series-parallel graphs

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.

Starting with one source--sink edge $G_0$, replace every edge independently at each generation by two edges in series with probability $p$ or two parallel edges with probability $1-p$. Let $\Delta_n$ be the unit-edge source--sink distance in generation $n$. Equivalently, \[\Delta_n\stackrel d=\begin{cases}\Delta_{n-1}^{(1)}+\Delta_{n-1}^{(2)},&\text{with probability }p,\\\min(\Delta_{n-1}^{(1)},\Delta_{n-1}^{(2)}),&\text{with probability }1-p,\end{cases}\] with independent copies and an independent choice of case. Put $\delta(p)=\lim_{n\to\infty}n^{-1}\log\mathbb E\Delta_n$, the exponential mean-distance rate. The source proves this rate exists and is positive for $p>1/2$.

Statement recorded in the supplied source.

Determine $p\mapsto\delta(p)$ on $[1/2,1]$, and decide whether $\delta(1/2)=0$. [S2]

Short English statement

Determine the exponential distance-growth rate in a random series-parallel graph, especially at its critical parameter.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 10000069 (AMR-099-0069). 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, final model and Question 9.6, p. 18. https://arquivo.pt/noFrame/replay/20201231041538id_/http://www.wisdom.weizmann.ac.il/~itai/erd100.pdf.