A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold
Xuan Fang, Tianyu Wang
Submitted by Xuan Fang
Published November 16, 2026 · Version v1, November 16, 2026 · DOI 10.66977/xsci.2611.002p
Combinatorics
Abstract
We proved a log-star comparison between the expectation threshold q(F) and the fractional
expectation threshold qf(F) for any nontrivial increasing family F on a finite ground set V of size ∣V∣=N. Specifically, we show that
qf(F)≤64log2∗(N+2)q(F),
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(F)≤Cq(F)log2∗(l(F)),qf(F)≤Cq(F)(1+log2∗(VC(minF)+2)),
where l(F):=max{2,maxS∈minF∣S∣} and VC(minF) denotes the VC-dimension of minF.
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.
View PDF