AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_reverse_inversion_number_le_of_eq_max

theoremverified

Whenever inv(D₁ → D₂) attains its theoretical minimum max(inv(D₁), inv(D₂)), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.

Statement

theorem tournament_dijoin_reverse_inversion_number_le_of_eq_max
    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)
    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂)
    (hmax : digraph_inversion_number (digraph_dijoin D₁ D₂) =
      max (digraph_inversion_number D₁) (digraph_inversion_number 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_reverse_is_tournamentThe reverse of a tournament is a tournament.
  • 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…
  • tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.

The proof, explained

The proof substitutes the assumption inv(D₁ → D₂) = max(inv(D₁), inv(D₂)) into the left-hand side of the goal. It then applies the general lower bound max(inv(T₁), inv(T₂)) ≤ inv(T₁ → T₂) to the reversed tournaments D̄₁ and D̄₂. Because the inversion number of a tournament is preserved under edge reversal, this lower bound simplifies to the rewritten goal.

  1. It suffices to prove max(inv(D₁), inv(D₂)) ≤ inv(D̄₁ → D̄₂).

    Using the hypothesis that inv(D₁ → D₂) = max(inv(D₁), inv(D₂)), we substitute this maximum for the left-hand side of the inequality to be proved.

    line 9

      rw [hmax]
  2. max(inv(D̄₁), inv(D̄₂)) ≤ inv(D̄₁ → D̄₂).

    Because reversing a tournament yields another tournament, D̄₁ and D̄₂ are tournaments. The general lower bound on the inversion number of a dijoin then applies to D̄₁ and D̄₂, showing that inv(D̄₁ → D̄₂) is at least max(inv(D̄₁), inv(D̄₂)).

    lines 10–12

    uses digraph_reverse_is_tournament, tournament_inversion_number_le_dijoin

      have hrev₁ := digraph_reverse_is_tournament D₁ h₁
      have hrev₂ := digraph_reverse_is_tournament D₂ h₂
      have hle := tournament_inversion_number_le_dijoin V W (digraph_reverse D₁) (digraph_reverse D₂) hrev₁ hrev₂
  3. max(inv(D₁), inv(D₂)) ≤ inv(D̄₁ → D̄₂).

    The inversion number of any tournament is equal to that of its reversal. Substituting inv(D̄₁) = inv(D₁) and inv(D̄₂) = inv(D₂) into the previous inequality gives the required bound.

    lines 13–14

    uses tournament_inversion_number_reverse

      rw [tournament_inversion_number_reverse V D₁ h₁, tournament_inversion_number_reverse W D₂ h₂] at hle
      exact hle
digraph_reverse_is_tournament
Reversing all edges of a tournament yields another tournament.
tournament_inversion_number_le_dijoin
The inversion number of the dijoin of two tournaments is at least the maximum of their individual inversion numbers.
tournament_inversion_number_reverse
The inversion number of a tournament is invariant under reversing edge directions.

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

/-- Whenever inv(D₁ → D₂) = max(inv(D₁), inv(D₂)), inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂). -/theorem tournament_dijoin_reverse_inversion_number_le_of_eq_max    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂)    (hmax : digraph_inversion_number (digraph_dijoin D₁ D₂) =      max (digraph_inversion_number D₁) (digraph_inversion_number D₂)) :    digraph_inversion_number (digraph_dijoin D₁ D₂) ≤      digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂)) := by  rw [hmax]  have hrev₁ := digraph_reverse_is_tournament D₁ h₁  have hrev₂ := digraph_reverse_is_tournament D₂ h₂  have hle := tournament_inversion_number_le_dijoin V W (digraph_reverse D₁) (digraph_reverse D₂) hrev₁ hrev₂  rw [tournament_inversion_number_reverse V D₁ h₁, tournament_inversion_number_reverse W D₂ h₂] at hle  exact hle
See it in the graphDiscuss this resultChallenge it