Thresholds, expectation thresholds and cloning

Journal article

Let pc and qc be the threshold and the expectation threshold, respectively, of an increasing family F of subsets of a finite set X, and let l be the size of a largest minimal element of F. Recently, Park and Pham proved the Kahn–Kalai conjecture, which says that pc ≤ Kqc log2 l for some universal constant K. Here, we slightly strengthen their result by showing that pc ≤ 1 − e−Kqc log 2l . The idea is to apply the Park–Pham Theorem to an appropriate ‘cloned’ family Fk, reducing the general case (of this and related results) to the case where the individual element probability p is small.

Authors: Przybyłowski, T; Riordan, O

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Electronic Journal of Combinatorics
• Journal: Electronic Journal of Combinatorics
• Volume: 31
• Issue: 4
• Article number: P4.74
• Publication date: 2024-12-27
• Acceptance date: 2024-10-24
• DOI: 10.37236/12825
• EISSN: 1077-8926
• Language: English