Seminars & Colloquia Calendar

_________________________________________

MATHEMATICAL PHYSICS SEMINAR
RUTGERS UNIVERSITY
HILL 705
__________________________________________

Jeffry Kahn - Rutgers University

  Date/Time/Location
Thursday, February 13th, 2:00pm; Hill 705

Title
"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.