gpa_nbr_nonneg
lemmaverified
Neighbour sums are nonnegative for nonnegative vectors.
Statement
open Finset in lemma gpa_nbr_nonneg {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj] (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) (i : Fin k) : 0 ≤ ∑ j, gpa_adjMat G i j * σ j
- Source
- step towards gpa_eq54_false / gpa_eq54_fails_of_indep (Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Sec. 5.3, Eq. (5.4))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- gpa_adjMatThe 0/1 matrix e of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation…
- Used by 3
- gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
- gpa_lhs_attainThe bound 1 - 1/α + 1/k is attained on the simplex, by the uniform distribution on a maximum independent set I (1 ≤ |I| ≤ k).
- gpa_uStar_le_indepKey structural lemma: for a nonnegative vector, the coordinates with a positive term of u* form an independent set P, and u*(σ) ≤ Σ_{i ∈…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset in/-- Neighbour sums are nonnegative for nonnegative vectors. -/lemma gpa_nbr_nonneg {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj] (σ : Fin k → ℝ) (hσ : ∀ i, 0 ≤ σ i) (i : Fin k) : 0 ≤ ∑ j, gpa_adjMat G i j * σ j := by apply Finset.sum_nonneg intro j _ unfold gpa_adjMat split_ifs <;> nlinarith [hσ j]