AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_inversion_number_symm_of_is_acyclic_left

theoremverifiedoriginal

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

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.

  1. $\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`.

    line 7

    uses digraph_inversion_number_eq_zero_of_is_acyclic

      have h0 := digraph_inversion_number_eq_zero_of_is_acyclic D₁ hac
  2. $\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$.

    lines 8–9

    uses tournament_dijoin_inversion_number_le_add

      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₁
  3. 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)$.

    lines 10–13

    uses tournament_inversion_number_le_dijoin, le_max_right, le_max_left

      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₁)
  4. $\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.

    line 14

      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)$.

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

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
See it in the graphDiscuss this resultChallenge it