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=(V,E)$ be a finite, connected, $k$-regular graph. Let $avg(d^2)$ be the averaged square distance between vertices, as defined in Average squared distance vs diameter in vertex-transitive graphs . Is it true that $\sqrt{avg(d^2)}=\Omega(\log(|V|))$? The answer is positive for vertex-transitive graphs. ($\Omega$ is the "Big Omega" Landau notation)

share|cite|improve this question
up vote 6 down vote accepted

The number of vertices in the ball of radius $c \log_k(|V|)$ ($c<1$) is small compared to $|V|$, so most pairs of vertices are more than that apart.

share|cite|improve this answer
Thanks! Clearly I should have thought more... – Alain Valette Jun 19 '11 at 7:37

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.