I'm trying to teach myself a little more on threshold probabilities for random graphs, and I'm looking at the probability that graphs have an isolated vertex, when we add on a few restrictions (when by a 'random graph' I mean we take the set of vertices and add each possible (non-directed) edge between vertices with probability p). For example, in the standard ('unrestricted') graph on n vertices, we have something like p = log(n)/n as a probability above which we expect to get no isolated vertices a.e., and below which a.e. we get an isolated vertex. This case is well documented - however, I can find little to nothing in books or online in the case of specific types of random graph which are, for example, k-connected/k-edge-connected bipartite/tripartite etc.

The case I'm most interested in (at the moment) is bipartite graphs, and I expect that's the next easiest case to understand too, but I can't find documentation anywhere. Is there a simple way to extend the result from normal graphs to bipartite graphs, assuming both vertex sets have the same size? I suppose my concern is that you're obviously looking at a different set of feasible graphs to the general case on 2n vertices, both fewer graphs with an isolated vertex and fewer graphs in total, so it isn't clear to me that we can immediately say the 'proportion' of graphs which have an isolated vertex will necessarily behave the same for large n.

As I mentioned above, I'd be happy to read up on anything anyone could suggest in more restricted cases, I just haven't been able to find it myself, so recommendations will be much appreciated.

Thanks very much!

  • 2
    $\begingroup$ Could you be more specific with your questions? The $k$-connected graphs will hardly have an isolated vertex. $\endgroup$ – Phira Apr 28 '11 at 15:11
  • $\begingroup$ Yes, sorry, I was asking too broad a question and wasn't thinking! Let's just worry about the bipartite graphs for now: suppose we have 2 vertex sets of size n, and we add vertices between each pair with probability p(n) (or p(2n) if you like)): is there a threshold probability function, above which we almost everywhere get no isolated vertex for large values of n, and below which we get an isolated vertex a.e. for large n? I suspect it is related to the non-bipartite case of log(n)/n, but I can't verify whether the function still remains that simple (assuming it exists). $\endgroup$ – Warner B. Apr 28 '11 at 15:36
  • $\begingroup$ If $p$ is smaller than $\log(2n)/2n \sim \log n/2n$, then we certainly have an isolated vertex almost certainly (we can hardly have more edges than in the non-bipartite case). In the other direction, I think that a direct calculation gives a bound of $\log n/n$. $\endgroup$ – Phira Apr 28 '11 at 15:55
  • $\begingroup$ I'll try and make use of Hans' answer below to see if I can obtain a logarithmic bound then; I could see obviously that in 1 direction the bound will just follow from the general case, as you said above, but it was the other which was confusing me; I'll see what I can suss out! Thanks again. $\endgroup$ – Warner B. Apr 28 '11 at 18:19
  • $\begingroup$ I provided an answer for the bipartite case here. $\endgroup$ – joriki Mar 7 '16 at 12:57

EDIT: Sorry - I did not think about threshold functions. I assumed we were working with a constant $p$, thought about the problem, and lost track of the actual question. I don't know how relevant it is, but I'll leave it.

Let $G$ be a bipartite graph on $2n$ vertices with parts $A$ and $B$ with $|A| = |B| = n$.

Let $E_A$ be the event that $A$ has an isolated vertex, $E_B$ be the event that $B$ has an isolated vertex. We're looking for $P(E_A \cup E_B) = P(E_A) + P(E_B) - P(E_A \cap E_B)$.

Each vertex in $A$ has $n$ possible edges, each with independent probability $p$, so the probability that it is isolated is $(1-p)^n$. Summing over the vertices of $A$, the probability that any vertex in $A$ is isolated is $n(1-p)^n$. The case for $B$ having an isolated is clearly symmetric. Hence, $P(E_A) = P(E_B) = n(1-p)^n$.

Now consider $P(E_A \cap E_B) = P(E_A)P(E_B|E_A)$. For any vertex in $B$, we have $n - 1$ possible edges (because we know one of the vertices in $A$ is isolated). The probability that a given vertex in $B$ is isolated is then $(1 - p)^{n - 1}$. Summing over the vertices of $B$, $P(E_B|E_A) = n(1-p)^{n-1}$. So $P(E_A \cap E_B) = (n(1-p)^n)(n(1-p)^{n-1}) = n^2(1-p)^{2n-1}$.

