team_thm4_part2
def
Theorem 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 matching M* with w(M*) ∈ [n/2 - √n log n, n/2 + √n log n] and every optimal line-up O, Pr[O wins] ≤ Pr[M* wins] + (4 + ε n)/(n+1) · Σ_{e ∈ M*} (p_e - 1/2)².
Statement
open Finset in def team_thm4_part2 (ε : ℕ → ℝ) (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 4
- 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…
- team_winProbWinning probability of a line-up in the Team Order problem of arXiv:2605.21234: team 1 wins if it wins at least ⌊n/2⌋ + 1 of the n…
- team_isMaxWeightπ is a maximum-weight perfect matching.
- team_isOptimalπ is an optimal line-up (maximises the winning probability).
- Used by 1
- team_thm4_part2_falseTheorem 4 (2) of arXiv:2605.21234 is false, whatever function is used for its o(1) term: for every m, on the (2m+3)-player instance the…
Lean source view module on GitHub
open Finset in /-- Theorem 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 matching `M*` with `w(M*) ∈ [n/2 - √n log n, n/2 + √n log n]` and every optimal line-up `O`, `Pr[O wins] ≤ Pr[M* wins] + (4 + ε n)/(n+1) · Σ_{e ∈ M*} (p_e - 1/2)²`. -/ def team_thm4_part2 (ε : ℕ → ℝ) (N : ℕ) : Prop := ∀ n ≥ N, ∀ P : Fin n → Fin n → ℝ, (∀ i j, 0 ≤ P i j ∧ P i j ≤ 1) → ∀ Mstar O : Equiv.Perm (Fin n), team_isMaxWeight P Mstar → team_isOptimal P O → (n : ℝ) / 2 - Real.sqrt n * Real.log n ≤ team_weight P Mstar → team_weight P Mstar ≤ (n : ℝ) / 2 + Real.sqrt n * Real.log n → team_winProb P O ≤ team_winProb P Mstar + (4 + ε n) / ((n : ℝ) + 1) * ∑ i, (P i (Mstar i) - 1 / 2) ^ 2