gpa_adjMat_zero_one
lemmaverified
The adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
Statement
lemma gpa_adjMat_zero_one {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj] (i j : Fin k) :
gpa_adjMat G i j = 0 ∨ gpa_adjMat G i j = 1- 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 2
- gpa_eq54_falseEq. (5.4) in the proof of Theorem 5 (hardness of costly information acquisition) of arXiv:2209.01146 is false: it is not true that for…
- gpa_cube_max_le_one_falseThe auxiliary claim max_{x ∈ [0,1]^k} u*(x) ≤ 1 used in the proof of Eq. (5.4) of arXiv:2209.01146 is false: on the path with three…
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.
/-- The adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146. -/lemma gpa_adjMat_zero_one {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj] (i j : Fin k) : gpa_adjMat G i j = 0 ∨ gpa_adjMat G i j = 1 := by unfold gpa_adjMat split_ifs <;> simp