Hitting times for Shamir’s problem

Abstract:

For fixed $r\geq 3$ and $n$ divisible by $r$, let $\boldsymbol {\mathcal {H}}=\boldsymbol {\mathcal {H}}^r_{n,M}$ be the random $M$-edge $r$-graph on $V=\{1,\ldots ,n\}$; that is, $\boldsymbol {\mathcal {H}}$ is chosen uniformly from the $M$-subsets of $\mathcal {K}≔{{V}\choose {r}}$ ($≔\{\text {$r$-subsets of$V$}\}$). Shamir’s Problem (circa 1980) asks, roughly, \[ \text {\emph {for what $\boldsymbol {M=M(n)}$ is }} \boldsymbol {\mathcal {H}} \text {\emph { likely to contain a perfect matching}} \] (that is, $n/r$ disjoint $r$-sets)?

In 2008 Johansson, Vu and the author showed that this is true for $M>C_rn\log n$. More recently the author proved the asymptotically correct version of that result: for fixed $C> 1/r$ and $M> Cn\log n$, \[ \mathbb {P}(\boldsymbol {\mathcal {H}} ~\text {\emph {contains a perfect matching}})\rightarrow 1 \,\,\, \text {\emph {as} $n\rightarrow \infty $}. \]

The present work completes a proof, begun in that recent paper, of the definitive “hitting time” statement:

Theorem. If $A_1, \ldots ~$ is a uniform permutation of $\mathcal {K}$, $\boldsymbol {\mathcal {H}}_t=\{A_1,\ldots ,A_t\}$, and \[ T=\min \{t:A_1\cup \cdots \cup A_t=V\}, \] then $\mathbb {P}(\boldsymbol {\mathcal {H}}_T ~\text {contains a perfect matching})\rightarrow 1 \,\,\, \text {\emph {as}$n→∞$}$.