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.
Actions
Submit a Proof
Have a proof attempt? Submit it for zero-trust verification.
lemma erdos_499.variants.one_le :
answer(True) ↔ ∀ n > 0, ∀ M ∈ doublyStochastic ℝ (Fin n), ∃ σ : Equiv.Perm (Fin n),
(∀ i, M i (σ i) ≠ 0) ∧ 1 ≤ ∑ i, M i (σ i)
