Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Kahn-Kalai conjecture proof: today, 2:30pm

Moses Charikar moses at
Wed May 11 08:27:56 PDT 2022

Theory friends,

Quick reminder that we have a special theory seminar by Huy Pham today,
2:30-4:30pm in Gates 415, on the proof of the Kahn-Kalai conjecture. See
details below.

A white board talk is much better in person, but for those who would like
to follow along remotely, here is a zoom link:


On Fri, May 6, 2022 at 11:02 AM Moses Charikar <moses at>

> Theory friends,
> For those of you who missed Huy Pham's combinatorics seminar talk last
> week about the breakthrough result on the Kahn-Kalai conjecture as well as
> those who attended and would like to hear more details ... we've arranged
> for him to give a 2 hour theory seminar next week so he can go over the
> short and elegant proof. The talk will be self contained. Abstract below.
> When: Wed May 11, 2:30-4:30pm
> Where: Gates 415
> You can read about the result in the Math dept news blurb
> <>
> and the Quanta magazine article.
> <>
> Cheers,
> Moses
> Title: A proof of the Kahn-Kalai conjecture
> Abstract: In this session, I will describe in detail the proof of the
> Kahn-Kalai conjecture in the recent joint work with Jinyoung Park. This
> conjecture concerns the threshold of an increasing boolean function (or of
> an increasing graph property), which is the density at which a random set
> (or a random graph) transitions from unlikely satisfying to likely
> satisfying the function (or property). Kahn and Kalai conjectured that for
> any nontrivial increasing property on a finite set, its threshold is never
> far from its "expectation-threshold," which is a natural (and often easy to
> calculate) lower bound on the threshold. The Kahn-Kalai conjecture directly
> implies a number of difficult results in probabilistic combinatorics and
> random graph theory, such as Shamir’s problem on hypergraph matchings, or
> the threshold for containing a bounded degree spanning tree.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list