Thresholds, Expectation Thresholds and Cloning
Let $p_\mathrm{c}$ and $q_\mathrm{c}$ be the threshold and the expectation threshold, respectively, of an increasing family $\mathcal{F}$ of subsets of a finite set $X$, and let $l$ be the size of a largest minimal element of $\mathcal{F}$. Recently, Park and Pham proved the Kahn–Kalai conjecture, which says that $p_\mathrm{c} \le K q_\mathrm{c} \log_2 l$ for some universal constant $K$. Here, we slightly strengthen their result by showing that $p_\mathrm{c} \le 1 - \mathrm{e}^{-K q_\mathrm{c} \log_2 l}$. The idea is to apply the Park-Pham Theorem to an appropriate "cloned" family $\mathcal{F}_k$, reducing the general case (of this and related results) to the case where the individual element probability $p$ is small.
Authors
- Oliver Riordan (ORCID: https://orcid.org/0000-0002-2934-8065)
- Tomasz Przybyłowski (ORCID: https://orcid.org/0009-0002-9757-8652)
Institutions
- University of Oxford (GB)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2024-12-26
- DOI
- https://doi.org/10.37236/12825
- Citations
- 1
- Primary Topic
- Neural Networks and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.35
Funders
- Engineering and Physical Sciences Research Council
- Division of Mathematical Sciences