digraph_invert
def
The 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 other arc.
Statement
def digraph_invert {V : Type*} (D : Digraph V) (X : Set V) : Digraph V
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 (definition of the inversion of X in D).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 14
- digraph_dijoin_reverse_eq_invertsThe dijoin D̄₁ → D̄₂ equals D₁ → D₂ after inverting the two vertex sets Set.range Sum.inl and Set.range Sum.inr.
- 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_exists_covering_realizationLet d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a…
- 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₂.
- digraph_inversion_numberThe 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…
- digraph_invert_invertInverting the same vertex set twice gives back the digraph.
- 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_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).
- digraph_invert_is_tournamentInverting a vertex set of a tournament gives a tournament.
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- 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_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
/-- Inversion of a vertex set `X` in a digraph: every arc with both endpoints in `X` is reversed, every other arc is kept. -/ def digraph_invert {V : Type*} (D : Digraph V) (X : Set V) : Digraph V where Adj x y := (x ∈ X ∧ y ∈ X ∧ D.Adj y x) ∨ (¬ (x ∈ X ∧ y ∈ X) ∧ D.Adj x y)