# Probability of vertices in a complete bipartite graph being disconnected such that no path of length 2 remains between them?

My problem is the following. I have a set of vertices $N$ and a set of vertices $H$. Each vertex $n \in N$ is connected by means of an edge to each vertex $h \in H$. So the two sets of vertices and the set of edges form a complete bipartite graph. The graph is also undirected. Let us say that two vertices $n_1,n_2 \in N$ can communicate with each other if there exists a path $n_1h_1n_2$ of length 2, where $h_1 \in H$. Since we start out with a complete bipartite graph, initially all vertices in $N$ can communicate with each other. However, now there is a probability $p$ assigned to each edge. This probability is the same for all edges and it models the probability that a vertex $n \in N$ is disconnected from a vertex $h \in H$ after some fixed amount of time $t$. Moreover, the probability of two vertices being disconnected is independent of the probability of two other vertices being disconnected. Thus, given that vertices can be disconnected, what is the probability that there does not exist a path $n_1h_1n_2$, for some $n_1, n_2 \in N$ and some $h_1 \in H$ when the time $t$ has elapsed? In other words, what is the probability that two vertices from the set $N$ cannot communicate after $t$ has elapsed?

Edit: To give some background, what I am trying to model is a computer network comprised of computing nodes, represented by the set of vertices $N$, and hubs, represented by the set of vertices $H$. Computing nodes cannot communicate directly with each other, but only by means of an intermediate hub. The edges basically represent cables connecting nodes and hubs. The probability $p$ represents the probability that a cable suffers a failure, e.g., breaks, in an interval of time $[0, t]$.

-
Is time continuous here? If not, do you assume that some pair of $n$s are disconnected at each point in time? –  user17794 Jun 18 '12 at 17:29
I am assuming that a disconnection can occur in each edge at any point in time within the interval $[0, t]$ with probability $p$. So as I understand it, time should be modeled as continuous. –  davitenio Jun 18 '12 at 18:45

so let's denote by $D_{n,h}$ the event that $n$ and $h$ are disconnected at time $t$. $n_1$ and $n_2$ can't communicate if the event $A_{n_1,n_2} := \bigcap_{h \in H} (D_{n_1,h} \cup D_{n_2,h})$ occurred (that is, each path of length 2 is destroyed). We have using indenpence and denoting complementation by ${}^c$: \begin{align*} P(A_{n_1, n_2}) &= \prod_{h\in H} P(D_{n_1, h} \cup D_{n_2,h})\\\ &= \prod_{h\in H} \bigl(1 - P(D_{n_1, h}^c \cap D_{n_2, h}^c)\bigr)\\\ &= \prod_{h\in H} \bigl(1 - P(D_{n_1,h}^c)P(D_{n_2,h}^c)\bigr)\\\ &= \prod_{h\in H} \bigl(1 - (1-p)^2\bigr)\\ &= \bigl(1 - (1-p)^2\bigr)^{|H|} \end{align*}
For $n_1$ and $n_2$ not being able to communicate it is not necessary that both edges of each path of length 2 between them is destroyed. For instance, let's assume the graph has a total of 4 vertices, two vertices $h_1, h_2 \in H$ and $n_1, n_2 \in N$. The edges are initially $\{n_1, h_1\}, \{n_1, h_2\}, \{n_2, h_1\},$ and $\{n_2, h_2\}$. If when time $t$ has elapsed, $\{n_1, h_2\}$ and $\{n_2, h_1\}$ have been disconnected, then $n_1$ and $n_2$ cannot communicate. Notice that in that case no event $D_{n1, h1} \cup D_{n2, h1}$ nor $D_{n1, h2} \cup D_{n2, h2}$ has occurred. –  davitenio Jun 18 '12 at 19:16
@davitenio There is a union $\cup$. $D_{n_1, h_1} \cup D_{n_2, h_1}$ has occured, since the second event has, $D_{n_1, h_2} \cup D_{n_2, h_2}$ since the first has. –  martini Jun 18 '12 at 19:39
$D_{n_1, h_2} \cup D_{n_2, h_2}$ describes the event that $\{n_1, h_2\}$ or $\{n_2, h_2\}$ is broken. –  martini Jun 18 '12 at 19:54