0
$\begingroup$

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability $p=\frac{\mathrm{log}(n)}{\omega(n)^{2}}$. Now i know the threshold for an isolated vertex is an $n \times n$ random bipartite graph is $p(n)=\frac{\mathrm{log}(n)}{n}$ i thought since $\omega(n)^{2} \leq n$ perhaps in my case as the probability for an edge was larger i might find a similar thing, but i think not. Here is my arguement

For any vertex $v$ in $K_{\omega(n)} \times K_{\omega(n)}$ let $X(v)$ be the indicator random variable with $X(v)=1$ if $v$ is isolated and $X(v)=0$ otherwise. It follows that $P(X(v)=1)=\left(1-\frac{\mathrm{log}(n)}{\omega(n)^{2}}\right)^{\omega(n)} \approx e^{-\frac{\mathrm{log}(n)}{\omega(n)}}=\frac{1}{n^{1/\omega(n)}}=O(1)$

Thus the probability that a vertex $v$ is isolated is constant as $n\rightarrow \infty$ and so it is very likely that there will be an isolated vertex. Is this arguement valid in proving we have an isolated vertex in the regime i have described.

Improve this question
$\endgroup$
4
  • $\begingroup$ Your notation may be confusing. Also, the theory of a random bipartite graph is not the same as that of a random graph. You have potentially $\omega^2$ edges with edge probability $\frac{\log{n}}{\omega^2}.$ So the expected number of edges is $\log{n}.$ Since the number of vertices is somewhere between $2\log{n}$ and $2\sqrt{n},$ it is highly likely that there are a great number of isolated vertices. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 4, 2014 at 20:09
  • $\begingroup$ Thanks for the help :)! I'm interested to know why the degree calculation i presented is incorrect, i appreciate you said that Random bipartite graphs need to be considered differently to a general random graph, so how should i have done the calculation for the degree? $\endgroup$
    – Pavan Sangha
    Commented Dec 6, 2014 at 16:14
  • $\begingroup$ Since you speak of an $n \times n$ bipartite graph, replace your $n$ by $t$ and your $\omega$ by $n$ hence "a random bipartite graph $K_{n} * K_{n}$ where $\mathrm{log}(t)\leq n \leq t^{1/2}$, in which each of the $n^{2}$ edges is placed randomly with probability $p=\frac{\mathrm{log}(t)}{n^2}$. See how that works. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 7, 2014 at 5:31
  • $\begingroup$ But I didn't say you were wrong, just that your notation is confusing and your conclusion much less than optimal. You say that the probability that the first vertex you check is isolated goes to something like $e^{-1}$ or $1$ (depending on if $\omega \approx \log{n}$ or $\omega\approx \sqrt{n}$ in your notation.) In any case, not only is it very likely that there is an isolated vertex. It is highly likely that over a third are isolated in the first case or that the proportion of isolated vertices goes rapidly to $1$ in the second. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 7, 2014 at 7:18

0

Reset to default

You must log in to answer this question.