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):