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!

  • 2
    Could you be more specific with your questions? The $k$-connected graphs will hardly have an isolated vertex.2011-04-28
  • 0
    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).2011-04-28
  • 0
    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$.2011-04-28
  • 0
    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.2011-04-28
  • 0
    I provided an answer for the bipartite case [here](http://math.stackexchange.com/questions/369830).2016-03-07

3 Answers 3