most recent 30 from http://mathoverflow.net 2013-05-23T00:22:06Z http://mathoverflow.net/feeds/question/68199 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/68199/average-squared-distance-in-k-regular-graphs Alain Valette 2011-06-19T06:34:48Z 2011-06-19T06:58:20Z

<p>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 <a href="http://mathoverflow.net/questions/67838/average-squared-distance-vs-diameter-in-vertex-transitive-graphs" rel="nofollow">http://mathoverflow.net/questions/67838/average-squared-distance-vs-diameter-in-vertex-transitive-graphs</a> . 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)</p>

http://mathoverflow.net/questions/68199/average-squared-distance-in-k-regular-graphs/68200#68200 Ori Gurel-Gurevich 2011-06-19T06:58:20Z 2011-06-19T06:58:20Z

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