Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose you have a graph, say a geometric random graph, with $n$ nodes where each link appears with probability $p$. Assuming $E_k$ is the event that the graph has minimum degree $k$, is it possible to find a lower-bound of the form

$$P(E_k) \geq [f(k)]^n \> ?$$

In other words, I'd like to find an expression that allows me to treat the vertices as if they were independent (which is not true).

share|cite|improve this question
I think most people would call this an Erdős–Rényi random graph. – cardinal May 10 '11 at 3:13
There is actually such a thing, a geometric random graph, but I think cardinal is right in assuming you didn't mean it. – Yuval Filmus May 10 '11 at 3:33
@Yuval, on the other hand, I just stumbled onto this MO question, apparently by the OP. – cardinal May 10 '11 at 3:40
@cardinal, there's more than one geometric random graph model, and they all have more than one parameter. – Yuval Filmus May 10 '11 at 3:41
True. I'm tangentially acquainted with Penrose's work. But, the two questions closely spaced in time and the somewhat vague wording in both led me to conjecture the OP just needs to clarify his question. Both for us and for himself. – cardinal May 10 '11 at 3:44
up vote 1 down vote accepted

Perhaps that would be helpful: The Maximum Degree of a Random Graph. Note that minimum and maximum degree are the same (just take $1-p$ instead of $p$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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