MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Mikhail Ostrovskii Sep 15 '13 at 1:58
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. – Mikhail Ostrovskii Oct 8 '13 at 3:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.