tournament_dijoin_swap_inversion_number_eq_reverse
For finite tournaments D₁, D₂: inv(D₂ → D₁) = inv(D̄₁ → D̄₂). So the symmetry conjecture inv(D₁ → D₂) = inv(D₂ → D₁) says exactly that the inversion number of a dijoin is unchanged when both parts are reversed.
Statement
theorem tournament_dijoin_swap_inversion_number_eq_reverse (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : digraph_inversion_number (digraph_dijoin D₂ D₁) = digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂))
- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4, reduction after Conjecture 4.1 (the reverse of D₂ → D₁ is D̄₁ → D̄₂).
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- digraph_reverseThe reverse D̄ of a digraph D: the digraph on the same vertices with every arc turned around.
- digraph_dijoinThe dijoin D₁ → D₂: disjoint copies of D₁ and D₂ together with every arc from a vertex of D₁ to a vertex 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_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_dijoin_is_tournamentThe dijoin of two tournaments 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 3
- 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.
- tournament_dijoin_reverse_inversion_number_le_add_twoFor finite tournaments D₁ and D₂, inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) + 2.
The proof, explained
The equality is established by antisymmetry, reducing to proving both directions of the inequality between inv(D₂ → D₁) and inv(D̄₁ → D̄₂). In each direction, the inversion number is bounded using `digraph_inversion_number_le_of_adj_iff_reverse` via the swap map `Sum.swap`, which interchanges the two summands. A four-way case analysis on vertex summands confirms that `Sum.swap` acts as an anti-isomorphism by directly unfolding the definitions of dijoin and reversal.
It suffices to show that inv(D₂ → D₁) ≤ inv(D̄₁ → D̄₂) and inv(D̄₁ → D̄₂) ≤ inv(D₂ → D₁).
By antisymmetry of the partial order on natural numbers (`le_antisymm`), the two inversion numbers are equal if each is less than or equal to the other.
uses
le_antisymmapply le_antisymminv(D₂ → D₁) ≤ inv(D̄₁ → D̄₂)
By `digraph_inversion_number_le_of_adj_iff_reverse`, an inversion number inequality holds whenever there is an adjacency-reversing map into a tournament. The target dijoin D̄₁ → D̄₂ is a tournament because the reversal of a tournament is a tournament (`digraph_reverse_is_tournament`) and the dijoin of tournaments is a tournament (`digraph_dijoin_is_tournament`). Using the canonical swap map `Sum.swap : W ⊕ V → V ⊕ W`, it remains to show that x → y in D₂ → D₁ if and only if y.swap → x.swap in D̄₁ → D̄₂. Case analysis on whether x and y originate from W or V yields four cases; in each case, unfolding the definitions of dijoin and reverse digraph simplifies the equivalence to an identity.
uses
digraph_inversion_number_le_of_adj_iff_reverse,digraph_dijoin_is_tournament,digraph_reverse_is_tournament· apply digraph_inversion_number_le_of_adj_iff_reverse _ _ Sum.swap (digraph_dijoin_is_tournament _ _ (digraph_reverse_is_tournament D₁ h₁) (digraph_reverse_is_tournament D₂ h₂)) intro x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_dijoin, digraph_reverse]
inv(D̄₁ → D̄₂) ≤ inv(D₂ → D₁)
By the same lemma `digraph_inversion_number_le_of_adj_iff_reverse` applied in the reverse direction with `Sum.swap : V ⊕ W → W ⊕ V`, and using that D₂ → D₁ is a tournament (`digraph_dijoin_is_tournament`), the inequality reduces to the reversed adjacency condition. Case analysis on whether x, y ∈ V ⊕ W come from V or W followed by unfolding the definitions of dijoin and reverse digraph closes all four cases.
uses
digraph_inversion_number_le_of_adj_iff_reverse,digraph_dijoin_is_tournament· apply digraph_inversion_number_le_of_adj_iff_reverse _ _ Sum.swap (digraph_dijoin_is_tournament _ _ h₂ h₁) intro x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_dijoin, digraph_reverse]
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
digraph_inversion_number_le_of_adj_iff_reverse- If E is a finite tournament and f : U → U' is an adjacency-reversing map from G to E (so x is adjacent to y in G iff f(y) is adjacent to f(x) in E), then the inversion number of G is at most that of E.
digraph_dijoin_is_tournament- The dijoin of two tournaments is a tournament.
digraph_reverse_is_tournament- The reversal of a tournament is a tournament.
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_dijoin_swap_inversion_number_eq_reverse (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : digraph_inversion_number (digraph_dijoin D₂ D₁) = digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂)) := by apply le_antisymm · apply digraph_inversion_number_le_of_adj_iff_reverse _ _ Sum.swap (digraph_dijoin_is_tournament _ _ (digraph_reverse_is_tournament D₁ h₁) (digraph_reverse_is_tournament D₂ h₂)) intro x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_dijoin, digraph_reverse] · apply digraph_inversion_number_le_of_adj_iff_reverse _ _ Sum.swap (digraph_dijoin_is_tournament _ _ h₂ h₁) intro x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_dijoin, digraph_reverse]