Jeffry Kahn – Rutgers University
Date/Time/Location
Thursday, January 29th, 2026, 12:10 pm; Hill Center 705
Thresholds for graph containment
Thresholds have been central to the study of random graphs and related structures since its initiation by Erdos and Renyi in 1960. E.g. a prototypical question is (roughly): for the usual binomial (or
"Erdos-Renyi") random graph G=G(n,p), how large should p=p(n) be to make it likely (as n tends to infinity) that G contains a copy of a given graph H (which may depend on n)?
For this talk I'll mainly focus on such graph containment questions, mostly filling in background, but hopefully also managing to say a little about recent progress on a (still very open) conjecture of Gil Kalai and myself, to the effect that the threshold is always within a logarithmic factor of a relatively easy lower bound, sometimes called the expectation threshold.
Joint with Quentin Dubroff and Jinyoung Park.