3
$\begingroup$

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).

  • 2
    I think most people would call this an [Erdős–Rényi random graph](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).2011-05-10
  • 0
    There is actually such a thing, a geometric random graph, but I think cardinal is right in assuming you didn't mean it.2011-05-10
  • 0
    @Yuval, on the other hand, I just stumbled onto this [MO question](http://mathoverflow.net/questions/64164/k-connectivity-of-a-geometric-random-graph), apparently by the OP.2011-05-10
  • 0
    @cardinal, there's more than one geometric random graph model, and they all have more than one parameter.2011-05-10
  • 0
    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.2011-05-10
  • 0
    in my case I have a geometric random graph: two nodes are connected if their distance is less than $r$.2011-05-10
  • 0
    I guess that my question is that $P(d_i) \geq k$ in place of $f(k)$ is not correct to compute $P(E_k)$, but I was wondering if there was a way to express it as a product in a similar way, possibly a lower bound of $P(E_k)$.2011-05-10

1 Answers 1

1

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$).