digraph_inversion_number_le_of_adj_iff_reverse
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
- tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
- tournament_dijoin_swap_inversion_number_eq_reverseFor finite tournaments D₁, D₂: inv(D₂ → D₁) = inv(D̄₁ → D̄₂). So the symmetry conjecture inv(D₁ → D₂) = inv(D₂ → D₁) says exactly that the…
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.
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.
uses
tournament_exists_family_length_eq_inversion_numberobtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number U' E hEInverting 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.
uses
List.map_cons,List.foldl_cons,digraph_invert,Set.mem_preimagehave 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
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).
uses
Nat.sInf_leapply Nat.sInf_le refine ⟨Zs.map (f ⁻¹' ·), by simp [hZl], ?_⟩
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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