2
$\begingroup$

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}$?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.