Putting it all together, $P(E_A \cup E_B) = 2n(1-p)^n + n^2(1-p)^{2n - 1}$.

As for a reference, I highly recommend Diestel's Graph Theory, which has an introductory treatment of random graphs (you may be above this level). There's a free preview here - http://diestel-graph-theory.com/. Bollobas' Modern Graph Theory has a similar but slightly deeper treatment. Bollobas also wrote a text called Random Graphs, which I know nothing about, but he is considered a leader in the field. I'm not sure that any of these address your specific problem.

  • $\begingroup$ That's brilliant, I can see how it might tie into a logarithmic threshold function in a way, given that we want n to either dominate $(1-p)^n$ or vice versa for large n: presumably that will give some sort of logarithmic value of p. Taking user9325's comment above into account, how do we evaluate $\lim_{n \to \infty} (1-\frac{log(n)}{n})^n$? Obviously for fixed k, $(1-\frac{k}{n})^n \to e^{-k}$, but the logarithm on top seems to throw a bit of a spanner in the works. $\endgroup$ – Warner B. Apr 28 '11 at 18:17
  • $\begingroup$ @WarnerB I guess you figured it out, but you can estimate $(1-k/n)^{n}$ as tightly as you want by Taylor expansion/inequalities, so long as $k = k(n)$ is not too big. For instance, try $1-\frac{\log n}{n} = \exp(-\frac{\log n}{n} \pm O(\frac{\log^2 n}{n^2}))$. $\endgroup$ – Srivatsan Jul 31 '11 at 13:29
  • $\begingroup$ This is incorrect, because $P(E_A)$ is not $n (1-p)^n$. You are overcounting the cases when more than one vertex of $A$ is isolated, and need to use the principle of inclusion-exclusion. (You can check in the case $n = 2$, $p=1/2$, in which case the probability of an isolated vertex is 9/16, but this formula (corrected to be a difference) gives $4 (1/2)^2 - 4(1/2)^3 = 1/2$. $\endgroup$ – Nick Matteo Apr 24 '13 at 19:32

I can't seem to leave this as a comment so I'm afraid I'll have to leave it as an 'answer'. I've been running simulations on random bipartite graphs of size up to 500x500 (i.e. 2n=1000), and the bounds seem to be out by a factor of two: I get almost no isolated vertices until p=log(500)/500, and above 2log(500)/500 I get a matching every time: between these values I sometimes get a matching and I sometimes don't. I have checked everything and I can't see anywhere whatsoever I could have lost a 2: am I being slow or is it at all possible that we get bounds of double what was anticipated for some reason?

  • $\begingroup$ In fact, it's the upper bound of log(n)/n which seems to be the problem. @user9325, would you mind telling me whether log(n)/n is a guess at the second bound or an actual calculation? $\endgroup$ – Warner B. May 1 '11 at 8:31

For many structured graphs (k-connected/k-edge-connected/bipartite/etc.) the idea of making a graph by adding random edges doesn't make much sense. You can pick a random k-connected graph on n vertices by listing all such graphs and picking one. For bipartite you can do something like you want. Imagine a bipartite graph on $n+m$ vertices, with the $n$ vertices on one side of the split specified in advance. There are then $nm$ candidate edges which you can fill in at random and you can ask about the probability of an isolated vertex. The simplest case is $n=m$, so there are $n^2$ candidate edges, and each vertex has $n$ of them connecting to it.

For a given vertex, if you pick $p$ edges, the probability it is isolated is $$ \frac{(n^2-n)(n^2-n-1)\ldots(n^2-n-p+1)}{n^2(n^2-1)\ldots(n^2-p+1)}=\frac{(n^2-n)!(n^2-p)!}{n^2!(n^2-n-p)!} $$
One approximation is to consider these independent events (ignoring the correlations induced by the fact that an edge that doesn't go to a given vertex does go to another one) and calculate the chance of any vertex being isolated.

  • $\begingroup$ Note that I assumed the number of edges to pick was given, not that each edge is chosen with a given probability. The problems are similar, but there will be dispersion on the picked edges in the second case. Hans was working the other way, which has advantages of independence. $\endgroup$ – Ross Millikan Apr 28 '11 at 16:18
  • $\begingroup$ Yes, though I was looking at the case which Hans addressed, this is still an excellent insight into the different approaches available, so thanks! $\endgroup$ – Warner B. Apr 28 '11 at 18:13

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.