Event time:
Thursday, September 27, 2018 - 8:00pm
Location:
DL 431
Speaker:
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):