0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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.$$ $\endgroup$
    – user22980
    Apr 2, 2013 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.