1
$\begingroup$

We know two basic random graph models:$G(n,p)$ and $G(n,m)$. $G(n,m)$ consists of all graphs with $n$ vertices and $m$ edges, in which the graphs have the same probability. We know that $G(n,p)$ and $G(n,m)$ are asymptotically equivalent when $C_n^2 p=m$. So when we want to calculate the probability of some property in $G(n,m)$, we can calculate it in $G(n,p)$, which is much easier.

Now, if we wang to study the random graph that consists of all graphs that have some property(such as all graphs that are $d$-regular graph with $\chi'=d$), in which the graphs have the same probability, we don't have similar asymptotic equivalence, how do we calculate the probability of some property? Are there any papers that study similar random graph models?

Improve this question
$\endgroup$
1
  • $\begingroup$ Certainly there are many papers about uniform regular graphs, look for Bollobas' "Random graphs". $\endgroup$
    – Fedor Petrov
    Commented May 27, 2023 at 13:28

1 Answer 1

Reset to default
1
$\begingroup$

There is a notion of contiguity for models of graphs. Two sequences of probability spaces $$\{(\Omega_n, \mathcal{F}_n, P_n)\}_{n\in\mathbb{N}} \text{ and } \{(\Omega_n, \mathcal{F}_n, \tilde{P}_n)\}_{n\in\mathbb{N}}$$ (with the same underlying measurable spaces $(\Omega_n, \mathcal{F}_n)$) are contiguous if any event that occurs in the first sequence with probability $1$ as $n\to \infty$ also occurs in the second sequence with probability $1$ as $n \to \infty$.

There are several papers about models for random $d$-regular graphs that are contiguous with the uniform model. One of these models is the following: take $d$ random matchings on the vertex set $[n]$ (assuming $n$ is even). Assuming they have no joint edges, take their union. If they do have some common edges, try to generate random matchings again. Graphs in this model all have $\chi' = d$ (give each matching a different color).

See Wormald's survey on models of random regular graphs, and also:

S. Janson, Random regular graphs: Asymptotic distributions and contiguity, Combinatorics, Probability and Computing, 4 (1995), 369–405.

M. Molloy, H. Robalewska, R. W. Robinson & N. C. Wormald, 1- factorisations of random regular graphs, Random Structures & Algorithms, 10 (1997), 305–321.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thank you! I think contiguity is equals asymptotically equivalent, that is, $P(G_1\in Q )=1$ as $n$ tends to inifinity $\rightarrow $ $P(G_2\in Q)=1$ as $n$ tends to inifinity for some property $Q$. $\endgroup$
    – Yuhang Bai
    Commented May 28, 2023 at 14:02
  • $\begingroup$ @zhukuibai I'm not so familiar with the terminology, but if that's the case the statement about $G(n,p)$ in your question seems inaccurate: the probability that $G(n,p)$ will have exactly $m={n \choose 2}p$ edges goes to $0$ as $n\to \infty$, so a sequence of the form $\{G(n_i, p_i)\}_i$ can't be contiguous with one of the form $\{G(n_i, m_i)\}_i$ if $n_i \to \infty$ as $i \to \infty$. $\endgroup$
    – Geva Yashfe
    Commented May 29, 2023 at 16:53
  • $\begingroup$ In fact, $m \approx C_n^2p$ is enough. Here, always $p=p(n), m=m(n)$. We have $C_n^2p \approx m$ and So $C_n^2p \neq 0$. Then I think that the form ${G(n_i,p_i)}$ can be contiguous with one of the form ${G(n_i,m_i)}$. $\endgroup$
    – Yuhang Bai
    Commented May 30, 2023 at 2:22
  • $\begingroup$ @zhukuibai I think this can't work: take $p=\frac{1}{2}$, define $m_i$ as you suggest, and for each $i$ let $E_i$ be the event that $G$ has precisely $m_i$ edges. Then in the sequence $\{G(n_i,p_i)\}_i$ we have $\lim_i P(E_i) = 0$, because the number of edges has a binomial distribution and $P(E_i) < \frac{1}{\sqrt{m_i}}$ for large enough $i$. But in the sequence $\{G(n_i, m_i)\}_i$ we have $\lim_i P(E_i) = 1$. $\endgroup$
    – Geva Yashfe
    Commented May 30, 2023 at 9:23
  • $\begingroup$ Why $P(E_i)<\frac{1}{\sqrt{m_i}}$? $\endgroup$
    – Yuhang Bai
    Commented May 30, 2023 at 9:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .