tournament_dijoin_reverse_inversion_number_le_add_two
For finite tournaments D₁ and D₂, inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) + 2.
Statement
theorem tournament_dijoin_reverse_inversion_number_le_add_two (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₂)) + 2
- Source
- step towards tournament_dijoin_reverse_inversion_number_le
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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.
- 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_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…
The proof, explained
The proof reduces the target inequality to comparing D₁ → D₂ with the swapped dijoin D₂ → D₁. By tournament_dijoin_swap_inversion_number_eq_reverse, the inversion number of D̄₁ → D̄₂ equals that of D₂ → D₁. The claim then follows directly from tournament_dijoin_inversion_number_le_symm_add_two, which shows that inv(D₁ → D₂) is bounded by inv(D₂ → D₁) + 2.
It suffices to show that inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2.
By tournament_dijoin_swap_inversion_number_eq_reverse, the inversion number of the dijoin with swapped components, D₂ → D₁, is equal to the inversion number of the dijoin of the reversed tournaments, D̄₁ → D̄₂. Rewriting with this equality replaces inv(D̄₁ → D̄₂) with inv(D₂ → D₁) on the right-hand side.
uses
tournament_dijoin_swap_inversion_number_eq_reverserw [← tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂]inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2, completing the proof.
This inequality is asserted directly by tournament_dijoin_inversion_number_le_symm_add_two, which bounds the inversion number of D₁ → D₂ by that of the swapped dijoin D₂ → D₁ plus 2.
uses
tournament_dijoin_inversion_number_le_symm_add_twoexact tournament_dijoin_inversion_number_le_symm_add_two V W D₁ D₂ h₁ h₂
tournament_dijoin_swap_inversion_number_eq_reverse- For finite tournaments D₁ and D₂, the inversion number of D₂ → D₁ is equal to that of D̄₁ → D̄₂.
tournament_dijoin_inversion_number_le_symm_add_two- For finite tournaments D₁ and D₂, the inversion number of D₁ → D₂ is at most that of D₂ → D₁ plus 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.
/-- For finite tournaments D₁ and D₂, the inversion number of D₁ → D₂ is at most that of D̄₁ → D̄₂ plus 2. -/theorem tournament_dijoin_reverse_inversion_number_le_add_two (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₂)) + 2 := by rw [← tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂] exact tournament_dijoin_inversion_number_le_symm_add_two V W D₁ D₂ h₁ h₂