Dept Banner
Dept Banner


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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.

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