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


Folks, for those who could not make it, a recording of this talk is
available here:
https://youtu.be/ElaaV3OLD9I

Cheers,
Moses

On Wed, May 11, 2022 at 8:27 AM Moses Charikar <moses at cs.stanford.edu>
wrote:

> 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:
> https://stanford.zoom.us/j/98564827425?pwd=QjZkS2RCclBLekpLZmczeGxKeTF2dz09
>
> Cheers,
> Moses
>
> On Fri, May 6, 2022 at 11:02 AM Moses Charikar <moses at cs.stanford.edu>
> 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
>> <https://mathematics.stanford.edu/news/jinyoung-park-and-huy-tuan-pham-prove-kahn-kalai-conjecture>
>> and the Quanta magazine article.
>> <https://www.quantamagazine.org/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425/>
>>
>> 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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220514/a4ce42ba/attachment.html>


More information about the theory-seminar mailing list