I have some problems understanding the theory of random graphs, in particular I have two questions:
- $G(n,p)$ define a probability space where the sample space is $\mathcal{G}_n$, the set of all simple graphs with vertex set $\{1,...,n\}$, because $\mathcal{G}_n$ is finite all subsets of the sample space are taken to be measurable and the probability measure is \begin{align*} \mathbb{P}(G_0)=\mathbb{P}(G=G_0)= p^{m}(1-p)^{{n \choose 2}-m} \end{align*} $G_0 \in \mathcal{G}_n, \ p \in [0,1]$, where $m$ is the number of edges of $G_0$.
Is it right ? How can I proof that this $\mathbb{P}$ is a probability measure ? Of course it is positive...
2)When I say "the random graph $G(n,p)$", what am I considering? In point 1) I have a probability space, so I think that "the random graph $G(n,p)$" is a possible outcome of a random variable $G \sim G(n,p)$, where I interpret $\mathbb{P}(G_0)$ as the probability to obtain $G_0$ from $G(n,p)$. For example, when the random graph $G(n,p)$ is connected w.h.p., which graph am I talking about?
Sorry if the questions are confusing, but my ideas are a bit confused too. Thank you all.
$G(n, p)$ is a probability distribution on $\mathcal G_n$ in the same way that $N(0, 1)$ is a probability distribution on $\mathbb R$.
The phrase 'with high probability' has special meaning in random graph theory. Normally $p$ is a function of $n$. Then we say $G(n, p(n))$ is connected w.h.p. if $$ \lim_{n \to \infty} \mathbb P(\text{$G_n$ is connected}) \to 1$$ where $G_n \sim G(n, p(n))$.
A more intuitive way to understand $G(n, p)$ is that if $G \sim G(n, p)$ then each of the $\binom{n}{2}$ edges of $K_n$ are included in $G$ independently with probability $p$. This leads to the formula for $\mathbb P$ that you have.