tournament_inversion_number_le_dijoin
For finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a decycling family restricts to one.
Statement
theorem tournament_inversion_number_le_dijoin (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : max (digraph_inversion_number D₁) (digraph_inversion_number D₂) ≤ digraph_inversion_number (digraph_dijoin D₁ D₂)
- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 ("the trivial lower bound inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)) always holds").
- 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 3
- tournament_dijoin_inversion_number_symm_of_is_acyclic_leftThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₁ is acyclic (a transitive tournament): both sides equal inv(D₂).
- tournament_dijoin_inversion_number_symm_of_is_acyclic_rightThe symmetry inv(D₁ → D₂) = inv(D₂ → D₁) holds when D₂ is acyclic: both sides equal inv(D₁).
- tournament_dijoin_reverse_inversion_number_le_of_eq_maxWhenever inv(D₁ → D₂) attains its theoretical minimum max(inv(D₁), inv(D₂)), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.
The proof, explained
To show that max(inv(D₁), inv(D₂)) ≤ inv(D₁ → D₂), it suffices to prove that any tournament D that embeds as an induced subtournament into the dijoin D₁ → D₂ satisfies inv(D) ≤ inv(D₁ → D₂). We take an optimal decycling family Zs for the dijoin and pull it back to D by taking preimages under the embedding. Because graph inversion commutes with taking preimages, any directed cycle in the inverted subtournament would push forward to a directed cycle in the inverted dijoin, which is impossible; thus the pulled-back family decycles D. Since its length is the same as Zs, inv(D) is bounded by inv(D₁ → D₂), and applying this to the canonical inclusions of D₁ and D₂ completes the proof.
There exists an optimal decycling family of vertex subsets for the dijoin D₁ → D₂, of length equal to inv(D₁ → D₂), whose sequential inversion leaves an acyclic digraph.
The dijoin D₁ → D₂ is a tournament by digraph_dijoin_is_tournament. By tournament_exists_family_length_eq_inversion_number, every finite tournament has a decycling family of vertex subsets achieving its inversion number.
uses
tournament_exists_family_length_eq_inversion_number,digraph_dijoin_is_tournamentobtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number (V ⊕ W) (digraph_dijoin D₁ D₂) (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂)Inverting an ambient graph E along a list of vertex subsets Zs is compatible with inverting an induced subgraph D along the preimage subsets under the embedding.
We prove by induction on Zs that if an embedding f : U → V ⊕ W induces D from E, then two vertices a, b are adjacent in the inverted subgraph if and only if f(a) and f(b) are adjacent in the inverted ambient graph. The base case where Zs is empty is immediate. In the inductive step, inverting by Z reverses an edge between f(a) and f(b) if and only if both endpoints lie in Z, which by Set.mem_preimage is equivalent to a and b lying in f ⁻¹' Z; the induction hypothesis then applies to the remaining list using List.map_cons and List.foldl_cons.
uses
List.map_cons,List.foldl_cons,Set.mem_preimagehave restrict : ∀ (U : Type) (f : U → V ⊕ W) (Zs : List (Set (V ⊕ W))) (E : Digraph (V ⊕ W)) (D : Digraph U), (∀ a b, E.Adj (f a) (f b) ↔ D.Adj a b) → ∀ a b, (Zs.foldl digraph_invert E).Adj (f a) (f b) ↔ ((Zs.map (f ⁻¹' ·)).foldl digraph_invert D).Adj a b := by intro U f Zs induction Zs with | nil => intro E D hED; simpa using hED | cons Z Zs ih => intro E D hED simp only [List.map_cons, List.foldl_cons] apply ih intro a b simp only [digraph_invert, Set.mem_preimage, hED]
Any digraph D that embeds as an induced subgraph into the dijoin D₁ → D₂ satisfies inv(D) ≤ inv(D₁ → D₂).
The inversion number of D is the infimum of lengths of decycling families, so by Nat.sInf_le it suffices to exhibit a decycling family for D of length inv(D₁ → D₂). We pull back the optimal family Zs along f via preimages; this preserved list has the same length as Zs. To show it decycles D, suppose there were a cycle from a to a in the inverted D. By the restriction lemma and induction along the transitive closure (Relation.TransGen), any directed path in the inverted D pushes forward to a directed path in the inverted dijoin, which would yield a cycle from f(a) to f(a) in the inverted dijoin. This contradicts acyclicity of the inverted dijoin, so the inverted D is acyclic.
uses
Nat.sInf_lehave lower : ∀ (U : Type) (f : U → V ⊕ W) (D : Digraph U), (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) → digraph_inversion_number D ≤ digraph_inversion_number (digraph_dijoin D₁ D₂) := by intro U f D hD apply Nat.sInf_le refine ⟨Zs.map (f ⁻¹' ·), by simp [hZl], ?_⟩ intro a ha apply hZa (f a) have hr := restrict U f Zs _ D hD have key : ∀ x y, Relation.TransGen ((Zs.map (f ⁻¹' ·)).foldl digraph_invert D).Adj x y → Relation.TransGen (Zs.foldl digraph_invert (digraph_dijoin D₁ D₂)).Adj (f x) (f y) := by intro x y hxy induction hxy with | single h => exact .single ((hr _ _).2 h) | tail _ h ih => exact .tail ih ((hr _ _).2 h) exact key a a ha
max(inv(D₁), inv(D₂)) ≤ inv(D₁ → D₂).
By max_le, it suffices to show inv(D₁) ≤ inv(D₁ → D₂) and inv(D₂) ≤ inv(D₁ → D₂). Both inequalities follow from the previous step: D₁ embeds into the dijoin via the left inclusion Sum.inl, and D₂ embeds via the right inclusion Sum.inr. In each case, the dijoin adjacency agrees with the original graph's adjacency by definition (verified by Iff.rfl), so both are induced subgraphs.
uses
max_le,Iff.rflapply max_le · exact lower V Sum.inl D₁ (fun a b => Iff.rfl) · exact lower W Sum.inr D₂ (fun a b => Iff.rfl)
tournament_exists_family_length_eq_inversion_number- Every finite tournament admits a decycling family of vertex subsets whose length equals its inversion number.
digraph_dijoin_is_tournament- The dijoin of two tournaments is a tournament.
List.map_cons- Mapping a function over a non-empty list yields the function applied to the head followed by the map of the tail.
List.foldl_cons- A left fold over a non-empty list applies the step function to the initial accumulator and head element, then folds over the tail.
Set.mem_preimage- An element belongs to 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 at most any element in the set.
max_le- The maximum of two elements is at most a bound if both elements are at most that bound.
Iff.rfl- Logical equivalence is reflexive (every proposition is equivalent to itself).
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 tournament_inversion_number_le_dijoin (V W : Type) [Fintype V] [Fintype W] (D₁ : Digraph V) (D₂ : Digraph W) (h₁ : digraph_is_tournament D₁) (h₂ : digraph_is_tournament D₂) : max (digraph_inversion_number D₁) (digraph_inversion_number D₂) ≤ digraph_inversion_number (digraph_dijoin D₁ D₂) := by obtain ⟨Zs, hZl, hZa⟩ := tournament_exists_family_length_eq_inversion_number (V ⊕ W) (digraph_dijoin D₁ D₂) (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂) -- restricting a family along an injection have restrict : ∀ (U : Type) (f : U → V ⊕ W) (Zs : List (Set (V ⊕ W))) (E : Digraph (V ⊕ W)) (D : Digraph U), (∀ a b, E.Adj (f a) (f b) ↔ D.Adj a b) → ∀ a b, (Zs.foldl digraph_invert E).Adj (f a) (f b) ↔ ((Zs.map (f ⁻¹' ·)).foldl digraph_invert D).Adj a b := by intro U f Zs induction Zs with | nil => intro E D hED; simpa using hED | cons Z Zs ih => intro E D hED simp only [List.map_cons, List.foldl_cons] apply ih intro a b simp only [digraph_invert, Set.mem_preimage, hED] have lower : ∀ (U : Type) (f : U → V ⊕ W) (D : Digraph U), (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) → digraph_inversion_number D ≤ digraph_inversion_number (digraph_dijoin D₁ D₂) := by intro U f D hD apply Nat.sInf_le refine ⟨Zs.map (f ⁻¹' ·), by simp [hZl], ?_⟩ intro a ha apply hZa (f a) have hr := restrict U f Zs _ D hD have key : ∀ x y, Relation.TransGen ((Zs.map (f ⁻¹' ·)).foldl digraph_invert D).Adj x y → Relation.TransGen (Zs.foldl digraph_invert (digraph_dijoin D₁ D₂)).Adj (f x) (f y) := by intro x y hxy induction hxy with | single h => exact .single ((hr _ _).2 h) | tail _ h ih => exact .tail ih ((hr _ _).2 h) exact key a a ha apply max_le · exact lower V Sum.inl D₁ (fun a b => Iff.rfl) · exact lower W Sum.inr D₂ (fun a b => Iff.rfl)