The $G (n, p)$ model, due to Erdös and Rényi, has two parameters, $n$ and $p$. Here $n$ is the number of vertices of the graph and $p$ is the edge probability. For each pair of distinct vertices, $v$ and $w, > p$ is the probability that the edge $(v,w)$ is present. The presence of each edge is statistically independent of all other edges. The graph-valued random variable with these parameters is denoted by $G(n,p)$. When we refer to “the graph $G(n,p)$”, we mean one realization of the random variable
Random graphs are random variables?
I thought that $G(n,p)$ is a random variable with $\Omega\rightarrow \mathbb{R}$, where $\Omega$ is $\mathcal{P}\{1,...,n\}^2,\mathcal{P}\{\mathcal{P}\{1,...,n\}^2\},1/|\mathcal{P}\{1,...,n\}^2|$ and $G(n,p)(\omega)= |\omega|^p|\{1,...,n\}^2|-|\omega|^{1-p}$. But if that would be the case I don t know how I can formally verify that the event that an edge is present is stochastically independed that an oher edge is present. I have chosen the model to look at all possible sets of edges ie all graphs possible, the author of this paper (J.Spencer) mentioned a graph-valued random variable hence I thought I have to find a probabiliypace where an elemen represents a graph.
If someone could tell me how I can verify the stochastic independence of the existence of two edges and how the random graphs are modeled as random variables I would really appreciate it
Random graphs are a random variable, but not a real-valued random variable: a graph-valued one. $G(n,p)$ is a function from the sample space $\Omega$ to the set of all $2^{\binom n2}$ graphs on a fixed vertex set $\{v_1, v_2, \dots, v_n\}$.
So what's the sample space, then? We could be lazy and just take $\Omega$ to be the same set of graphs, so that $G(n,p)$ is the identity function. Generally, we try not to be too specific about what $\Omega$ is, though, because we might want other sources of randomness involved. We are happy as long as the distribution of $G(n,p)$ is correct: as long as $$\Pr[G(n,p) = G] = p^{|E(G)|} (1-p)^{\binom n2 - |E(G)|}.$$
We might also want to think of the graph evolution process, in which case $\Omega = [0,1]^{\binom n2}$. For each outcome $\omega \in \Omega$, $G(n,p)(\omega)$ includes the $i^{\text{th}}$ edge (order the edges however you like) if $\omega_i < p$. Here, we can define multiple graph valued random variables $G(n,p)$ and $G(n,p')$ in the same probability space.