tournament_inversion_number_reverse
For a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
Statement
theorem tournament_inversion_number_reverse (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : digraph_inversion_number (digraph_reverse D) = digraph_inversion_number D
- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4 ("a set of inversions decycle D if and only if they decycle D̄, so inv(D) = inv(D̄)").
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- digraph_reverseThe reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
- 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_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)…
- digraph_reverse_is_tournamentThe reverse of a tournament is a tournament.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- Used by 1
- 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.
The proof, explained
The equality is proved by establishing the mutual bounds inv(D̄) ≤ inv(D) and inv(D) ≤ inv(D̄) via antisymmetry. Each direction applies an existing lemma stating that an arc-reversing vertex map from a digraph into a tournament bounds the inversion number; the identity map gives the required reversal in both directions, using the fact that reversing a tournament produces another tournament.
To show inv(D̄) = inv(D), it suffices to prove inv(D̄) ≤ inv(D) and inv(D) ≤ inv(D̄).
By the antisymmetry of the partial order on natural numbers (le_antisymm), an equality follows from proving inequalities in both directions.
uses
le_antisymmapply le_antisymminv(D̄) ≤ inv(D)
We apply the comparison lemma digraph_inversion_number_le_of_adj_iff_reverse with G = D̄, E = D, and the identity map. The hypothesis that D is a tournament is given by h, and the adjacency-reversal condition (D̄.Adj x y ↔ D.Adj y x) holds definitionally by reflexivity of equivalence (Iff.rfl).
uses
digraph_inversion_number_le_of_adj_iff_reverse,Iff.rfl· exact digraph_inversion_number_le_of_adj_iff_reverse _ D id h (fun x y => Iff.rfl)
inv(D) ≤ inv(D̄)
We apply the same comparison lemma in the opposite direction, with G = D, E = D̄, and the identity map. The requirement that D̄ is a tournament is supplied by digraph_reverse_is_tournament, and the adjacency condition (D.Adj x y ↔ D̄.Adj y x) again holds definitionally by reflexivity (Iff.rfl).
uses
digraph_inversion_number_le_of_adj_iff_reverse,digraph_reverse_is_tournament,Iff.rfl· exact digraph_inversion_number_le_of_adj_iff_reverse D (digraph_reverse D) id (digraph_reverse_is_tournament D h) (fun x y => Iff.rfl)
le_antisymm- If a ≤ b and b ≤ a in a partial order, then a = b.
digraph_inversion_number_le_of_adj_iff_reverse- If E is a finite tournament and f reverses adjacencies between G and E (that is, G.Adj x y ↔ E.Adj (f y) (f x)), then digraph_inversion_number G ≤ digraph_inversion_number E.
digraph_reverse_is_tournament- The reversal of any tournament is also a tournament.
Iff.rfl- Any proposition is logically equivalent to itself (P ↔ P).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem tournament_inversion_number_reverse (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : digraph_inversion_number (digraph_reverse D) = digraph_inversion_number D := by apply le_antisymm · exact digraph_inversion_number_le_of_adj_iff_reverse _ D id h (fun x y => Iff.rfl) · exact digraph_inversion_number_le_of_adj_iff_reverse D (digraph_reverse D) id (digraph_reverse_is_tournament D h) (fun x y => Iff.rfl)