Configuration model

For a prescribed degree sequence with even sum $M={\sum }_i{d}_i$, attach $d_i$ labelled half-edges to vertex $i$ and choose a uniform perfect matching of the $M$ half-edges. Each pair becomes an edge, giving a multigraph that may have self-loops or parallel edges. The number of pairings is $M!/[2^{M/2}(M/2)!]$. Every simple graph with that degree sequence has exactly ${\prod }_i{d}_i!$ pairing representations, so conditioning on simplicity produces the uniform simple-graph model.

For bounded vertex degrees, total degree $M\to \infty$, and a forbidden graph $G_0$ of bounded maximum degree, put $\lambda =M^{-1}{\sum }_i{d}_i(d_i-1)$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$. Count prescribed loop pairs, double-edge pairs, and forbidden-edge pairs in the configuration model. Their means are respectively $\lambda /2+o(1)$, ${\lambda }^2/4+o(1)$, and $\mu +o(1)$. A fixed collection of $t$ disjoint prescribed pairs occurs with probability $[(M-1)(M-3)\cdots (M-2t+1){]}^{-1}$. Bounded degrees make intersecting bad configurations contribute $O(M^{-1})$ to each fixed factorial moment. Thus the total bad-pattern count has factorial moments $(\lambda /2+{\lambda }^2/4+\mu {)}^j+o(1)$. The Bonferroni inequalities and uniformly bounded means give the displayed zero-pattern probability, without requiring the parameters to converge.

A half-edge records an incidence of an edge at a vertex. Two half-edges form each edge, including two incidences at the same vertex for a self-loop. In the configuration model these incidences are individually labelled before random pairing.