AFTD Auto-Formalizing Theoretical Domains

digraph_inversion_number_le_of_adj_iff_reverse

theoremverified

If G's arcs are E's arcs pulled back along a map f and reversed (x → y in G iff f y → f x in E), and E is a finite tournament, then inv(G) ≤ inv(E): a decycling family of E pulls back to one of G of the same length.

Statement

theorem digraph_inversion_number_le_of_adj_iff_reverse {U U' : Type} [Fintype U']
    (G : Digraph U) (E : Digraph U') (f : U → U') (hE : digraph_is_tournament E)
    (hGE : ∀ x y, G.Adj x y ↔ E.Adj (f y) (f x)) :
    digraph_inversion_number G ≤ digraph_inversion_number E
Source
Helper for the reduction in arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 4 (a set of inversions decycles D iff it decycles D̄; inv(D₂ → D₁) = inv(D̄₁ → D̄₂)).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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_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.
  • 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 2

The proof, explained

To show that inv(G) ≤ inv(E), we take an optimal decycling family Zs for the tournament E, of length inv(E), and pull it back to G via preimages under f. An induction on the list of subsets shows that inverting G along preimages preserves the reversed adjacency relation at each step: x → y in the inverted G if and only if f(y) → f(x) in the inverted E. Consequently, every directed path in the inverted G reverses to a directed path in the inverted E. Any cycle in the inverted G would therefore push forward to a cycle in the inverted E, contradicting its acyclicity and establishing that the pulled-back family decycles G.

  1. There exists an optimal decycling family for the tournament E whose length equals the inversion number of E.

    Applying tournament_exists_family_length_eq_inversion_number to the finite tournament E provides a list Zs of vertex subsets whose length is inv(E) and such that inverting E successively along Zs produces an acyclic digraph.

    line 5

    uses tournament_exists_family_length_eq_inversion_number

      obtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number U' E hE
  2. Inverting G along the preimages f⁻¹(Z) preserves the reversed adjacency relation with the inverted tournament E.

    We prove by induction on Zs that an arc exists from x to y in the inverted G if and only if an arc exists from f(y) to f(x) in the inverted E. The base case (an empty list) is the initial hypothesis. For the inductive step, inverting along f⁻¹(Z) reverses adjacency between x and y precisely when both vertices lie in f⁻¹(Z), which is equivalent to f(x) and f(y) both lying in Z; thus the single-step inversion preserves the reversed adjacency relation, and the induction hypothesis applies to the rest of the list.

    lines 6–19

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

      have rev : ∀ (Zs : List (Set U')) (E : Digraph U') (G : Digraph U),
          (∀ x y, G.Adj x y ↔ E.Adj (f y) (f x)) →
          ∀ x y, ((Zs.map (f ⁻¹' ·)).foldl digraph_invert G).Adj x y ↔
            (Zs.foldl digraph_invert E).Adj (f y) (f 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 inversion number of G is at most that of E, provided that inverting G along the preimage family yields an acyclic digraph.

    By definition, the inversion number is the infimum of the lengths of decycling families. The pulled-back family of subsets Zs.map (f ⁻¹' ·) has length equal to the length of Zs, which equals inv(E). By Nat.sInf_le, showing that this family decycles G bounds inv(G) ≤ inv(E).

    lines 20–21

    uses Nat.sInf_le

      apply Nat.sInf_le
      refine ⟨Zs.map (f ⁻¹' ·), by simp [hZl], ?_⟩
  4. The digraph obtained by inverting G along the preimage family is acyclic.

    Suppose for contradiction that there is a cycle at vertex x in the inverted G. By induction on paths (TransGen), any directed path from u to v in the inverted G reverses to a directed path from f(v) to f(u) in the inverted E, because every individual step reverses by the lemma rev proved in the second step. In particular, the cycle at x in G yields a cycle at f(x) in the inverted E, contradicting the fact that inverting E along Zs yields an acyclic digraph.

    lines 22–31

      intro x hx
      apply hZa (f x)
      have hr := rev Zs E G hGE
      have key : ∀ x y, Relation.TransGen ((Zs.map (f ⁻¹' ·)).foldl digraph_invert G).Adj x y →
          Relation.TransGen (Zs.foldl digraph_invert E).Adj (f y) (f 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
tournament_exists_family_length_eq_inversion_number
every finite tournament admits a decycling family of vertex 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
folding over a cons list applies the fold operation to the accumulator and the head, then continues over the tail
digraph_invert
inverting a digraph on a set of vertices reverses arcs between pairs both in the set and leaves all other arcs unchanged
Set.mem_preimage
an element belongs to the preimage of a set under a map 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 element in 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 digraph_inversion_number_le_of_adj_iff_reverse {U U' : Type} [Fintype U']    (G : Digraph U) (E : Digraph U') (f : U → U') (hE : digraph_is_tournament E)    (hGE : ∀ x y, G.Adj x y ↔ E.Adj (f y) (f x)) :    digraph_inversion_number G ≤ digraph_inversion_number E := by  obtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number U' E hE  have rev : ∀ (Zs : List (Set U')) (E : Digraph U') (G : Digraph U),      (∀ x y, G.Adj x y ↔ E.Adj (f y) (f x)) →      ∀ x y, ((Zs.map (f ⁻¹' ·)).foldl digraph_invert G).Adj x y ↔        (Zs.foldl digraph_invert E).Adj (f y) (f 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  apply Nat.sInf_le  refine ⟨Zs.map (f ⁻¹' ·), by simp [hZl], ?_⟩  intro x hx  apply hZa (f x)  have hr := rev Zs E G hGE  have key : ∀ x y, Relation.TransGen ((Zs.map (f ⁻¹' ·)).foldl digraph_invert G).Adj x y →      Relation.TransGen (Zs.foldl digraph_invert E).Adj (f y) (f 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