digraph_reverse
def
The reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
Statement
def digraph_reverse {V : Type*} (D : Digraph V) : Digraph V
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4 (D̄, the tournament obtained by flipping every arc of D).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 10
- tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
- 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_reverse_inversion_number_eq_of_is_acyclic_leftWhen D₁ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_rightWhen D₂ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- digraph_reverse_reverseReversing a digraph twice yields the original digraph.
- 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_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.
- digraph_reverse_is_tournamentThe reverse of a tournament is a tournament.
Lean source view module on GitHub
/-- The reverse of a digraph: every arc turned around. -/ def digraph_reverse {V : Type*} (D : Digraph V) : Digraph V where Adj x y := D.Adj y x