[Math] Diameter of random graph.

graph theoryrandom-graphs

Basically I was given a random graph with fixed probability and I need to prove that the diameter of the random graph is asymptotically 2. See the following picture for the detail of the question. a.a.s here means asymptotically almost sure. enter image description here

My attempt is to find the expected value of the shortest path between any pair of vertices. Let $X$ be the random variable indicating the length of the shortest path between any pair of vertices. Then $Pr(X=1) = p$, $Pr(X=2) = (n-2)p^2(1-p)$, $Pr(X=3) = (n-2)(n-3)p^3[1-Pr(X=1)-Pr(X=2)]$ and etc. But to the best of my knowledge, it seems not easy to calculate the expected value based these probabilities asymptotically. Any suggestions on how should I calculate the expectation or should I try another direction?

EDIT1: I think I was very wrong about the probability. $Pr(X=2)$ goes to infinity according to my calculation. Sorry about the naive mistake. I am trying Martigale.

Edit2: Maybe think of it from eccentricity.

Edit3: Let $X$ be the eccentricity of vertex $v$. $Pr(X=1) = p^{n-1}$ which goes to $0$ as $n$ goes to infinity. $Pr(X>2)$ indicates that there is a vertex $u$ such that $u$ is not connected to $v$ or any of the vertices that is directly connected to $v$. So $Pr(X>2) = (n-1)(1-p)^{(|S|+1)}$, where $S$ is the set of vertices connected to $v$. Since $|S| = np + o(1)$ when n is sufficiently large, $Pr(X>2)$ also goes to $0$ as $n$ goes to infinity. I think it is probably the solution.

Best Answer

The solution you suggest in your third edit isn't rigorous, since $\left|S\right|=(n-2)p$ is just an approximation; the actual number of edges emanating from $v$ varies. (It's also not clear how "given $v$ and $u$" is to be interpreted, given that $u$ was introduced in an existential clause referring to the vertices being counted.)

The probability that a given pair of vertices is not connected by a path of length $2$ is $(1-p^2)^{n-2}$, since all edges forming these potential paths are distinct. Thus the expected number of pairs not thus connected is $\binom n2(1-p^2)^{n-2}$, which goes to $0$ as $n\to\infty$ at fixed $p\gt0$. The probability for the diameter to exceed $2$ is less than this expected number, and thus also goes to $0$.

Related Question