Problem 499

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}?

Source: erdosproblems.com/499

Combinatorics

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved on the site (label PROVED (LEAN)). The site credits the answer yes to Marcus and Minc [MaMi62]; the Lean qualifier refers to a third-party proof described under Formalization. The accepted claims are the Marcus–Minc theorem, on its refereed publication and the curator's credit, and the two proofs of van der Waerden's conjecture, which implies the statement: Egorychev and Falikman, each on its refereed publication. The site also credits Gyires with a proof of the conjecture; his paper does not contain one, and that attribution is rejected on its claim page.

Eg81: Egorychev, G. P., The solution of the van der Waerden problem for permanents. Dokl. Akad. Nauk SSSR (1981), 1041-1044.
Fa81: Falikman, D. I., Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix. Mat. Zametki 29 (1981), no. 6, 931-938, 957.
Gy80: Gyires, B., The common source of several inequalities concerning doubly stochastic matrices. Publ. Math. Debrecen (1980), 291-304.
MaMi62: Marcus, Marvin and Minc, Henryk, Some results on doubly stochastic matrices. Proc. Amer. Math. Soc. (1962), 571-579.
MaRe59: Marcus, M. and Ree, R., Diagonals of doubly stochastic matrices. Quart. J. Math. Oxford Ser. (2) (1959), 296-302.

Problem 499

Status

Proof claims

Discussion