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
Sat May 14 12:07:58 PDT 2022

Folks, for those who could not make it, a recording of this talk is
available here:


On Wed, May 11, 2022 at 8:27 AM Moses Charikar <moses at>

> 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:
> Cheers,
> Moses
> On Fri, May 6, 2022 at 11:02 AM Moses Charikar <moses at>
> wrote:
>> 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