digraph_inversion_number
def
The inversion number inv(D): the least number p of vertex sets X₁, …, X_p whose successive inversions turn D into an acyclic digraph (0 by convention when no such family exists, which never happens for a finite tournament).
Statement
noncomputable def digraph_inversion_number {V : Type*} (D : Digraph V) : ℕ
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 (decycling family, inversion number).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Built on 2
- digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
- 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 16
- tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
- tournament_dijoin_inversion_number_symm_of_is_acyclic_leftThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).
- tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_leftWhen D₁ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- tournament_dijoin_inversion_number_le_addFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
- tournament_dijoin_inversion_number_symm_of_is_acyclic_rightThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic: both sides equal inv(D₁).
- digraph_inversion_number_le_of_adj_iff_reverseIf G's arcs are E's arcs pulled back along a map f and reversed (x → y in G iff f y → f x in E), and E is a finite tournament, then inv(G)…
- tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_rightWhen D₂ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- tournament_dijoin_inversion_number_le_symm_add_twoFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2 (with D₁, D₂ swapped this gives |inv(D₁ → D₂) − inv(D₂ → D₁)| ≤ 2): invert…
- digraph_inversion_number_eq_zero_of_is_acyclicAn acyclic digraph has inversion number 0.
- tournament_min_rank_le_inversion_numberFor a finite tournament D: tmr(D) ≤ inv(D).
- tournament_dijoin_reverse_inversion_number_le_of_eq_maxWhenever inv(D₁ → D₂) attains its theoretical minimum max(inv(D₁), inv(D₂)), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.
- tournament_dijoin_swap_inversion_number_eq_reverseFor finite tournaments D₁, D₂: inv(D₂ → D₁) = inv(D̄₁ → D̄₂). So the symmetry conjecture inv(D₁ → D₂) = inv(D₂ → D₁) says exactly that the…
- tournament_dijoin_reverse_inversion_number_le_add_twoFor finite tournaments D₁ and D₂, inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) + 2.
- tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
- tournament_dijoin_reverse_inversion_number_le_of_eq_addWhenever inv(D̄₁ → D̄₂) attains its theoretical maximum inv(D₁) + inv(D₂), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.
- tournament_exists_family_length_eq_inversion_numberFor a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
Lean source view module on GitHub
/-- The inversion number `inv D`: the least number of successive inversions that make the digraph acyclic. -/ noncomputable def digraph_inversion_number {V : Type*} (D : Digraph V) : ℕ := sInf {p | ∃ Xs : List (Set V), Xs.length = p ∧ digraph_is_acyclic (Xs.foldl digraph_invert D)}