Down‐set thresholds
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.
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}
}
EUVIMED