Hitting times for Shamir’s Problem

Combinatorics Seminar
Event time: 
Thursday, September 27, 2018 - 8:00pm
DL 431
Jeff Kahn
Speaker affiliation: 
Rutgers University
Event description: 

Shamir’s Problem (circa 1980) asks:  for fixed $r\geq 3$ and $n$ a (large) multiple of $r$, how large should $M$ be so that $M$ random $r$-subsets of $\{1\dots n\}$ are likely to include a perfect matching (that is, $n/r$ disjoint $r$-sets)?  About ten years ago Johansson, Vu and I proved the natural conjecture that this is true if $M>C n\ln n$, for some large $C=C_r$.  Some listeners may have heard me speak some months ago on the asymptotically precise statement:  the same behavior holds for any fixed $C> 1/r$.  Here we’ll discuss the definitive “hitting time” version.

Research Area(s):