tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_right
When D₂ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
Statement
theorem tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_right (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) (hac : digraph_is_acyclic D₂) : digraph_inversion_number (digraph_dijoin D₁ D₂) = digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂))
- Source
- step towards tournament_dijoin_reverse_inversion_number_le
- Verified
- 22 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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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…
- 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_inversion_number_symm_of_is_acyclic_rightThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic: both sides equal inv(D₁).
The proof, explained
The proof chains two existing identities for the inversion number of tournament dijoins. First, because $D_2$ is acyclic, swapping the factors preserves the inversion number: $\operatorname{inv}(D_1 \to D_2) = \operatorname{inv}(D_2 \to D_1)$. Second, swapping the factors of any tournament dijoin is known to match the inversion number of reversing both components: $\operatorname{inv}(D_2 \to D_1) = \operatorname{inv}(\overline{D}_1 \to \overline{D}_2)$.
$\operatorname{inv}(D_1 \to D_2) = \operatorname{inv}(D_2 \to D_1)$, reducing the goal to showing $\operatorname{inv}(D_2 \to D_1) = \operatorname{inv}(\overline{D}_1 \to \overline{D}_2)$.
Because $D_1$ and $D_2$ are tournaments and $D_2$ is acyclic, `tournament_dijoin_inversion_number_symm_of_is_acyclic_right` allows us to swap the order of $D_1$ and $D_2$ in the dijoin without altering its inversion number.
uses
tournament_dijoin_inversion_number_symm_of_is_acyclic_rightrw [tournament_dijoin_inversion_number_symm_of_is_acyclic_right V W D₁ D₂ h₁ h₂ hac]$\operatorname{inv}(D_2 \to D_1) = \operatorname{inv}(\overline{D}_1 \to \overline{D}_2)$, completing the proof.
By `tournament_dijoin_swap_inversion_number_eq_reverse`, swapping the two factors of a tournament dijoin yields the same inversion number as reversing both factors, which closes the goal.
uses
tournament_dijoin_swap_inversion_number_eq_reverserw [tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂]
tournament_dijoin_inversion_number_symm_of_is_acyclic_right- For tournaments $D_1$ and $D_2$ with $D_2$ acyclic, the dijoin $D_1 \to D_2$ and the swapped dijoin $D_2 \to D_1$ have the same inversion number.
tournament_dijoin_swap_inversion_number_eq_reverse- For tournaments $D_1$ and $D_2$, the swapped dijoin $D_2 \to D_1$ has the same inversion number as the dijoin of their reversals $\overline{D}_1 \to \overline{D}_2$.
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.
/-- When D₂ is an acyclic tournament, inv(D₁ → D₂) = inv(D̄₁ → D̄₂). -/theorem tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_right (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) (hac : digraph_is_acyclic D₂) : digraph_inversion_number (digraph_dijoin D₁ D₂) = digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂)) := by rw [tournament_dijoin_inversion_number_symm_of_is_acyclic_right V W D₁ D₂ h₁ h₂ hac] rw [tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂]