4
$\begingroup$

Suppose we have an Erdos random graph with $n$ vertices and $c n$ edges.

What can you say about the probability that the graph is connected?

(More importantly) If it is connected, what is the distribution on the number of bridges?

EDIT:

I am interested in asymptotics as $c$ is fixed but $n \rightarrow \infty$. That is, I know that the probability that the graph is connected is exponentially small in $n$, but I don't know what the exponent is.

As for the number of non-bridges, I would like some result like the number of bridges for a random connected graph is $> c' n$ where $c'$ is another constant, with probability approaching $1$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If $c$ is a fixed constant, then almost surely the graph will contain isolated vertices and hence be disconnected. Indeed it is well-known that $p=\log(n)/n$ is a sharp threshold for connectivity of $G(n,p)$. $\endgroup$
    – Tony Huynh
    Jun 13, 2011 at 16:04
  • $\begingroup$ @David: From the title (I cannot access the paper), this seems promising for the asymptotics of connectivity, or, at the least, useful citations: Robert F. Ling, "An exact probability distribution on the connectivity of random graphs." Journal of Mathematical Psychology, Volume 12, Issue 1, February 1975, Pages 90-98. $\endgroup$
    – Joseph O'Rourke
    Jun 13, 2011 at 16:43

2 Answers 2

Reset to default
1
$\begingroup$

Concerning your first question, if $p$ is the edge probability, then $G(n,p)$ is almost surely connected when $p$ passes the sharp $\ln n/n$ threshold. Because $G$ has about $p \binom{n}{2}$ edges, which in your formulation is $c n$, when $c$ exceeds $c_t=((n-1)/ (2n)) \ln n $, then $G$ is almost surely connected, and below that, will almost surely be disconnected. So if you fix $c$ and let $n \rightarrow \infty$, the threshold $c_t$ grows without bound and your fixed $c$ will be below it, and so $G$ almost surely disconnected.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh, Tony's comment with the same content appeared as I was writing this! $\endgroup$
    – Joseph O'Rourke
    Jun 13, 2011 at 16:23
1
$\begingroup$

The number of isolated vertices has expected value approximately $n e^{-2c}$, so the probability that there are no isolated vertices should be approximately $e^{-n e^{-2c}}$. This should be an upper bound on the probability of connectedness. Better approximations should be attainable by taking into account other ways a graph can be disconnected, e.g. having two vertices connected only to each other.

Improve this answer
$\endgroup$
1
  • $\begingroup$ When c=1, this estimate gives $e−(n∗e−2))≈1.14^{−n}$ while Cayley's formula gives $1.36^{−n}$. So this bound is not tight. $\endgroup$
    – David Harris
    Jun 13, 2011 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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