- This event has passed.
Simons Institute Event: Breakthroughs – Thresholds with Jinyoung Park (Stanford University)
Registration is required to attend
For a finite set X, a family F of subsets of X is said to be increasing if any set A that contains B in F is also in F. The p-biased product measure of F increases as p increases from 0 to 1, and often exhibits a drastic phase transition around a specific value, which is called a "threshold." Thresholds of increasing families have been of great historical interest and a central focus of the study of random discrete structures (e.g. random graphs and hypergraphs), with estimation of thresholds for specific properties the subject of some of the most challenging work in the area. In 2006, Kahn and Kalai conjectured that a natural (and often easy to calculate) lower bound q(F) (which we refer to as the “expectation-threshold”) for the threshold is in fact never far from its actual value. The positive answer to this conjecture enables one to narrow down the location of thresholds for any increasing properties in a tiny window. In particular, this easily implies several previously very difficult results in probabilistic combinatorics such as thresholds for perfect hypergraph matchings (Johansson–Kahn–Vu) and bounded-degree spanning trees (Montgomery). In this talk, I will present the recent resolution of the Kahn-Kalai Conjecture, along with some preceding work around this topic.
Based on joint work with Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Huy Tuan Pham.
Breakthroughs is a lecture series highlighting major new developments in theoretical computer science and is geared toward a scientific audience.
If you require accommodation for communication, please contact our access coordinator at firstname.lastname@example.org with as much advance notice as possible.
This event is made possible in part by a grant from the Simons Foundation.