Dept Banner
Dept Banner

List All Events

Download as iCal file

Mathematical Physics Seminar

The constant in Shamir's Problem

Jeff Kahn - Rutgers University

Location:  Hill 705
Date & time: Thursday, 08 March 2018 at 12:00PM - 1:00PM

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 (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).  I can now show the asymptotically correct statement:  the same behavior holds for any fixed C > 1/r.

Contact Us

HillCenter small

Department of Mathematics

Department of Mathematics
Rutgers University
Hill Center - Busch Campus
110 Frelinghuysen Road
Piscataway, NJ 08854-8019, USA

Phone: +1.848.445.2390
Fax: +1.732.445.5530