A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold
Abstract
We proved a log-star comparison between the expectation threshold q(ℱ) and the fractional expectation threshold qf(ℱ) for any nontrivial increasing family ℱ on a finite ground set V of size |V|=N. Specifically, we show that qf(ℱ)≤64log2*(N+2) q(ℱ), where log2* x is the iterated logarithm of base-2. Using similiar methods, one can extend this result to the following stronger form: there exists a universal constant C>0 such that qf(ℱ)≤ Cq(ℱ)log2*(l(ℱ)), qf(ℱ)≤ Cq(ℱ)log2*(VC(minℱ)), where l(ℱ):=max{2,maxS∈minℱ|S|} and VC(minℱ) denotes the VC-dimension of minℱ. On October 7, 2026, OpenAI released a result proving the equivalence of fractional and integral thresholds, which supersedes the findings in this note. The authors are keeping this note for historical reference.
Related
- A dimension-free comparison between expectation thresholds and fractional expectation thresholds
- Fractional expectation thresholds and the "second" Kahn-Kalai conjecture
- Graph Decompositions at the Expectation Threshold
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- A Sharp Mass Threshold for Fractional Choquard Equations with Lower Hardy-Littlewood-Sobolev and L2-Critical Terms
BibTeX
@misc{fang2026logstar,
title = {{A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold}},
author = {Xuan Fang and Tianyu Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30680},
eprint = {2609.30680},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30680},
}
RIS
TY - UNPB
TI - A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold
AU - Xuan Fang
AU - Tianyu Wang
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2609.30680
UR - https://arxiv.org/abs/2609.30680
AB - We proved a log-star comparison between the expectation threshold q(ℱ) and the fractional expectation threshold q_f(ℱ) for any nontrivial increasing family ℱ on a finite ground set V of size |V|=N. Specifically, we show that q_f(ℱ)≤64log_2^*(N+2) q(ℱ), where log_2^* x is the iterated logarithm of base-2. Using similiar methods, one can extend this result to the following stronger form: there exists a universal constant C>0 such that q_f(ℱ)≤ Cq(ℱ)log_2^*(l(ℱ)), q_f(ℱ)≤ Cq(ℱ)log_2^*(VC(minℱ)), where l(ℱ):=max{2,max_S∈minℱ|S|} and VC(minℱ) denotes the VC-dimension of minℱ. On October 7, 2026, OpenAI released a result proving the equivalence of fractional and integral thresholds, which supersedes the findings in this note. The authors are keeping this note for historical reference.
ER -