Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 12 / 3

Put $M=2m$ and $a_i=\left(\genfrac{}{}{0ex}{}{d_i}{2}\right)$. Use the configuration model: give vertex $i$ exactly $d_i$ labelled half-edges and choose a uniform perfect matching of all $M$ half-edges. There arepairings, with $(2m{)}_m$ denoting a falling factorial. Each allowed simple graph has exactly ${\prod }_i{d}_i!$ representations: at every vertex, assign its incident graph edges bijectively to its labelled half-edges. Therefore its enumeration reduces to the probability that a pairing is simple and avoids $G_0$.

Count three kinds of prescribed bad patterns. A loop pattern consists of a pair of half-edges at one vertex. A double-edge pattern consists of two half-edges at each of two distinct vertices and one of their two cross-pairings. A forbidden-edge pattern consists of one half-edge at each endpoint of an edge of $G_0$. Let their respective counts in the random pairing be $Z_L,Z_D,Z_F$. Simplicity and avoidance are equivalent to $Z=Z_L+Z_D+Z_F=0$, including exclusion of triple edges because those contain double-edge patterns.

A prescribed collection of $t$ disjoint half-edge pairs occurs with probabilityConsequently the bad-pattern expected values areHere $\lambda =({\sum }_i{a}_i)/m$ and $\mu =M^{-1}{\sum }_{ij\in E(G_0)}{d}_i{d}_j$, as in the PDF. Since $1\le d_i\le \Delta$ and $G_0$ has bounded maximum degree, $M=\Theta (n)$ and all three means are uniformly bounded. For the double-edge estimate, ${\sum }_i{a}_i^2=O(n)$, so its contribution after division by $M^2$ is $o(1)$.

We now give the moment-counting step rather than assume independence. For each fixed $h$, expand the factorial moment $\mathbb{E}(Z{)}_h$ as the sum over ordered distinct bad patterns. Collections on disjoint vertex sets have, by the displayed pairing probability, joint probabilities equal to the product probabilities times $1+O(1/n)$. Their total contribution isDeleting collections with a shared vertex changes the independent-product sum by $O(1/n)$, since all ordinary and forbidden vertex degrees are bounded.

For actual joint probabilities of overlapping patterns, incompatible uses of a half-edge give zero. Compatible collections with no shared paired edge lose at least one free vertex choice, without reducing the number of required pairs, so contribute $O(1/n)$. A shared paired edge can occur only between two double-edge patterns or between a double-edge pattern and a forbidden-edge pattern. In the first case their union requires at least three parallel paired edges: there are $O(n^2)$ endpoint choices and probability $O(n^{-3})$. In the second case the endpoint pair must be an edge of $G_0$: there are only $O(n)$ choices and at least two required pairs, giving $O(n^{-1})$. Adding further patterns in a fixed collection does not remove this deficit: a disjoint addition contributes bounded order, while an addition to an existing cluster has only bounded half-edge choices unless it supplies new free vertices, compensated by its new required pairs. Summing the finitely many overlap types for fixed $h$ therefore gives $o(1)$. Thus, with $\Lambda =\lambda /2+{\lambda }^2/4+\mu$,The Bonferroni inequalities bracket $\mathrm{Pr}(Z=0)$ by the odd and even partial sums of ${\sum }_h(-1{)}^h\mathbb{E}(Z{)}_h/h!$. The means $\Lambda$ are bounded, so the corresponding exponential-series remainders vanish uniformly as the truncation increases. Taking $n\to \infty$ and then the truncation to infinity proves the bounded-degree pairing avoidance estimate $\mathrm{Pr}(Z=0)=e^{-\Lambda }+o(1)$. This does not require $\lambda$ or $\mu$ to converge. The exponential is bounded away from zero, so the additive error is also a relative $o(1)$ error.

Multiplying by the pairing count and dividing by the representation factor givesThe factor $(2m{)}_m$ multiplies the exponential; it is not part of its exponent. The TeX aid misgroups this factor, whereas the original PDF is unambiguous. The bounded-degree proof also covers the stated additional assumption $2m-n\to \infty$.

Begin with the configuration model for $n$ labelled vertices of degree $r$. Let $Y_{\ell }$ count cycles in a graph with specified paired edges, so parallel-edge choices are counted separately before conditioning. Choose a cyclic ordering of $\ell$ distinct vertices in $(n{)}_{\ell }/(2\ell )$ ways, where division by $2\ell$ removes rotation and reversal. At each vertex choose an ordered pair of distinct half-edges for the entering and leaving edges, in $r(r-1)$ ways. These $\ell$ prescribed pairs appear with the pairing probability from part (i), givingIt remains to justify conditioning on simplicity: merely dividing by a positive simplicity probability would give an incorrect constant.

Unconditionally, part (i) with no forbidden graph has $\lambda =r-1$, soCondition on one specified cycle pairing. The unpaired half-edges form a uniform configuration model with degree $r-2$ at its $\ell$ vertices and degree $r$ elsewhere. A completion of the full graph is simple exactly when the residual graph is simple and has no additional edge along one of the already prescribed cycle edges. This forbidden graph has maximum degree two. Because $r,\ell$ are fixed,After permuting labels if needed to sort the degrees, the assumptions of part (i) still hold, including residual degrees at least one. Its bounded-degree pairing avoidance estimate therefore shows thatThis ratio is the same for each prescribed cycle, by symmetry. Sum over their indicators to obtain $\mathbb{E}(Y_{\ell }\mid \text{simple})=(1+o(1))\mathbb{E}{Y}_{\ell }$. Conditioning is uniform over all simple $r$-regular graphs because each has $(r!{)}^n$ pairing representations. On simplicity, $Y_{\ell }$ is the ordinary cycle count. Hence the short-cycle expectation in a uniform regular graph is