8
$\begingroup$

Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal distortion of a metric embedding $X \rightarrow Y$?

Recall that for two metric spaces $(X, d), (Y, d')$ a Lipschitz map $f: X\rightarrow Y$ has distortion $C$ if $d(x,x')\leq C d'(f(x),f(x'))$.

In some sense this asks if the finite coarse geometry of a random graph is unique. Since the maximal distortion is always $O(\log n)$ (Bourgain's theorem), the essential question is whether $D(X, Y)=\Omega(\log n)$ or $D(X,Y)=o(\log n)$ with high probability. One can e.g. ask whether two sequences of random graphs $\{X_n\}_{n=1}^{\infty}, \{Y_n\}_{n=1}^{\infty}$ coarsely embed into each other.

$\endgroup$
3
  • 2
    $\begingroup$ There is some confusion in the definition of distortion and the statement of Bourgain's theorem (e.g. the distortion of any embedding of a path $P_n$ into a complete graph $K_n$ is $n-1$), but the question is interesting. $\endgroup$ Sep 15, 2013 at 1:58
  • 1
    $\begingroup$ Mendel and Naor (arXiv:1306.5434, Proposition 8.1) proved a result which implies the maximal order of distortion for random 3-regular graph. Possibly their proof can be adjusted to get what you want. $\endgroup$ Oct 8, 2013 at 3:00
  • $\begingroup$ A similar argument can be done in the $G(n,c/n)$ model - I think it's even slightly easier there. $\endgroup$
    – Will Sawin
    Dec 12, 2016 at 15:45

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.