AFTD Auto-Formalizing Theoretical Domains

tournament_dijoin_inversion_number_le_symm_add_two

theoremverifiedformalization

For finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₂ → D₁) + 2 (with D₁, D₂ swapped this gives |inv(D₁ → D₂) − inv(D₂ → D₁)| ≤ 2): invert V(D₁) and V(D₂) first, which turns D₁ → D₂ into the reverse of D₂ → D₁, and a family decycles a digraph iff it decycles its reverse.

Statement

theorem tournament_dijoin_inversion_number_le_symm_add_two
    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)
    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) :
    digraph_inversion_number (digraph_dijoin D₁ D₂) ≤
      digraph_inversion_number (digraph_dijoin D₂ D₁) + 2
Formalizes
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4 (remark after Conjecture 4.1: |inv(D₁ → D₂) − inv(D̄₁ → D̄₂)| ≤ 2 and inv(D₂ → D₁) = inv(D̄₁ → D̄₂)).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
  • digraph_dijoin_is_tournamentThe dijoin of two tournaments is a tournament.
  • tournament_exists_family_length_eq_inversion_numberFor a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
Used by 1

The proof, explained

To bound the inversion number of D₁ → D₂, we invert the vertex sets V and W first, which leaves the cross edges intact while reversing the internal edges of D₁ and D₂. Under swapping the two components, the resulting digraph is the reverse of D₂ → D₁. An optimal decycling family Zs for D₂ → D₁ can then be transported back via preimages, decycling the reversed graph; prepending V and W to this transported family gives an acyclic digraph of length inv(D₂ → D₁) + 2.

  1. There exists a decycling family Zs for the dijoin D₂ → D₁ whose length equals the inversion number of D₂ → D₁.

    By tournament_exists_family_length_eq_inversion_number applied to the dijoin D₂ → D₁, which is a tournament by digraph_dijoin_is_tournament, we obtain an optimal decycling family Zs of subsets of W ⊕ V.

    lines 6–7

    uses tournament_exists_family_length_eq_inversion_number, digraph_dijoin_is_tournament

      obtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number (W ⊕ V)
        (digraph_dijoin D₂ D₁) (digraph_dijoin_is_tournament D₂ D₁ h₂ h₁)
  2. Inverting the preimages of a list of subsets on a graph G produces the reverse of inverting the original subsets on a graph E, provided G is the reverse of E under Sum.swap.

    We prove this general property by induction on the list of subsets Zs. In the base case (an empty list), the graphs are unchanged and the hypothesis hGE holds directly. In the induction step, folding a single subset inversion preserves the reversed-edge relationship under preimages, which simplifies by definition and propositional reasoning before applying the induction hypothesis.

    lines 8–22

    uses List.map_cons, List.foldl_cons, Set.mem_preimage

      -- a family transported along `f` acts on a digraph that is the reverse of the pullback
      have rev : ∀ (Zs : List (Set (W ⊕ V))) (E : Digraph (W ⊕ V)) (G : Digraph (V ⊕ W)),
          (∀ x y, G.Adj x y ↔ E.Adj (Sum.swap y) (Sum.swap x)) →
          ∀ x y, ((Zs.map (Sum.swap ⁻¹' ·)).foldl digraph_invert G).Adj x y ↔
            (Zs.foldl digraph_invert E).Adj (Sum.swap y) (Sum.swap x) := by
        intro Zs
        induction Zs with
        | nil => intro E G hGE; simpa using hGE
        | cons Z Zs ih =>
          intro E G hGE
          simp only [List.map_cons, List.foldl_cons]
          apply ih
          intro x y
          simp only [digraph_invert, Set.mem_preimage, hGE]
          tauto
  3. The graph G, obtained from D₁ → D₂ by inverting V and then inverting W, is isomorphic via Sum.swap to the reverse digraph of D₂ → D₁. automation

    By case analysis on whether the endpoints lie in V or W, inverting V reverses edges within D₁ while inverting W reverses edges within D₂, and neither inversion affects the cross edges from V to W. The resulting adjacencies match the swapped and reversed adjacencies of D₂ → D₁.

    lines 23–29

      let G : Digraph (V ⊕ W) :=
        digraph_invert (digraph_invert (digraph_dijoin D₁ D₂) (Set.range Sum.inl))
          (Set.range Sum.inr)
      have hG : ∀ x y, G.Adj x y ↔ (digraph_dijoin D₂ D₁).Adj (Sum.swap y) (Sum.swap x) := by
        intro x y
        rcases x with a | a <;> rcases y with b | b <;>
          simp [G, digraph_invert, digraph_dijoin]
  4. The inversion number of D₁ → D₂ is at most the inversion number of D₂ → D₁ plus 2, provided that prepending V and W to the preimages of Zs yields an acyclic digraph.

    We construct the candidate family consisting of V (the range of Sum.inl), W (the range of Sum.inr), and the preimages under Sum.swap of each set in Zs. By Nat.sInf_le and definition of the inversion number as an infimum, its length |Zs| + 2 bounds the inversion number of D₁ → D₂.

    lines 30–32

    uses Nat.sInf_le

      apply Nat.sInf_le
      refine ⟨Set.range Sum.inl :: Set.range Sum.inr :: Zs.map (Sum.swap ⁻¹' ·),
        by simp [hZl], ?_⟩
  5. To show that the candidate family decycles D₁ → D₂, it suffices to show that any cycle in the inverted graph would induce a cycle in the inverted D₂ → D₁.

    Suppose there is a cycle containing vertex x. After the first two inversions of V and W, the graph is G. Applying the acyclicity of Zs on D₂ → D₁ to Sum.swap x, the goal reduces to producing a cycle from Sum.swap x to Sum.swap x in the inverted D₂ → D₁.

    lines 33–36

    uses List.foldl_cons

      intro x hx
      simp only [List.foldl_cons] at hx
      apply hZa (Sum.swap x)
      have hr := rev Zs _ G hG
  6. Any directed path in the inverted D₁ → D₂ corresponds to a reversed directed path in the inverted D₂ → D₁, completing the proof by contradiction.

    By induction on the transitive closure of the adjacency relation, each directed edge from x to y corresponds by the lemma rev to a reversed edge from Sum.swap y to Sum.swap x. Applying this to the cycle at x produces a self-loop in the transitive closure of the inverted D₂ → D₁, contradicting its acyclicity.

    lines 37–44

      have key : ∀ x y, Relation.TransGen ((Zs.map (Sum.swap ⁻¹' ·)).foldl digraph_invert G).Adj x y →
          Relation.TransGen (Zs.foldl digraph_invert (digraph_dijoin D₂ D₁)).Adj
            (Sum.swap y) (Sum.swap x) := by
        intro x y hxy
        induction hxy with
        | single h => exact .single ((hr _ _).1 h)
        | tail _ h ih => exact .head ((hr _ _).1 h) ih
      exact key x x hx
digraph_dijoin_is_tournament
The dijoin of two tournaments is itself a tournament.
tournament_exists_family_length_eq_inversion_number
Every finite tournament has a decycling family of subsets whose length equals its inversion number.
List.map_cons
Mapping a function over a cons list applies the function to the head and maps over the tail.
List.foldl_cons
Left-folding over a cons list applies the function to the initial accumulator and the head, then folds over the tail.
Set.mem_preimage
An element is in the preimage of a set under a function if and only if its image belongs to the set.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any member of the set.

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_le_symm_add_two    (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W)    (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) :    digraph_inversion_number (digraph_dijoin D₁ D₂) ≤      digraph_inversion_number (digraph_dijoin D₂ D₁) + 2 := by  obtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number (W ⊕ V)    (digraph_dijoin D₂ D₁) (digraph_dijoin_is_tournament D₂ D₁ h₂ h₁)  -- a family transported along `f` acts on a digraph that is the reverse of the pullback  have rev : ∀ (Zs : List (Set (W ⊕ V))) (E : Digraph (W ⊕ V)) (G : Digraph (V ⊕ W)),      (∀ x y, G.Adj x y ↔ E.Adj (Sum.swap y) (Sum.swap x)) →      ∀ x y, ((Zs.map (Sum.swap ⁻¹' ·)).foldl digraph_invert G).Adj x y ↔        (Zs.foldl digraph_invert E).Adj (Sum.swap y) (Sum.swap x) := by    intro Zs    induction Zs with    | nil => intro E G hGE; simpa using hGE    | cons Z Zs ih =>      intro E G hGE      simp only [List.map_cons, List.foldl_cons]      apply ih      intro x y      simp only [digraph_invert, Set.mem_preimage, hGE]      tauto  let G : Digraph (V ⊕ W) :=    digraph_invert (digraph_invert (digraph_dijoin D₁ D₂) (Set.range Sum.inl))      (Set.range Sum.inr)  have hG : ∀ x y, G.Adj x y ↔ (digraph_dijoin D₂ D₁).Adj (Sum.swap y) (Sum.swap x) := by    intro x y    rcases x with a | a <;> rcases y with b | b <;>      simp [G, digraph_invert, digraph_dijoin]  apply Nat.sInf_le  refine ⟨Set.range Sum.inl :: Set.range Sum.inr :: Zs.map (Sum.swap ⁻¹' ·),    by simp [hZl], ?_⟩  intro x hx  simp only [List.foldl_cons] at hx  apply hZa (Sum.swap x)  have hr := rev Zs _ G hG  have key : ∀ x y, Relation.TransGen ((Zs.map (Sum.swap ⁻¹' ·)).foldl digraph_invert G).Adj x y →      Relation.TransGen (Zs.foldl digraph_invert (digraph_dijoin D₂ D₁)).Adj        (Sum.swap y) (Sum.swap x) := by    intro x y hxy    induction hxy with    | single h => exact .single ((hr _ _).1 h)    | tail _ h ih => exact .head ((hr _ _).1 h) ih  exact key x x hx
See it in the graphDiscuss this resultChallenge it