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
- tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
- tournament_min_rank_le_dijoinFor finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a…
- tournament_min_rank_le_inversion_numberFor a finite tournament D: tmr(D) ≤ inv(D).
- tournament_min_rank_eq_zero_of_is_acyclicAn acyclic digraph has tournament minimum rank 0 (the zero matrix decycles it).
- tournament_min_rank_dijoin_le_of_symm_invLet B be an invertible symmetric n × n matrix over F₂, L the lower triangular all-ones matrix, and A = L B⁻¹ Lᵀ. Then the tournaments D₁ =…
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}