[theory-seminar] Kahn-Kalai conjecture proof: Wed May 11, 2:30pm

[Moses Charikar]

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/20220506/f5e03d31/attachment.html>