AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_reverse_inversion_number_le_of_eq_add

theoremverified

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

Statement

theorem tournament_dijoin_reverse_inversion_number_le_of_eq_add
    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)
    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂)
    (hadd : digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂)) =
      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 5
  • 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.
  • 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₂.

The proof, explained

The proof rewrites the right-hand side of the goal using the hypothesis that inv(D̄₁ → D̄₂) = inv(D₁) + inv(D₂). This reduces the goal to showing that inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), which holds by the general upper bound for the inversion number of a tournament dijoin (tournament_dijoin_inversion_number_le_add).

  1. It suffices to show that inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂).

    Using the equality assumption (hadd), we rewrite the right-hand side of the target inequality, replacing the inversion number of the dijoin of the reversed tournaments, inv(D̄₁ → D̄₂), with the sum of the individual inversion numbers inv(D₁) + inv(D₂).

    line 9

      rw [hadd]
  2. The inequality inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂) holds.

    This follows directly from the general subadditivity theorem tournament_dijoin_inversion_number_le_add applied to the tournaments D₁ and D₂.

    line 10

    uses tournament_dijoin_inversion_number_le_add

      exact tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂
tournament_dijoin_inversion_number_le_add
For any finite tournaments D₁ and D₂, the inversion number of their dijoin D₁ → D₂ is at most the sum of their individual inversion numbers, inv(D₁) + inv(D₂).

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̄₂) = inv(D₁) + inv(D₂), inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂). -/theorem tournament_dijoin_reverse_inversion_number_le_of_eq_add    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂)    (hadd : digraph_inversion_number (digraph_dijoin (digraph_reverse D₁) (digraph_reverse D₂)) =      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 [hadd]  exact tournament_dijoin_inversion_number_le_add V W D₁ D₂ h₁ h₂
See it in the graphDiscuss this resultChallenge it