Erdős problem 499 · problems.science

The conjecture of van der Waerden, which states that the permanent of a doubly stochastic matrix is at least $n^{-n} n!$ .

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

499.lean

Retained formal statement2 of 3

A weaker version of Erdős' problem 499, which asks whether for every doubly stochastic matrix, there exists a permutation $σ \in S_n$ with $M_{i, σ(i)} ≠ 0$ and such that $\sum_{1 \leq i \leq n} M_{i, σ(i)} \geq 1$ Proved by Marcus and Ree [MaRe59].

[MaRe59] Marcus, M. and Ree, R., Diagonals of doubly stochastic matrices. Quart. J. Math. Oxford Ser. (2) (1959), 296-302.

FormalConjectures/ErdosProblems/499.leanErdos499.erdos_499.variants.one_le1 lineExact file

1True ↔ ∀ n > 0, ∀ M ∈ doublyStochastic ℝ (Fin n), ∃ σ, (∀ (i : Fin n), M i (σ i) ≠ 0) ∧ 1 ≤ ∑ i, M i (σ i)

SolvedStatement only, no proof

Sources

Search problems.science