AFTD Auto-Formalizing Theoretical Domains

team_P2

def

The strengthened instance: p(i,i) = 1/2, p(i, i+1 mod n) = 1/2 - v'_i + v'_{i+1} - τ, all other entries 0.

Statement

noncomputable def team_P2 (m : ℕ) (i j : Fin (2 * m + 3)) : ℝ
Source
step towards team_thm4_part2_false / team_thm4_part2_exists_false (The Team Order Problem: Maximizing the Probability of Matching Being Large Enough, SAGT 2024 (arXiv:2605.21234), Section 6, Theorem 4(2))
Verified
06 Oct 2026
Axioms
none listed
Built on 3
  • team_nextThe cycle successor relation on positions.
  • team_tauSlack parameter τ_m = 1/(100(m+1)).
  • team_v2Scaled column potentials v'_j = (1 - 2τ) v_j (range 1/2 - τ).
Used by 12
  • team_id_winProb2In the strengthened instance the identity line-up (all edges 1/2) wins with probability exactly 1/2.
  • team2_unique_maxWeightThe identity is the unique maximum-weight matching of the strengthened instance.
  • team_weight2_idIn the strengthened instance the identity line-up has weight n/2.
  • team_rot_list2The edge probabilities of the rotation in the strengthened instance are 3/4 - 3tau/2, 3/4 - 3tau/2, followed by 0, 1-2tau, 0, ..., 0.
  • team_P2_rotIn the strengthened instance the rotation line-up i -> i+1 uses the cycle edge probabilities team_w2.
  • team_thm4_part2_exists_falseEven the existential reading of Theorem 4 (2) of arXiv:2605.21234 is false, for every function ε in place of o(1): on the (2m+3)-player…
  • team_dual2_diagIn the strengthened instance the dual constraint is tight on the diagonal: p(i,i) = u_i + v_i.
  • team_P2_boundsAll entries of the strengthened Team Order instance are probabilities in [0,1].
  • team_gap_uniqueQuantitative form of the strengthened counterexample: for every m, the identity is the unique maximum-weight matching, its edges are all…
  • team_weight2_ltEvery line-up other than the identity has weight strictly below n/2.
  • team_dual2Strict dual slack on every off-diagonal entry.
  • 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

/-- The strengthened instance: `p(i,i) = 1/2`, `p(i, i+1 mod n) = 1/2 - v'_i + v'_{i+1} - τ`, all other entries `0`. -/
noncomputable def team_P2 (m : ℕ) (i j : Fin (2 * m + 3)) : ℝ :=
  if j = i then 1 / 2
  else if team_next i j then 1 / 2 - team_v2 i + team_v2 j - team_tau m else 0
See it in the graphDiscuss this resultChallenge it