AFTD Auto-Formalizing Theoretical Domains

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

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)}
See it in the graphDiscuss this resultChallenge it