1
$\begingroup$

Given a random (undirected and unweighted) graph $G$ on $n$ vertices where each of the edges has equal and independent probability $p$ of existing (see Erdős–Rényi model). Fix some vertex $u\in G$ and call it the source. I am interested in the probability that our random graph has the following property: we can start at the source and go to any other vertex in the graph in at most exactly $l$ edges, i.e., there is at least some vertex $v\in G$ such that the shortest distance between $u$ and $v$ is $l$ and there is no vertex $v'\in G$ such that the shortest distnace between $u$ and $v'$ is more than $l$.

Distance $d$ between $u\in G$ and $v\in G$ is measured by the number of edges between $u$ and $v$ along a shortest path.

$\endgroup$
  • $\begingroup$ Is there a particular range of $p$ and $\ell$ that you are interested in? Also, do you care mostly about "w.h.p." results or do you care about $p$ and $\ell$ so that this probability tends to zero and you want to find out exactly how quickly? $\endgroup$ – D Poole Aug 11 '14 at 21:39
  • $\begingroup$ The answer to this question might give me an insight into a proof that I'm working on. The range of $p$ that I would like to test is up to 1024, so I would like for the answer to give at least approximately good results in that range, i.e., something that only works at $\infty$ would be useless to me. The range of $l$ should be from 1 to $p-1$, i.e., all possible $l$ values. I do not care for how quickly the probability tends to 0 with changing $p$ and $l$. $\endgroup$ – nick.bourbaki Aug 11 '14 at 22:06
0
$\begingroup$

It seems to me that you want an exact expression for this probability. Here is one such formula albeit it does not have a nice closed form. Fix some vertex $u$ in $G(n,p)$. Let's define $d(u) = \max_v d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. So you are interested in $P(d(u) \leq \ell)$ for any $\ell \in [1,n-1]$.

Let $$A_\ell:=\{(k_1, ..., k_\ell): k_i \geq 0, k_1+...+k_\ell = n-1, \text{ if }k_i=0, \text{ then } k_{i+1}=...=k_{\ell}=0\}, $$ and $k_0:=1$.

Then $$P(d(u) \leq \ell) = \sum_{(k_1,...k_\ell)\in A_{\ell}} {n-1 \choose k_1, k_2, ..., k_\ell} \prod_{i=1}^{\ell} \left( 1 - \left( 1- p\right)^{k_{i-1}}\right)^{k_i} (1-p)^{(1+k_1+...+k_{i-2})k_i},$$ with the understanding that the last factor is defined to be 1 for $i=1$.

Why? Run a breadth-first search starting from $u$. Let $\mathcal{L}_1, ..., \mathcal{L}_{n-1}$ be the (random) set of vertices found at each level; formally $\mathcal{L}_i:=\{v \in G(n,p): d(u,v)=i\}$. Suppose that $L_1,...,L_{n-1}$ is a partition of $[n]\setminus \{u\}$ so that if $|L_j|=0,$ then $|L_{j+1}|=...=|L_{n-1}|=0$. So $$ P((\mathcal{L}_1,...,\mathcal{L}_{n-1})=(L_1,...,L_{n-1}))= \prod_{i=1}^{n-1} \left( 1 - \left(1-p\right)^{|L_{i-1}|}\right)^{|L_i|}(1-p)^{(1+k_1+...+k_{i-2})k_i}. $$ This is because we need every vertex of $L_{i}$ to be adjacent to at least one vertex of $L_{i-1}$ and NOT adjacent to any vertex of $L_0, ..., L_{i-2}$. To finish off the proof, the events $\vec{\mathcal{L}} = \vec{L}$ and $\vec{\mathcal{L}}=\vec{L}'$ are disjoint if $\vec{L} \neq \vec{L}'$. Adding over all possible such sequences yields the formula above.

EDIT: I forgot the $(1-p)^{(1+...+k_{i-2})k_i}$ term in the original post.

$\endgroup$
  • $\begingroup$ While it will take me a little bit of time to traverse and really understand your answer, I wanted to say that I appreciate you writing it out! I just realized that I said something a little bit wrong in my question and actually meant that I was interested in $P(d(u) = l))$. Nevertheless, I think I should be able to arrive at that answer by understanding your answer. $\endgroup$ – nick.bourbaki Aug 13 '14 at 20:20
  • $\begingroup$ To get $P(d(u)=\ell)$, instead of summing over $A_\ell$, sum over $(k_1, ..., k_\ell)$ with $k_i >0$ and $k_1+...+k_\ell=n-1$. This forces there to be vertices at distance $\ell$ from $u$. $\endgroup$ – D Poole Aug 14 '14 at 13:41
  • $\begingroup$ In both cases, I think the condition should be $k_1 + \ldots + k_l \leq n - 1$ because if it's "$=$", then you're assuming that the graph is connected. Do you agree? $\endgroup$ – nick.bourbaki Aug 14 '14 at 16:10
  • $\begingroup$ If the graph is not connected, then all other vertices can not be reached within $\ell$ edges. You need the graph to be connected for how the problem is worded. $\endgroup$ – D Poole Aug 15 '14 at 4:40
  • $\begingroup$ I agree. Okay, so I understand your answer fully, but the numbers don't seem to add up correctly when I try $n=4, p=0.5$. I expect $P(d(u)=1)+P(d(u)=2)+P(d(u)=3) = 1$, but I get $2/16, 15/16, $ and $2/16$, respectfully... $\endgroup$ – nick.bourbaki Aug 15 '14 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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