2020/08/02 by Kahn, Jeff · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2008.01605
For fixed r≥ 3 and n divisible by r, let \mathcal H=\mathcal Hrn,M be the random M-edge r-graph on V=\1,… ,n\; that is, \mathcal H is chosen uniformly from the M-subsets of \mathcal K:=V \choose r (:= \r-subsets of V\). Shamir's Problem (circa 1980) asks, roughly, for what M=M(n) is \mathcal H 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>Crnlog n. More recently the author proved the asymptotically correct version of that result: for fixed C> 1/r and M> Cnlog n, P(\mathcal H ~contains a perfect matching)→ 1 as n→∞. The present work completes a proof, begun in that recent paper, of the definitive "hitting time" statement: Theorem. If A1, … ~ is a uniform permutation of \mathcal K, \mathcal Ht=\A1… At\, and T=min\t:A1∪ ⋯∪ At=V\, then P(\mathcal HT ~contains a perfect matching)→ 1 as n→∞.