AFTD Auto-Formalizing Theoretical Domains

gpa_adjMat

def

The 0/1 matrix e of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation lemma): e i j = 1 iff i and j are adjacent.

Statement

noncomputable def gpa_adjMat {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (i j : Fin k) : ℝ
Defined in
Generalized Principal-Agency: Contracts, Information, Games and Beyond, WINE 2024 (arXiv:2209.01146v2), Section 5.3 (proof of Theorem 5) and Appendix 13.2, Eq. (5.4); formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Used by 13
  • gpa_lhs_isGreatestExact value of the left side of Eq. (5.4) of arXiv:2209.01146 on the independent-set instances: max_{σ ∈ Δ_k} u*(σ) - h(σ) = 1 - 1/α(G) +…
  • gpa_rhs_attainThe value α(G) is attained on the cube, at the indicator vector of a maximum independent set.
  • gpa_adjMat_zero_oneThe adjacency matrix is a 0/1 matrix, as required in Section 5.3 of arXiv:2209.01146.
  • 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_nbr_nonnegNeighbour sums are nonnegative for nonnegative vectors.
  • gpa_lhs_upperUpper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every independent set.
  • gpa_rhs_isGreatestExact value of the right side of Eq. (5.4) of arXiv:2209.01146 (before the factor 1/k): max_{x ∈ [0,1]^k} u*(x) = α(G).
  • 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_nbr_geA single neighbour's coordinate is bounded by the neighbour sum.
  • gpa_rhs_upperUpper bound on the cube: u*(x) ≤ α(G) for every x ∈ [0,1]^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 ∈…
  • gpa_eq54_fails_of_indepEq. (5.4) of arXiv:2209.01146 (max_{Δ_k} (u* - h) = (1/k) max_{[0,1]^k} u*) fails on every graph whose independence number α satisfies 2 ≤…
  • 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

/-- The 0/1 matrix `e` of arXiv:2209.01146, Section 5.3 (taken from the maximum-independent-set instances of the cited convex-maximisation lemma): `e i j = 1` iff `i` and `j` are adjacent. -/
noncomputable def gpa_adjMat {k : ℕ} (G : SimpleGraph (Fin k)) [DecidableRel G.Adj]
    (i j : Fin k) : ℝ :=
  if G.Adj i j then 1 else 0
See it in the graphDiscuss this resultChallenge it