\[lm:large\] For every $\varepsilon>0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left({\overline{\ensuremath{\mathfrak{W}}}}>\Phi(\lambda)+\varepsilon\right)  & = & o\left(\frac 1{N^2}\right)\, .\end{aligned}$$

\[lm:collisions\] For every $\varepsilon>0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(x\in{\ensuremath{\mathcal{R}}},y\in{\ensuremath{\mathcal{R}}}\setminus{\ensuremath{\mathcal{B}}}_x,\sum_{z\in{\ensuremath{\mathfrak{U}}}}{\ensuremath{\mathbf{w}}}(z)<2-\varepsilon\right) & = & o\left(\frac 1{N^2}\right)\, .\end{aligned}$$

Proof of Lemma \[lm:completion\] {#sec:completion}
================================

Combining the representation (\[eq:reversible\]) with the observation (\[wbound\]) yields $$\begin{aligned}
P^{t}(x,\pi(y)) & \geq & \sum_{(u,v)\in{\ensuremath{\mathcal{H}}}_x\times{\ensuremath{\mathcal{H}}}_y}{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v){\bf 1}_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta}{\bf 1}_{\pi(u)=v}.\end{aligned}$$ The right-hand side can be interpreted as the weight of the uniform pairing chosen at the completion stage, provided we define the weight of a pair $(u,v)$ as $$\begin{aligned}
\label{eq:weight-pairing}
{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v){\bf 1}_{u\in{\ensuremath{\mathcal{H}}}_x}{\bf 1}_{v\in{\ensuremath{\mathcal{H}}}_y}{\bf 1}_{{\ensuremath{\mathbf{w}}}(u){\ensuremath{\mathbf{w}}}(v)\leq \theta}.\end{aligned}$$ Lemma \[lm:completion\] now follows from the following general concentration inequality, which we apply conditionally on the exploration stage, with ${\ensuremath{\mathcal{I}}}$ being the set of half-edges that did not get paired, and weights being given by (\[eq:weight-pairing\]).

\[prop:conc\_ineq\_matching\] Let ${\ensuremath{\mathcal{I}}}$ be an even set, $\{w_{i,j}\}_{(i,j)\in {\ensuremath{\mathcal{I}}}\times {\ensuremath{\mathcal{I}}}}$ an array of non-negative weights, and $\pi$ a uniform random pairing on ${\ensuremath{\mathcal{I}}}$. Then for all $a> 0$, $$\begin{aligned}
{\ensuremath{\mathbb{P}}}\left(\sum_{i\in{\ensuremath{\mathcal{I}}}} w_{i,\pi(i)}\leq m-a\right) & \leq & \exp\left\{-\frac{a^2}{4 \theta m}\right\},
$$ where $m=\frac{1}{|{\ensuremath{\mathcal{I}}}|-1}\sum_{i\in{\ensuremath{\mathcal{I}}}}\sum_{j\neq i}w_{i,j}$ and $\theta=\max_{i\neq j}(w_{i,j}+w_{j,i})$.

Note that in our case, $m  =  \frac{{\ensuremath{\mathfrak{W}}}}{|{\ensuremath{\mathcal{I}}}|-1}$. Lemma \[lm:completion\] follows easily by taking $a=\frac{\varepsilon}{|{\ensuremath{\mathcal{I}}}|-1}$ and observing that $|{\ensuremath{\mathcal{I}}}|-1\leq N$ and ${\ensuremath{\mathfrak{W}}}\leq 1$.

We exploit the following concentration result for Stein pairs due to @chatterjee2007stein (see 