# Probability of randomly selecting an edge in a bipartite graph

Given an $n \times n$ bipartite graph $G$ with a minimum degree $\ge n - d$, make a set $S$ by randomly selecting vertices from the left side with probability $p = \frac1{d+1}$, and make set $T$ by selecting all of the vertices on the right side which have an edge connecting them to every vertex in $S$.

What is the lower bound on the probability that the complete bipartite subgraph $S \times T$ contains a random edge $uw$?

I'm pretty sure that it's:

$$Pr[S \times T\;covers\;uw] \ge (prob.\;u\;was\;selected) \times (prob.\;w\;is\;connected\;to\;every\;member\;of\;S)$$

Obviously the first term there is just $p$, and I think the second term is:

$$Pr[w\;is\;connected\;to\;every\;member\;of\;S] \ge p^{n-d} (1 - p)^d$$

Is that correct?

-
What is the degree of a bipartite graph? – joriki May 4 '13 at 19:40
Also, how does one select from $n$ vertices with probability $p=\frac{1}{d+1}$? – Alex R. May 4 '13 at 21:01
@joriki I meant 'minimum degree', as in the minimum number of edges connected to each vertex. i've updated the question. – aaronstacy May 4 '13 at 22:23
Im sort of confused on the construction. First $S$ is a random set constructed by letting $v\in S$ with probability $1/(d+1)$. Then, you define a set $T$ (which depends on $S$) by $v\in T$ if and only if for every $s\in S$ we have that $(v,s)$ is an edge. Then, you say, remove every vertex in $S$ that is not connected with every vertex in $T$, but by construction, isn't every vertex in $T$ already connected to every vertex in $S$? – Daniel Montealegre May 4 '13 at 22:52
@aaronstacy I elaborated a little in an answer below. It is basically the same as joriki but since you didn't accept his answer I decided to go ahead and post a little more. Let me know if something is not clear. – Daniel Montealegre May 8 '13 at 6:22

Since you commented about $11$ hours ago and joriki's answer was given $2$ days ago, and you didnt accept it I will go ahead and expand a little on his answer.

First of all since you want $w$ to connect to all of $S$, then we are looking for the probability of the event $S\subset N(w)$ (the set of neighbors of $w$). Note that you probably tried to calculate the probability of $N(w)=S$. I think this will be quite hard because $S$ is a $\textbf{random}$ set. It is however possible to calculate the probabilty that the non neighbors of $w$ on the left fail to be in $S$ (note that this is $u\notin W \Rightarrow u\notin S$ is the same as $u\in S \Rightarrow u\in N(w)$ which means $S\subset N(w)$).

$\Pr(w\in T)=\Pr(\forall u\notin N(w) \textbf{ (on the left) }, u\notin S)=(1-p)^{n-\deg(w)}\geq (1-p)^d$.

Since the minimal degree is greater or equal to $n-d$.

-

The first inequality is in fact an equality.

In the second inequality, you don't need the term $p^{n-d}$, since you don't care whether the vertices that $w$ is connected to have been selected or not. All you need is that none of the up to $d$ vertices that $w$ isn't connected to have been selected. Thus

$$\Pr[uw\in S\times T] \ge p(1-p)^d\;.$$

-