5
$\begingroup$

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!

  • 0
    I provided an answer for the bipartite case [here](http://math.stackexchange.com/questions/369830).2016-03-07

3 Answers 3

2

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.

  • 0
    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$.2013-04-24
2

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.

  • 0
    Yes, though I was looking at the case which Hans addressed, this is still an excellent insight into the different approaches available, so thanks!2011-04-28
2

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?

  • 0
    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?2011-05-01