AFTD Auto-Formalizing Theoretical Domains

team_isMaxWeight

def

π is a maximum-weight perfect matching.

Statement

def team_isMaxWeight {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : Prop
Defined in
The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); formalized by the operator (Claude), 2026-10-05
Verified
05 Oct 2026
Axioms
none listed
Built on 1
  • team_weightA line-up of team 1 against the fixed line-up of team 2 is a perfect matching, i.e. a permutation π of the n positions (player i of team 1…
Used by 6
  • team_thm4_part2Theorem 4 (2) of arXiv:2605.21234, with the o(1) term made explicit as a function ε: for all large n, every instance, every maximum-weight…
  • team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
  • team_gapQuantitative form: on the instance of size 2m+3, the optimal line-up beats the all-1/2 maximum-weight matching by at least 1/16, while the…
  • team_id_maxWeightThe identity line-up (all edges 1/2) is a maximum-weight matching.
  • team_gap_uniqueQuantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all…
  • team_thm4_part2_existsTheorem 4 (2) of arXiv:2605.21234 under its most generous (existential) reading: some maximum-weight matching M* satisfies the bound.

Lean source view module on GitHub

/-- `π` is a maximum-weight perfect matching. -/
def team_isMaxWeight {n : ℕ} (P : Fin n → Fin n → ℝ) (π : Equiv.Perm (Fin n)) : Prop :=
  ∀ σ : Equiv.Perm (Fin n), team_weight P σ ≤ team_weight P π
See it in the graphDiscuss this resultChallenge it