Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

Fractional expectation thresholds and the "second" Kahn-Kalai conjecture

  • Tuan Tran
Open at sourcePDFDOICite

Abstract

We show that the uniform probability measure on copies of a nonempty graph H in Kn is CqHlog(2e(H))-spread, where qH is its graphic expectation threshold. Consequently, the fractional expectation threshold of H is at most CqHlog(2e(H)). We remove the logarithmic factor for trees and for graphs whose average degree is at least the logarithm of their maximum degree. This proves the ``second'' Kahn-Kalai conjecture for these two classes, which encompass most of the standard families studied in random graph containment problems.

Related

  1. A dimension-free comparison between expectation thresholds and fractional expectation thresholds
    Jinyoung Park
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Kalai's Conjecture for Tight Trees
    Dhruv Mubayi, Jacques Verstraete
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold
    Xuan Fang, Tianyu Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
    Raghu Bollapragada, Yash Kumar
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Exact Thresholds for Global Univalence, Convexity, and Positive Real Part of a Modified Second Einstein Function
    Amr M. Y. Abdelaty, Hesham M. A. Mohamed, Ibrahim S. Elshazly
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref

Cite

BibTeXRIS
BibTeX
@misc{tran2026fractional,
  title = {{Fractional expectation thresholds and the "second" Kahn-Kalai conjecture}},
  author = {Tuan Tran},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.20546},
  eprint = {2609.20546},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20546},
}
RIS
TY  - UNPB
TI  - Fractional expectation thresholds and the "second" Kahn-Kalai conjecture
AU  - Tuan Tran
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.20546
UR  - https://arxiv.org/abs/2609.20546
AB  - We show that the uniform probability measure on copies of a nonempty graph H in K_n is Cq_Hlog(2e(H))-spread, where q_H is its graphic expectation threshold. Consequently, the fractional expectation threshold of H is at most Cq_Hlog(2e(H)). We remove the logarithmic factor for trees and for graphs whose average degree is at least the logarithm of their maximum degree. This proves the ``second'' Kahn-Kalai conjecture for these two classes, which encompass most of the standard families studied in random graph containment problems.
ER  -