Definition) The length of a path between two vertices in a graph is the number of edges in the path connecting them.

Definition) A random graph $G(n,p)$ is a graph with $n$ vertices, and the probability of drawing each edge is $p$ and independent of other edges.

Let $G(n,p)$ be a random graph.

  • Event $A$ : There is at least one path with length $l$ between $v$ and $u$.
  • Event $B_{1}$ : There is no path with length $1$ between $v$ and $u$.
  • Event $B_{2}$ : There is no path with length $2$ between $v$ and $u$.
  • ...
  • Event $B_{l-1}$ : There is no path with length $l-1$ between $v$ and $u$.

Are $A,B_{1},...,B_{l-1}$ independent events?

  • $\begingroup$ You give the the definition of the distance between two vertices. The events however seem to be about the distance of a path. So are those events about the length of any (not necessarily shortest) path, or about the distance between the vertices? $\endgroup$ – Jaap Scherphuis Feb 5 '18 at 16:21
  • $\begingroup$ @JaapScherphuis I modify the question. $\endgroup$ – Hasan Heydari Feb 5 '18 at 16:33
  • $\begingroup$ @Henry There is an ambiguity in my question. I correct it. $\endgroup$ – Hasan Heydari Feb 5 '18 at 16:34
  • $\begingroup$ The question is still unclear because you don't define random graph. How are you randomly choosing this graph? Does each edge have a 50% probability of being present? Presumably $n$ and $p$ are the number of vertices and edges. Are they fixed or randomly chosen somehow? How are they related to $l$? Are all non-isomorphic graphs equally likely? Are only simple graphs included? What about $u$ and $v$, are they always distinct? Are they randomly chosen amongst the vertices? Are they the same for all events, you are interested in? etc. You'll need to give more context to get a meaningful answer. $\endgroup$ – Jaap Scherphuis Feb 6 '18 at 14:00
  • $\begingroup$ @JaapScherphuis The definition of the random graph is added to the question. $\endgroup$ – Hasan Heydari Feb 7 '18 at 6:04

Consider the path of length 1 between $u$ and $v$. There is only one such path. Since the usual convention is that paths do visit any vertex more than once, all longer paths between $u$ and $v$ cannot use the edge directly connecting $u$ and $v$. So the path of length 1 has no edge in common with the longer paths. This makes the event $B_1$ independent from all the other events since it uses its own unique potential edge that is randomly chosen to be present or not independently from the other edges.

Let's assume $n>3$. $B_1$ will be independent from $B_2$ and $B_3$. Generally however, $B_2$ and $B_3$ will not be independent. Intuitively, not having a path of length 2 would make it more likely that $u$ and $v$ have few edges, which in turn makes it more likely that there are no paths of length 3. For example, let's look at the simplest case, $G(4, 1/2)$.

$K_4$ has 6 edges, so we have $2^6=64$ equally probably graphs.

Exactly 28 of these graphs have at least one path of length 2 between two designated vertices $u$ and $v$. This means that 36 have none, so $P(B_2)=36/64=9/16$.

Exactly 14 of the 64 graphs have at least one path of length 3 between $u$ and $v$, so 50 have none and $P(B_3)=50/64=25/32$.

There are 32 graphs that have neither a path of length 2 nor a path of length 3, so $P(B_2 \cap B_3) = 32/64 = 1/2$.

So as expected we have: $$P(B_3|B_2) = \frac{P(B_3 \cap B_2)}{P(B_2)} = \frac{32}{36} = \frac{8}{9} > P(B_3)$$


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.