tournament_dijoin_inversion_number_symm_of_is_acyclic_right
The symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic: both sides equal inv(D₁).
Statement
theorem tournament_dijoin_inversion_number_symm_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 D₂ D₁)
- Source
- step towards tournament_dijoin_inversion_number_symm
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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_eq_zero_of_is_acyclicAn acyclic digraph has inversion number 0.
- tournament_dijoin_inversion_number_le_addFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
- tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
- Used by 1
- tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_rightWhen D₂ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
The proof, explained
The inversion number of the dijoin of two tournaments is always bounded below by the maximum of their individual inversion numbers and above by their sum. When D₂ is acyclic, its inversion number is 0, which collapses the lower and upper bounds for both D₁ → D₂ and D₂ → D₁ to inv(D₁), forcing both dijoin inversion numbers to be equal.
The inversion number of D₂ is 0.
Because D₂ is acyclic, applying `digraph_inversion_number_eq_zero_of_is_acyclic` shows that its inversion number is 0.
uses
digraph_inversion_number_eq_zero_of_is_acyclichave h2_zero := digraph_inversion_number_eq_zero_of_is_acyclic D₂ hacBoth inv(D₁ → D₂) and inv(D₂ → D₁) are bounded below by the maximum and above by the sum of inv(D₁) and inv(D₂).
For any pair of tournaments, the dijoin inversion number is bounded above by the sum of their inversion numbers (`tournament_dijoin_inversion_number_le_add`) and below by their maximum (`tournament_inversion_number_le_dijoin`). We record these upper and lower bounds for D₁ → D₂ and for D₂ → D₁.
uses
tournament_dijoin_inversion_number_le_add,tournament_inversion_number_le_dijoinhave h_le1 := tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂ have h_ge1 := tournament_inversion_number_le_dijoin V W D₁ D₂ h₁ h₂ have h_le2 := tournament_dijoin_inversion_number_le_add W V D₂ D₁ h₂ h₁ have h_ge2 := tournament_inversion_number_le_dijoin W V D₂ D₁ h₂ h₁
The inversion numbers of D₁ → D₂ and D₂ → D₁ are equal.
Substituting inv(D₂) = 0 into the bounds shows that both inv(D₁ → D₂) and inv(D₂ → D₁) are squeezed between max(inv(D₁), 0) = inv(D₁) and inv(D₁) + 0 = inv(D₁). Linear integer arithmetic (`omega`) deduces that both sides are equal to inv(D₁) and therefore equal to each other.
omega
digraph_inversion_number_eq_zero_of_is_acyclic- An acyclic directed graph has inversion number 0.
tournament_dijoin_inversion_number_le_add- The inversion number of the dijoin of two tournaments is at most the sum of their individual inversion numbers.
tournament_inversion_number_le_dijoin- The inversion number of the dijoin of two tournaments is at least the maximum of their individual inversion numbers.
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.
/-- The symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic (a transitive tournament): both sides equal inv(D₁). -/theorem tournament_dijoin_inversion_number_symm_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 D₂ D₁) := by have h2_zero := digraph_inversion_number_eq_zero_of_is_acyclic D₂ hac have h_le1 := tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂ have h_ge1 := tournament_inversion_number_le_dijoin V W D₁ D₂ h₁ h₂ have h_le2 := tournament_dijoin_inversion_number_le_add W V D₂ D₁ h₂ h₁ have h_ge2 := tournament_inversion_number_le_dijoin W V D₂ D₁ h₂ h₁ omega