Seminars & Colloquia Calendar
Hitting times for Shamir's Problem
Jeff Kahn, Rutgers
Location: Hill 705
Date & time: Monday, 01 April 2019 at 2:00PM - 3:00PM
| Abstract: | Shamir's Problem (circa 1980) asks: for fixed r at least 3 and n a (large) multiple of r, how large should M be so that M random r-subsets of {1, ... ,n} are likely to contain a perfect matching (i.e., 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 talk a while back on the asymptotically precise statement: the same behavior holds for any fixed C> 1/r. Here I'll try to say something about the definitive ``hitting time" version. |
|---|
