# Two different definitions of Erdos-Rényi random graph

There are two or more ways to define an Erdos-Rényi random graph. Let consider the following two:

1) $G_n=(V_n,E_n)$ with vertex set $V_n=(1,\dots,n)$ and edge set $E_n=(ij\in\mathcal{P}_2(V_n)\ |\ \epsilon_{ij}=1)$, where $(\epsilon_{ij})_{ij}$ are i.i.d. random variables with distribution Bernoulli($2c/(n-1)$).

2) $G_n^*=(V_n,E_n^*)$ with (multi)-edge set $E_n^*=(i_1j_1,\ i_2j_2,\ \dots,\ i_mj_m)$ where $m=[cn]$ and $(i_s)_s\cup(j_s)_s$ are i.i.d. random vertices uniformly chosen in $V_n$

Notice that $G_n^*$ is in general a multigraph, i.e. it admits self-loops and multi-edges, whilest $G_n$ is a simple graph. Notice that $G_n^*$ has a deterministic number $m=[cn]$ of edges, while $G_n$ has a random number of edges whose expected value is $cn$.

I read that $$G_n\ \overset{d}{=}\ G_n^*\ |\ ''G_n^*\ \text{is simple}''$$ and that $$\mathbb{P}(G_n^*\ \text{is simple})\geq\delta>0\ \ \forall n\in\mathbb{N}.$$

Could you help me to prove this two fact, or tell me where I can find a proof?

Edit. The two distributions can't be equal at fixed $n$ (see Greg Martin's answer). But I hope they're asymptotically equivalent.

If this can help, I think the law of $G_n^*$ conditionally on ($G_n^*$ simple) is the uniform distribution on the set $\mathcal{G}_{n,m}$ of simple graphs with vertex set $V_n$ and $m$ edges.

If I understand the first fact correctly, I find it hard to believe how it could be true. As you say, $G_n$ is unlikely to have exactly $[cn]$ edges, while the right-hand side always does.
As for the second fact: Think of choosing the edges for $G_n^*$ one at a time, and what could happen to make the graph not simple. For the first edge, there is an $n/n^2$ probability that we get a loop; so there's a $1-1/n$ probability of being simple after the first edge. For the second edge, we have the same $n/n^2$ chance of getting a loop, and an additional $2/n^2$ chance of repeating the first edge ($2$ because we could swap the endpoints); so there's a $(1-1/n)(1-1/n-2/n^2)$ probability of the graph being simple after the second edge. Continuing in this way, we see that the probability of the graph being simple after all $m$ edges are placed is $$\prod_{j=0}^{m-1} \bigg( 1 - \frac1n - \frac j{n^2} \bigg).$$ This can be bounded below:
$$\prod_{j=0}^{m-1} \bigg( 1 - \frac1n - \frac j{n^2} \bigg) \ge \bigg( 1 - \frac{n+m-1}{n^2} \bigg)^m \ge \bigg( 1-\frac{c+1}n \bigg)^{cn}.$$ This last quantity tends to $e^{-c(c+1)}$ as $n$ goes to infinity; in particular, it is bounded below uniformly for $n$ sufficiently large in terms of $c$. (That's the best we can hope for: if $c=100$, then there's no chance that the $G_n^*$ graph is simple if $n\le200$ - there aren't enough distinct edges.)
• Thank you very much for your answer. The second part is exactly what I was looking for. For the first part you are certainly right: at fixed $n$ no hope the two distributions are the same. But is it possible to say that they are asymptotically equivalent? e.g. $$\mathbb{P}(G_n=g)-\mathbb{P}(G_n^*=g|G_n^*\text{simple})\xrightarrow[n\to\infty]{}0$$ or $$\mathbb{P}(G_n=g)/\mathbb{P}(G_n^*=g|G_n^*\text{simple})\xrightarrow[n\toinfty]{}1.$$ – user22980 Apr 2 '13 at 22:24