EUVIMEDEUVIMED entdecken
Crossref

Down‐set thresholds

Benjamin Gunby, Xiaoyu He, Bhargav Narayanan

Random Structures & Algorithms · 2023-09 · 63 (2) · 442-456

DOI: 10.1002/rsa.21148 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 12.04.2023. Verfasst von Benjamin Gunby und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 16 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitieren

Abstract (Originalsprache)

We elucidate the relationship between the threshold and the expectation‐threshold of a down‐set. Qualitatively, our main result demonstrates that there exist down‐sets with polynomial gaps between their thresholds and expectation‐thresholds; in particular, the logarithmic gap predictions of Kahn–Kalai and Talagrand (recently proved by Park–Pham and Frankston–Kahn–Narayanan–Park) about up‐sets do not apply to down‐sets. Quantitatively, we show that any collection of graphs on that covers the family of all triangle‐free graphs on satisfies the inequality for some universal , and this is essentially best‐possible.

Förderung

  • National Science Foundation

Zitieren

APA

Gunby, B., He, X., & Narayanan, B. (2023). Down‐set thresholds. Random Structures & Algorithms, 63(2), 442-456. https://doi.org/10.1002/rsa.21148

Vancouver

Gunby B, He X, Narayanan B. Down‐set thresholds. Random Structures & Algorithms. 2023;63(2):442-456. doi:10.1002/rsa.21148

BibTeX
@article{Gunby2023,
  author = {Gunby, Benjamin and He, Xiaoyu and Narayanan, Bhargav},
  title = {Down‐set thresholds},
  journal = {Random Structures & Algorithms},
  year = {2023},
  volume = {63},
  number = {2},
  pages = {442--456},
  doi = {10.1002/rsa.21148}
}
Kostenlos starten →