Chapter 37 lemma: van der Waerden permanent lower bound
ProvedBookSixth.permanent_doubly_stochastic_lowerproofs-from-the-booksixth-edition
Van der Waerden's theorem (Egorychev-Falikman): the permanent of a doubly stochastic real matrix is at least . This is the permanent estimate behind the lower counting bound of Chapter 37, Theorem 2.
Preamble
import Mathlib import Definitions.Def_BookSixth open scoped BigOperators open BookSixth
Formal statement
theorem BookSixth.permanent_doubly_stochastic_lower (n : ℕ) (M : Matrix (Fin n) (Fin n) ℝ) (hnn : ∀ i j, 0 ≤ M i j) (hrow : ∀ i, ∑ j, M i j = 1) (hcol : ∀ j, ∑ i, M i j = 1) :
(n.factorial : ℝ) / (n : ℝ) ^ n ≤ Matrix.permanent M := by sorrySource
Aigner and Ziegler, Proofs from THE BOOK, Sixth Edition (2018), Chapter 37, permanent lower bound used for Theorem 2, p. 266. https://doi.org/10.1007/978-3-662-57265-8_37