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

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