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?



Random graph uniformly sample from the special graphs
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.


