tournament_dijoin_inversion_number_le_add
For finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
Statement
theorem tournament_dijoin_inversion_number_le_add (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 D₁ + digraph_inversion_number D₂
- Formalizes
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 ("it is easy to see that inv(D₁ → D₂) ≤ inv(D₁) + inv(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_is_acyclic_dijoinThe dijoin of two acyclic digraphs is acyclic: a directed walk never comes back from the D₂ side to the D₁ side.
- 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_addWhenever inv(D̄₁ → D̄₂) attains its theoretical maximum inv(D₁) + inv(D₂), the inequality inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) holds.
The proof, explained
The inversion number of a tournament is the minimum number of subset inversions needed to make it acyclic. We obtain optimal inverting families Xs for D₁ and Ys for D₂ of lengths inv(D₁) and inv(D₂). Because inverting a subset lying entirely within one component leaves all cross-edges and the other component intact, successively inverting the embedded family Xs and then the embedded family Ys produces the dijoin of the two acyclic graphs. Since the dijoin of acyclic graphs is acyclic, this concatenated family witnesses that inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂).
There exist optimal inverting families Xs for D₁ and Ys for D₂ of lengths inv(D₁) and inv(D₂), respectively, that render each tournament acyclic.
Applying tournament_exists_family_length_eq_inversion_number to tournaments D₁ and D₂ yields an inverting list Xs of length inv(D₁) making D₁ acyclic, and an inverting list Ys of length inv(D₂) making D₂ acyclic.
uses
tournament_exists_family_length_eq_inversion_numberobtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D₁ h₁ obtain ⟨Ys, hYl, hYa⟩ := tournament_exists_family_length_eq_inversion_number W D₂ h₂
Inverting the dijoin E₁ → E₂ by a subset X ⊆ V (embedded via Sum.inl) inverts only the left digraph E₁ and preserves the rest of the dijoin (stepL).
We verify that the adjacency relations agree for all vertex pairs (x, y) in V ⊕ W. By case analysis on whether x and y belong to V or W, cross-edges from V to W as well as edges within W never have both endpoints in Sum.inl '' X, so they are not inverted. For pairs both in V, both endpoints lie in Sum.inl '' X if and only if they lie in X, which matches the inversion of E₁ by X.
uses
Or.inl,Or.inrhave stepL : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (X : Set V), digraph_invert (digraph_dijoin E₁ E₂) (Sum.inl '' X) = digraph_dijoin (digraph_invert E₁ X) E₂ := by intro E₁ E₂ X ext x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_invert, digraph_dijoin] constructor · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩ · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩
Inverting the dijoin E₁ → E₂ by a subset Y ⊆ W (embedded via Sum.inr) inverts only the right digraph E₂ and preserves the rest of the dijoin (stepR).
Symmetrically to stepL, only pairs of vertices with both endpoints in W can both belong to Sum.inr '' Y. Thus, edges within V and cross-edges from V to W are unchanged, while edges within W are inverted precisely when both endpoints lie in Y.
uses
Or.inl,Or.inrhave stepR : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (Y : Set W), digraph_invert (digraph_dijoin E₁ E₂) (Sum.inr '' Y) = digraph_dijoin E₁ (digraph_invert E₂ Y) := by intro E₁ E₂ Y ext x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_invert, digraph_dijoin] constructor · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩ · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩
Iterating inversions along a list Xs of subsets of V (embedded via Sum.inl) transforms the dijoin E₁ → E₂ into (foldl invert E₁ Xs) → E₂ (foldL).
This is proved by induction on the list Xs. The empty list case holds by definition. In the induction step, folding across X :: Xs simplifies using List.map_cons, List.foldl_cons, the single-step lemma stepL, and the induction hypothesis.
uses
List.map_cons,List.foldl_conshave foldL : ∀ (Xs : List (Set V)) (E₁ : Digraph V) (E₂ : Digraph W), (Xs.map (Sum.inl '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) = digraph_dijoin (Xs.foldl digraph_invert E₁) E₂ := by intro Xs induction Xs with | nil => intro E₁ E₂; rfl | cons X Xs ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepL, ih]
Iterating inversions along a list Ys of subsets of W (embedded via Sum.inr) transforms the dijoin E₁ → E₂ into E₁ → (foldl invert E₂ Ys) (foldR).
This is proved by induction on the list Ys. The empty list case holds by definition. In the induction step, folding across Y :: Ys simplifies using List.map_cons, List.foldl_cons, the single-step lemma stepR, and the induction hypothesis.
uses
List.map_cons,List.foldl_conshave foldR : ∀ (Ys : List (Set W)) (E₁ : Digraph V) (E₂ : Digraph W), (Ys.map (Sum.inr '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) = digraph_dijoin E₁ (Ys.foldl digraph_invert E₂) := by intro Ys induction Ys with | nil => intro E₁ E₂; rfl | cons Y Ys ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepR, ih]
The inversion number of the dijoin D₁ → D₂ is at most inv(D₁) + inv(D₂).
The inversion number is defined as the infimum of lengths of families whose successive inversions produce an acyclic digraph. By Nat.sInf_le, it suffices to exhibit one such family. We concatenate the embedded lists Xs and Ys; its length is inv(D₁) + inv(D₂). Folding over this concatenation splits by List.foldl_append, foldL, and foldR into the dijoin of the two individually inverted tournaments. Since both components are acyclic, their dijoin is acyclic by digraph_is_acyclic_dijoin.
uses
Nat.sInf_le,List.foldl_append,digraph_is_acyclic_dijoinapply Nat.sInf_le refine ⟨Xs.map (Sum.inl '' ·) ++ Ys.map (Sum.inr '' ·), by simp [hXl, hYl], ?_⟩ rw [List.foldl_append, foldL, foldR] exact digraph_is_acyclic_dijoin _ _ hXa hYa
tournament_exists_family_length_eq_inversion_number- Every finite tournament has a sequence of subset inversions of length equal to its inversion number that makes it acyclic.
Or.inl- From a proof of P, deduce P ∨ Q.
Or.inr- From a proof of Q, deduce P ∨ Q.
List.map_cons- Mapping a function over a non-empty list a :: l yields f(a) :: map(f, l).
List.foldl_cons- Left-folding over a non-empty list a :: l from accumulator b equals left-folding over l from f(b, a).
Nat.sInf_le- If a natural number m belongs to a set s of natural numbers, then the infimum of s is at most m.
List.foldl_append- Left-folding over the concatenation l ++ l' equals left-folding over l' starting from the result of folding over l.
digraph_is_acyclic_dijoin- The dijoin of two acyclic directed graphs is acyclic.
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_dijoin_inversion_number_le_add (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 D₁ + digraph_inversion_number D₂ := by obtain ⟨Xs, hXl, hXa⟩ := tournament_exists_family_length_eq_inversion_number V D₁ h₁ obtain ⟨Ys, hYl, hYa⟩ := tournament_exists_family_length_eq_inversion_number W D₂ h₂ have stepL : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (X : Set V), digraph_invert (digraph_dijoin E₁ E₂) (Sum.inl '' X) = digraph_dijoin (digraph_invert E₁ X) E₂ := by intro E₁ E₂ X ext x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_invert, digraph_dijoin] constructor · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩ · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩ have stepR : ∀ (E₁ : Digraph V) (E₂ : Digraph W) (Y : Set W), digraph_invert (digraph_dijoin E₁ E₂) (Sum.inr '' Y) = digraph_dijoin E₁ (digraph_invert E₂ Y) := by intro E₁ E₂ Y ext x y rcases x with a | a <;> rcases y with b | b <;> simp [digraph_invert, digraph_dijoin] constructor · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun ha hb => h1 _ ha rfl _ hb rfl, h2⟩ · rintro (h | ⟨h1, h2⟩) · exact Or.inl h · exact Or.inr ⟨fun x hx hxa y hy hyb => h1 (hxa ▸ hx) (hyb ▸ hy), h2⟩ have foldL : ∀ (Xs : List (Set V)) (E₁ : Digraph V) (E₂ : Digraph W), (Xs.map (Sum.inl '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) = digraph_dijoin (Xs.foldl digraph_invert E₁) E₂ := by intro Xs induction Xs with | nil => intro E₁ E₂; rfl | cons X Xs ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepL, ih] have foldR : ∀ (Ys : List (Set W)) (E₁ : Digraph V) (E₂ : Digraph W), (Ys.map (Sum.inr '' ·)).foldl digraph_invert (digraph_dijoin E₁ E₂) = digraph_dijoin E₁ (Ys.foldl digraph_invert E₂) := by intro Ys induction Ys with | nil => intro E₁ E₂; rfl | cons Y Ys ih => intro E₁ E₂; simp only [List.map_cons, List.foldl_cons, stepR, ih] apply Nat.sInf_le refine ⟨Xs.map (Sum.inl '' ·) ++ Ys.map (Sum.inr '' ·), by simp [hXl, hYl], ?_⟩ rw [List.foldl_append, foldL, foldR] exact digraph_is_acyclic_dijoin _ _ hXa hYa