Girth and Euclidean Distortion

NEW

Problem: Let $G=(V,E)$ be a finite connected simple unweighted graph with shortest-path metric $d_G$, girth $g$, and minimum degree $\delta(G)\ge 3$. The reconstructed question is whether the Linial--Magen--Naor lower bound for regular graphs,

$$c_2(G)\gtrsim \sqrt{g},$$

continues to hold without regularity. Here

$$c_2(G)=\inf_f \operatorname{Lip}(f)\operatorname{Lip}(f^{-1}),$$

where $f:V\to \ell_2$ ranges over injective maps and distances on $V$ are $d_G$.

This is the natural formalization of “large girth and the degree of each vertex is greater than $2$”: finite graph metric, minimum degree at least $3$, no regularity assumption.

Result: The conjectured lower bound is true. In fact,

$$c_2(G)\ge \frac{1}{3}\sqrt{\left\lfloor \frac g2\right\rfloor}.$$

Proof. Let $t=\lfloor g/2\rfloor$. Run the stationary simple random walk $(X_s)_{s\ge0}$ on $G$, whose stationary measure is

$$\pi(v)=\frac{\deg(v)}{2|E|}.$$

The chain is reversible.

Fix a starting vertex $v$. Since $t\le g/2$, during the first $t$ steps the distance

$$R_s=d_G(v,X_s)$$

evolves locally as on a tree: whenever $R_s=r>0$, there is exactly one neighbor of $X_s$ at distance $r-1$ from $v$, and all other neighbors are at distance $r+1$. Otherwise a cycle of length $<g$ would be formed. Because $\deg(X_s)\ge3$,

$$\mathbb P(R_{s+1}=R_s+1\mid X_s)\ge \frac23, \qquad \mathbb P(R_{s+1}=R_s-1\mid X_s)\le \frac13.$$

At $R_s=0$, the next step increases the distance. Hence

$$\mathbb E(R_{s+1}-R_s\mid X_0,\dots,X_s)\ge \frac13.$$

Summing gives

$$\mathbb E[d_G(X_t,X_0)\mid X_0=v]\ge \frac t3,$$

and therefore, by Jensen,

$$\mathbb E[d_G(X_t,X_0)^2]\ge \frac{t^2}{9}.$$

Now let $f:V\to\ell_2$ be scaled so that it is $1$-Lipschitz and has distortion $D$, i.e.

$$\|f(x)-f(y)\|_2\ge \frac{d_G(x,y)}{D}.$$

Hilbert space has Markov type $2$ with constant $1$; equivalently, for every stationary reversible Markov chain,

$$\mathbb E\|f(X_t)-f(X_0)\|_2^2 \le t\,\mathbb E\|f(X_1)-f(X_0)\|_2^2.$$

Since $f$ is $1$-Lipschitz on edges,

$$\mathbb E\|f(X_1)-f(X_0)\|_2^2\le 1,$$

so

$$\mathbb E\|f(X_t)-f(X_0)\|_2^2\le t.$$

On the other hand,

$$\mathbb E\|f(X_t)-f(X_0)\|_2^2 \ge \frac{1}{D^2}\mathbb E[d_G(X_t,X_0)^2] \ge \frac{t^2}{9D^2}.$$

Thus

$$\frac{t^2}{9D^2}\le t,$$

so

$$D\ge \frac{\sqrt t}{3}.$$

Taking the infimum over $f$ proves

$$c_2(G)\ge \frac{1}{3}\sqrt{\left\lfloor \frac g2\right\rfloor}.$$

The boundary case $\delta=2$ is genuinely different: cycles have arbitrarily large girth but embed into $\mathbb R^2$ with bounded distortion. Thus the assumption $\delta(G)\ge3$ is essential.

Citation: The exact nonregular statement is proved above. The Markov type inequality used is standard; see K. Ball, “Markov chains, Riesz transforms and Lipschitz maps,” Geom. Funct. Anal. 2 (1992), 137–172. The motivating regular-graph problem is from Linial--Magen--Naor, “Girth and Euclidean Distortion.”