gpa_indep
def
An independent set of the graph G.
Statement
open Finset in def gpa_indep {k : ℕ} (G : SimpleGraph (Fin k)) (S : Finset (Fin k)) : Prop
- 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 9
- 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_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_lhs_upperUpper bound on the simplex: u*(σ) - h(σ) ≤ 1 - 1/α + 1/k for every σ ∈ Δ_k, where α ≥ 1 bounds every independent set.
- gpa_path3_indepIn the path 0 - 2 - 1, {0, 1} is a maximum 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_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 ≤…
Lean source view module on GitHub
open Finset in /-- An independent set of the graph `G`. -/ def gpa_indep {k : ℕ} (G : SimpleGraph (Fin k)) (S : Finset (Fin k)) : Prop := ∀ i ∈ S, ∀ j ∈ S, ¬ G.Adj i j