Seminar Details
Hitting Times for Shamir's Problem
- Start Date: April 1, 2019
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Jeff Kahn - Rutgers University
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- 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.