team_gap_unique
theoremverifiedoriginal
Quantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all 1/2, and every optimal line-up beats it by at least 1/40.
Statement
theorem team_gap_unique (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3)))
(hO : team_isOptimal (team_P2 m) O) :
(∀ M, team_isMaxWeight (team_P2 m) M ↔ M = 1) ∧
(∀ i, team_P2 m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) = 1 / 2) ∧
team_winProb (team_P2 m) 1 + 1 / 40 ≤ team_winProb (team_P2 m) O- Related work
- operator (Claude), 2026-10-05: counterexample to Theorem 4(2) of The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2); n = 2m+3 players, the identity line-up is the unique maximum-weight matching with all edges 1/2 (so the error term vanishes for every o(1) function), yet a rotation wins with probability at least 1/2 + 1/40; found by a search agent, checked by the Lean kernel
- Verified
- 05 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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).
- team_P2The strengthened instance: p(i,i) = 1/2, p(i, i+1 mod n) = 1/2 - v'_i + v'_{i+1} - τ, all other entries 0.
- team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
- team_id_winProb2In the strengthened instance the identity line-up (all edges 1/2) wins with probability exactly 1/2.
- team_rot_winProb2The rotation line-up of the strengthened instance wins with probability at least 1/2 + 1/40.
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.
/-- Quantitative form of the strengthened counterexample: for every `m`, the identity is the unique maximum-weight matching, its edges are all `1/2`, and every optimal line-up beats it by at least `1/40`. -/theorem team_gap_unique (m : ℕ) (O : Equiv.Perm (Fin (2 * m + 3))) (hO : team_isOptimal (team_P2 m) O) : (∀ M, team_isMaxWeight (team_P2 m) M ↔ M = 1) ∧ (∀ i, team_P2 m i ((1 : Equiv.Perm (Fin (2 * m + 3))) i) = 1 / 2) ∧ team_winProb (team_P2 m) 1 + 1 / 40 ≤ team_winProb (team_P2 m) O := by refine ⟨team2_unique_maxWeight m, fun i => by simp [team_P2], ?_⟩ have := hO (finRotate (2 * m + 3)) have := team_rot_winProb2 m rw [team_id_winProb2] linarith