Relation between random graph models $G^{(B)}_{n,m}$ and $G_{n,m}$

Question

In Frieze, Alan; Karoński, Michał, Introduction to random graphs, in Section 1.3 Pseudo-Graphs, there is a model of random multi-graphs, which is denoted as $\mathbb{G}^{(B)}_{n,m}$.

Def. A random multi-graph $\mathbb{G}^{(B)}_{n,m}$ contains $m$ edges, where every edge is chosen uniformly at random and independently from ${[n] \choose 2}$.

It is also shown in the same section that $\mathbb{G}^{(B)}_{n,m}$ and $\mathbb{G}_{n,m}$ are equivalent, when $m = O(n)$. ($\mathbb{G}_{n,m}$ is the simple random graph with $m$ edges.) The equivalence is in the sense that for a graph property $\mathcal{P}$, if $\mathbb{P}(\mathbb{G}^{(B)}_{n,m} \in \mathcal{P}) = o(1)$, then $\mathbb{P}(\mathbb{G}_{n,m} \in \mathcal{P}) = o(1)$, for $m = O(n)$.

My question is what happens in the case when $m = \omega(n)$? For example, $\mathbb{G}_{n,m}$ is connected a.a.s. when $m = \frac{1}{2}(n\log{n} + \omega(1))$. What about $\mathbb{G}^{(B)}_{n,m}$?

Answer 1

The relation between $\mathbb{G}_{n,m}$ and $\mathbb{G}^{(B)}_{n,m}$ is not quite an equivalence. All we have is that if the random multigraph does not have a property almost surely, then the random simple graph also does not have this property, within the range $m=O(n)$. The reason essentially is that is within this range, $m$ is so small that there is a constant probability that the random multigraph turns out to be a simple graph. However, the converse implication need not hold, for example for the graph property "The graph is not simple" will hold with probability $0$ for the simple random graph, but not necessarily for the random multigraph.

For larger values of $m$, $\mathbb{G}^{(B)}_{n,m}$ will become non-simple, so there wouldn't be any natural implications anymore. For the specific question you ask, I think Theorem 4.2 from the same book ($\mathbb{G}_{n,m}$ becomes connected precisely when no isolated vertices remain) can give you an answer, provided that the same result holds for $\mathbb{G}_{n,m}^{(B)}$. I haven't read through the entire proof carefully to check this, but I would be very surprised if it did not generalize for some reason.