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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Thresholds, Expectation Thresholds and Cloning

Oliver Riordan, Tomasz Przybyłowski
1 citations
The Electronic Journal of Combinatorics
Neural Networks and Applications
0.35
article

Thresholds, Expectation Thresholds and Cloning

Oliver Riordan, Tomasz Przybyłowski
article en
1 citations

Abstract

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.

The Electronic Journal of CombinatoricsVol. 31(4)
University of Oxford (GB)
Engineering and Physical Sciences Research Council, Division of Mathematical Sciences
Openalex Percentile: Top 30%
Neural Networks and Applications
0.35
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.