Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Added definition of $\mathbb{G}_{n,m}$ and corrected a typo
Source Link

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

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)$. The equivalence is in a 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}$?

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

Source Link
Victor
  • 655
  • 3
  • 11

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

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)$. The equivalence is in a 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}$?