EUVIMEDEUVIMED entdecken
Crossref

Thresholds, Expectation Thresholds and Cloning

Tomasz Przybyłowski, Oliver Riordan

The Electronic Journal of Combinatorics · 27.12.2024 · 31 (4)

DOI: 10.37236/12825 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 27.12.2024. Verfasst von Tomasz Przybyłowski und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Przybyłowski, T., & Riordan, O. (2024). Thresholds, Expectation Thresholds and Cloning. The Electronic Journal of Combinatorics, 31(4). https://doi.org/10.37236/12825

Vancouver

Przybyłowski T, Riordan O. Thresholds, Expectation Thresholds and Cloning. The Electronic Journal of Combinatorics. 2024;31(4). doi:10.37236/12825

BibTeX
@article{Przybyowski2024,
  author = {Przybyłowski, Tomasz and Riordan, Oliver},
  title = {Thresholds, Expectation Thresholds and Cloning},
  journal = {The Electronic Journal of Combinatorics},
  year = {2024},
  volume = {31},
  number = {4},
  doi = {10.37236/12825}
}
Kostenlos starten →