Feige’s conjecture

Feige’s conjecture concerns independent nonnegative random variables with expectation $1$ and a sharp upper bound on the probability that their sum exceeds a threshold. The standard case is equivalent to a lower bound of $1/e$ for the complementary event.

Known results

• Feige proved a constant bound of $12/13$.
• He, Zhang, and Zhang improved this to $7/8$.
• Garnett obtained the then-best bound $43/50$.
• A 2019 paper identified the associated fractional-matching threshold with the corresponding probabilistic supremum, without proving the conjecture.

October 2026 proof claim

Milojević and Sudakov’s preprint reports a direct proof of Feige’s inequality. A separate July 2026 preprint claims the standard case and the stronger bound $\delta\left(\frac{n}{n+\delta}\right)^n$ for $0<\delta\leq 1$; it says the latter remains open. The proofs are unrefereed and have no independent mathematical assessment in the retrieved sources.

Current status (as of October 2026): Feige’s conjecture is claimed proved in unrefereed preprints, but remains mathematically unverified; the stronger arbitrary-$\delta$ statement remains open.