Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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$.

share|cite|improve this answer

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\;. $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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