Feige’s conjecture
For every positive integer and every collection of independent nonnegative random variables satisfying for all , one has , equivalently .
References
- Perfect matchings in hypergraphs and Feige’s inequality — arXiv — Aleksa Milojević, Benny Sudakov
Source: arXiv
Progress summary
A 2026 specialist preprint claims to prove the conjecture, but the claim has not been independently checked.
Feige’s conjecture concerns independent nonnegative random variables with expectation and a sharp upper bound on the probability that their sum exceeds a threshold. The standard case is equivalent to a lower bound of for the complementary event.
Known results
- Feige proved a constant bound of .
- He, Zhang, and Zhang improved this to .
- Garnett obtained the then-best bound .
- 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 for ; 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- statement remains open.
Sources
Solutions 0
No solutions have been posted yet.