PROVED (LEAN)
This has been solved in the affirmative and the proof verified in Lean.
Let $M=(a_{ij})$ be a real $n\times n$ doubly stochastic matrix (i.e. the entries are non-negative and each column and row sums to $1$). Does there exist some $\sigma\in S_n$ such that\[\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}?\]
A weaker form of the conjecture of van der Waerden, which states that\[\mathrm{perm}(M)=\sum_{\sigma\in S_n}\prod_{1\leq i\leq n}a_{i\sigma(i)}\geq n^{-n}n!\]with equality if and only if $a_{ij}=1/n$ for all $i,j$.
This conjecture is true, and was proved by Marcus and Minc
[MaMi62].
Erdős also conjectured the even weaker fact that there exists some $\sigma\in S_n$ such that $a_{i\sigma(i)}\neq 0$ for all $i$ and\[\sum_{i}a_{i\sigma(i)}\geq 1.\]This weaker statement was proved by Marcus and Ree
[MaRe59].
van der Waerden's conjecture itself was proved by Gyires
[Gy80], Egorychev
[Eg81], and Falikman
[Fa81].
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #499, https://www.erdosproblems.com/499, accessed 2026-01-16
