Seminars & Colloquia Calendar

Download as iCal file

Mathematical Physics Seminar

Jeffry Kahn - Thresholds vs fractional expectation-thresholds

Jeffry Kahn

Location:  Hill Center Room 705
Date & time: Thursday, 13 February 2020 at 2:00PM - 3:00PM


HILL 705

Jeffry Kahn - Rutgers University

Thursday, February 13th, 2:00pm; Hill 705

"Thresholds vs. fractional expectation-thresholds"

The threshold, p_c(F), for an increasing family F contained in {0,1}^n is the (unique) p for which mu_p(F) = 1/2, where mu_p is the natural p-biased product measure on {0,1}^n.  Thresholds have been central to the study of random discrete structures (e.g. random graphs and hypergraphs) since the work of Erdos and Renyi in 1960, with, in particular, estimation of thresholds for various specific properties the subject of some of the most powerful work in the area.


In 2006, Gil Kalai and I conjectured that a natural lower bound q(F) (the "expectation-threshold") on p_c(F) is never too far from the true value.  In this talk I'll focus on a recent result proving a fractional version of this conjecture suggested about ten years ago by Michel Talagrand.?


This easily implies several previously difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery).  We also resolve (and vastly extend) the ``axial'' version of the random multi-dimensional assignment problem, proving a 2005 conjecture of Martin, Mezard and Rivoire.?


Our approach builds on a recent breakthrough of Alweiss, Lovett, Wu and Zhang on the Erdos–Rado “Sunflower Conjecture.”?


Joint with Keith Frankston, Bhargav Narayanan and Jinyoung Park.

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.