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
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:
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/20220511/7ab1e3b9/attachment.html>


More information about the theory-seminar mailing list