tournament_dijoin_inversion_number_symm_of_is_acyclic_left
The symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).
Statement
theorem tournament_dijoin_inversion_number_symm_of_is_acyclic_left (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₁)
- Related work
- Special case of Conjecture 4.1 of arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins): one side transitive. Both dijoins have inversion number inv(D₂) by the bounds inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂) and inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)) of the same paper's Sec. 1.
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- digraph_invertThe inversion of a vertex set X in a digraph D: the digraph obtained by reversing every arc with both endpoints in X and keeping every…
- 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…
- 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…
- digraph_inversion_number_eq_zero_of_is_acyclicAn acyclic digraph has inversion number 0.
- digraph_dijoin_is_tournamentThe dijoin of two tournaments is a tournament.
- Used by 1
- tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_leftWhen 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 squeezed between the maximum and the sum of the components' inversion numbers. Because $D_1$ is acyclic, its inversion number is 0, which forces both the upper bound and the lower bound for each dijoin to equal $\operatorname{inv}(D_2)$. Consequently, both $\operatorname{inv}(D_1 \to D_2)$ and $\operatorname{inv}(D_2 \to D_1)$ equal $\operatorname{inv}(D_2)$ and are therefore equal.
$\operatorname{inv}(D_1) = 0$
Since $D_1$ is acyclic (hypothesis `hac`), its inversion number is zero by `digraph_inversion_number_eq_zero_of_is_acyclic`.
uses
digraph_inversion_number_eq_zero_of_is_acyclichave h0 := digraph_inversion_number_eq_zero_of_is_acyclic D₁ hac$\operatorname{inv}(D_1 \to D_2) \le \operatorname{inv}(D_1) + \operatorname{inv}(D_2)$ and $\operatorname{inv}(D_2 \to D_1) \le \operatorname{inv}(D_2) + \operatorname{inv}(D_1)$
The inversion number of the dijoin of two tournaments is bounded from above by the sum of their individual inversion numbers (`tournament_dijoin_inversion_number_le_add`). This inequality is instantiated for both orientations $D_1 \to D_2$ and $D_2 \to D_1$.
uses
tournament_dijoin_inversion_number_le_addhave a1 := tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂ have a2 := tournament_dijoin_inversion_number_le_add W V D₂ D₁ h₂ h₁
The inversion number of each dijoin is bounded from below by the maximum of the components' inversion numbers, which in turn is at least $\operatorname{inv}(D_2)$.
By `tournament_inversion_number_le_dijoin`, each dijoin's inversion number is bounded below by the maximum of the inversion numbers of its components: $\max(\operatorname{inv}(D_1), \operatorname{inv}(D_2)) \le \operatorname{inv}(D_1 \to D_2)$ and $\max(\operatorname{inv}(D_2), \operatorname{inv}(D_1)) \le \operatorname{inv}(D_2 \to D_1)$. The lemmas `le_max_right` and `le_max_left` then establish that both maxima are at least $\operatorname{inv}(D_2)$.
uses
tournament_inversion_number_le_dijoin,le_max_right,le_max_lefthave b1 := tournament_inversion_number_le_dijoin V W D₁ D₂ h₁ h₂ have b2 := tournament_inversion_number_le_dijoin W V D₂ D₁ h₂ h₁ have c1 := le_max_right (digraph_inversion_number D₁) (digraph_inversion_number D₂) have c2 := le_max_left (digraph_inversion_number D₂) (digraph_inversion_number D₁)
$\operatorname{inv}(D_1 \to D_2) = \operatorname{inv}(D_2 \to D_1)$
Since $\operatorname{inv}(D_1) = 0$, the upper bounds $\operatorname{inv}(D_1 \to D_2) \le 0 + \operatorname{inv}(D_2)$ and $\operatorname{inv}(D_2 \to D_1) \le \operatorname{inv}(D_2) + 0$ collapse to $\operatorname{inv}(D_2)$, while the lower bounds squeeze both values from below by $\operatorname{inv}(D_2)$. Thus both dijoin inversion numbers equal $\operatorname{inv}(D_2)$. The linear arithmetic tactic `omega` closes the equality goal from these hypotheses.
omega
digraph_inversion_number_eq_zero_of_is_acyclic- An acyclic directed graph has inversion number 0.
tournament_dijoin_inversion_number_le_add- For any tournaments $D_1$ and $D_2$, the inversion number of their dijoin is at most the sum of their inversion numbers: $\operatorname{inv}(D_1 \to D_2) \le \operatorname{inv}(D_1) + \operatorname{inv}(D_2)$.
tournament_inversion_number_le_dijoin- For any tournaments $D_1$ and $D_2$, the inversion number of their dijoin is at least the maximum of their inversion numbers: $\max(\operatorname{inv}(D_1), \operatorname{inv}(D_2)) \le \operatorname{inv}(D_1 \to D_2)$.
le_max_right- In any linear order, the right argument is less than or equal to the maximum: $b \le \max(a, b)$.
le_max_left- In any linear order, the left argument is less than or equal to the maximum: $a \le \max(a, b)$.
- Lines 12–13 explicitly supply the inequalities $\operatorname{inv}(D_2) \le \max(\operatorname{inv}(D_1), \operatorname{inv}(D_2))$ and $\operatorname{inv}(D_2) \le \max(\operatorname{inv}(D_2), \operatorname{inv}(D_1))$ because the `omega` tactic handles linear arithmetic over $\mathbb{N}$ but does not natively reason about the $\max$ operation.
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_inversion_number_symm_of_is_acyclic_left (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 h0 := digraph_inversion_number_eq_zero_of_is_acyclic D₁ hac have a1 := tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂ have a2 := tournament_dijoin_inversion_number_le_add W V D₂ D₁ h₂ h₁ have b1 := tournament_inversion_number_le_dijoin V W D₁ D₂ h₁ h₂ have b2 := tournament_inversion_number_le_dijoin W V D₂ D₁ h₂ h₁ have c1 := le_max_right (digraph_inversion_number D₁) (digraph_inversion_number D₂) have c2 := le_max_left (digraph_inversion_number D₂) (digraph_inversion_number D₁) omega