AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_inversion_number_symm_of_is_acyclic_right

theoremverified

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

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.

  1. 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.

    line 8

    uses digraph_inversion_number_eq_zero_of_is_acyclic

      have h2_zero := digraph_inversion_number_eq_zero_of_is_acyclic D₂ hac
  2. Both 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₁.

    lines 9–12

    uses tournament_dijoin_inversion_number_le_add, tournament_inversion_number_le_dijoin

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

    line 13

      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

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