Let $n\geq 1$ be an even number and $d\geq 1$ be integers.
In these notes by Luca Trevisan, we see a procedure of coming up with a $d$-regular on $n$ vertices on the first page.
The procedure is: Let $V=\{1, 2, 3, \ldots, n\}$.
Choose $d$ perfect matchings on $V$ (uniformly?) at random and take the union of these matchings.
It is not clear as to how this procedure gives rise to a $d$-regular graph. Two different matchings can share an edge. So unless we are allowing multiple edges (which I am pretty sure we are not), this does not seem to make sense.
Can somebody clarify what is happening here?
It's possible that the idea in the lecture notes is just to allow parallel edges. But we can achieve an actual reasonable distribution with the same properties by sampling a union of $d$ disjoint matchings, chosen uniformly at random. In practice, this can be done by picking $d$ matchings uniformly and rejecting if an edge appears in more than one of them.
(Note that by default, we must start over from the beginning if this happens; the similar-looking algorithm which goes through the matchings one at a time, and keeps sampling the $i^{\text{th}}$ matching until it is disjoint from the previous $i-1$, does not produce the same distribution. No idea if it produces a sufficiently similar distribution to be worth doing anyway.)
This is a reasonable model for two reasons:
Regarding the first point: the probability that two uniformly chosen edges are equal is $\frac{1}{\binom n2} \sim \frac{2}{n^2}$. In the union-of-$d$-matchings model, there are $\binom d2 n^2$ pairs of edges we have to worry about, so the expected number of collisions is $\binom d2 n^2 \cdot \frac{2}{n^2} = d(d-1)$. These collisions are so close to independent that their distribution is asymptotically Poisson; in particular, the chance of getting no collisions is $e^{-d(d-1)}+o(1)$. This may seem bad, but it is remarkable in that the limit does not depend on $n$.
Regarding the second point: there are several such contiguity results known, which are summarized in these slides. Let $\mathcal G_{n,d}$ be the uniform distribution on $d$-regular graphs. Then the relevant result from these slides is that $\mathcal G_{n,d}$ is contiguous with $\mathcal G_{n,d-1} \oplus \mathcal G_{n,1}$ for all $d\ge 2$, where $\oplus$ denotes this try-it-until-it-works disjoint superposition. As a corollary, $\mathcal G_{n,d}$ is contiguous with $\mathcal G_{n,1}^{\oplus d}$, which is the model used here - because $\mathcal G_{n,1}$ is precisely a uniformly chosen matching.
In particular, though this does not appear to be mentioned in those lecture notes (yet?), proving an a.a.s. expansion result for $\mathcal G_{n,1}^{\oplus d}$ is the same as proving it for $\mathcal G_{n,d}$.
Moreover, proving this result in the union-of-matchings model without resampling if the matchings fail to be disjoint also achieves the same result. Conditioning on an event with probability $e^{-d(d-1)}$ can increase the probability that the graph is not an expander by at most a factor of $e^{d(d-1)}$, and $e^{d(d-1)} \cdot O(\frac{1}{n^2})$ is still $O(\frac{1}{n^2})$.