AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_reverse_inversion_number_eq_of_is_acyclic_left

theoremverified

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_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 (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_leftThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).

The proof, explained

The proof proceeds by transitivity through the swapped dijoin $D₂ \to D₁$. Because $D₁$ is an acyclic tournament, the inversion number of $D₁ \to D₂$ equals that of $D₂ \to D₁$. In turn, for any tournaments $D₁$ and $D₂$, the inversion number of $D₂ \to D₁$ equals that of the reversed dijoin $\bar{D}₁ \to \bar{D}₂$. Combining these two equalities yields the result.

  1. $\operatorname{inv}(D₁ \to D₂) = \operatorname{inv}(\bar{D}₁ \to \bar{D}₂)$

    The equality is established by chaining two known results through transitivity of equality: first, since $D₁$ is an acyclic tournament, the dijoin inversion number is invariant under swapping the order of the components, so $\operatorname{inv}(D₁ \to D₂) = \operatorname{inv}(D₂ \to D₁)$ by tournament_dijoin_inversion_number_symm_of_is_acyclic_left. Second, by tournament_dijoin_swap_inversion_number_eq_reverse, the inversion number of $D₂ \to D₁$ is equal to that of $\bar{D}₁ \to \bar{D}₂$. Transitivity (.trans) connects these two equalities.

    lines 8–9

    uses tournament_dijoin_inversion_number_symm_of_is_acyclic_left, tournament_dijoin_swap_inversion_number_eq_reverse

      (tournament_dijoin_inversion_number_symm_of_is_acyclic_left V W D₁ D₂ h₁ h₂ hac).trans
        (tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂)
tournament_dijoin_inversion_number_symm_of_is_acyclic_left
For tournaments $D₁$ on $V$ and $D₂$ on $W$ where $D₁$ is acyclic, the inversion number of the dijoin $D₁ \to D₂$ equals that of the swapped dijoin $D₂ \to D₁$.
tournament_dijoin_swap_inversion_number_eq_reverse
For any tournaments $D₁$ on $V$ and $D₂$ on $W$, the inversion number of the swapped dijoin $D₂ \to D₁$ equals that of the dijoin of their reversals $\bar{D}₁ \to \bar{D}₂$.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- When D₁ is an acyclic tournament, inv(D₁ → D₂) = inv(D̄₁ → D̄₂). -/theorem tournament_dijoin_reverse_inversion_number_eq_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 (digraph_reverse D₁) (digraph_reverse D₂)) :=  (tournament_dijoin_inversion_number_symm_of_is_acyclic_left V W D₁ D₂ h₁ h₂ hac).trans    (tournament_dijoin_swap_inversion_number_eq_reverse V W D₁ D₂ h₁ h₂)
See it in the graphDiscuss this resultChallenge it