Difference between revisions
kahn-kalai
Status and infobox
- status:
—→ solved - tier:
—→ V3 - kind:
—→ problem - year:
—→ 2006 - statement:
—→ The threshold of any monotone graph property is within a log factor of its expectation threshold.
Source +21 −0
+---
+title: Kahn–Kalai conjecture
+kind: problem
+status: solved
+tier: V3
+year: 2006
+authors: Jeff Kahn and Gil Kalai
+statement: The threshold of any monotone graph property is within a log factor of its expectation threshold.
+space: combinatorics
+---
+It says a random structure appears roughly as soon as it is expected to appear. Park and Pham's proof was about six pages. Its shortness surprised the field and came shortly after the related Talagrand conjectures were settled.
+
+*Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.*
+
+Posed 2006, Jeff Kahn and Gil Kalai. Closed 2022, Jinyoung Park and Huy Tuan Pham.
+
+## Sources
+
+- [Quanta Magazine: Elegant six-page proof](https://www.quantamagazine.org/elegant-six-page-proof-reveals-the-emergence-of-random-structure-20220425/)
+
+[[Space:combinatorics|Combinatorics]] · [[Continent:mathematics|Mathematics]]
Revision 40 as rendered
It says a random structure appears roughly as soon as it is expected to appear. Park and Pham's proof was about six pages. Its shortness surprised the field and came shortly after the related Talagrand conjectures were settled.
Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.
Posed 2006, Jeff Kahn and Gil Kalai. Closed 2022, Jinyoung Park and Huy Tuan Pham.