2025/08/19 by Dubroff, Quentin, Kahn, Jeff, Park, Jinyoung
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2508.14269
We make progress on a conjecture of Kahn and Kalai, the original (stronger but less general) version of what became known as the ``Kahn-Kalai Conjecture" (KKC; now a theorem of Park and Pham). This ``second" KKC concerns the threshold, pc(H), for Gn,p to contain a copy of a given graph H, predicting pc(H) = O(p\mathbb E(H)log n), where p\mathbb E is an easy lower bound on pc. What we actually show is p\mathbb E^*(H)=O(p\mathbb E(H)log 2n), where p\mathbb E^*, the fractional expectation threshold, is a larger lower bound suggested by Talagrand. When combined with Talagrand's fractional relaxation of the KKC (now a theorem of Frankston, Kahn, Narayanan and Park), this gives pc(H)=O(p\mathbb E(H)log3 n). (The second KKC would follow similarly if one could remove the log factors from the above bound on p\mathbb E^*.)