AFTD Auto-Formalizing Theoretical Domains

tournament_min_rank

def

The tournament minimum rank tmr(D): the least F₂-rank of a symmetric matrix M over F₂ that decycles D, i.e. such that reversing every arc uv with M_uv = 1 makes D acyclic.

Statement

noncomputable def tournament_min_rank {V : Type*} [Fintype V] (D : Digraph V) : ℕ
Defined in
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 2.2 (tournament minimum rank).
Verified
13 Oct 2026
Axioms
none listed
Built on 2
  • digraph_flip_by_matrixGiven a digraph D and a (symmetric) matrix M over F₂ indexed by its vertices, the digraph obtained by reversing every arc uv with M_uv = 1…
  • digraph_is_acyclicA digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it…
Used by 5

Lean source view module on GitHub

/-- `tmr D`: least `𝔽₂`-rank of a symmetric decycling matrix of `D`. -/
noncomputable def tournament_min_rank {V : Type*} [Fintype V] (D : Digraph V) : ℕ :=
  sInf {r | ∃ M : Matrix V V (ZMod 2), M.IsSymm ∧
    digraph_is_acyclic (digraph_flip_by_matrix D M) ∧ M.rank = r}
See it in the graphDiscuss this resultChallenge it