tournament_exists_family_length_eq_inversion_number
For a finite tournament D, the inversion number is attained: some decycling family of D has exactly inv(D) sets.
Statement
theorem tournament_exists_family_length_eq_inversion_number (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ Xs : List (Set V), Xs.length = digraph_inversion_number D ∧ digraph_is_acyclic (Xs.foldl digraph_invert D)
- Source
- Helper for the bounds on inversion numbers of dijoins in arXiv:2610.13798 (Sec. 1 and Sec. 4): the infimum defining inv(D) is a minimum.
- Verified
- 13 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- 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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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_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…
- Used by 5
- tournament_dijoin_inversion_number_le_addFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≤ inv(D₁) + inv(D₂), by inverting an optimal family of D₁ and then one of D₂.
- digraph_inversion_number_le_of_adj_iff_reverseIf 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)…
- tournament_dijoin_inversion_number_le_symm_add_twoFor 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…
- tournament_min_rank_le_inversion_numberFor a finite tournament D: tmr(D) ≤ inv(D).
- tournament_inversion_number_le_dijoinFor finite tournaments D₁, D₂: inv(D₁ → D₂) ≥ max(inv(D₁), inv(D₂)), since D₁ and D₂ are induced subtournaments of the dijoin and a…
The proof, explained
The inversion number of a tournament D is defined as the infimum of the lengths of all decycling families for D. By `tournament_exists_decycling_family`, every finite tournament admits at least one decycling family, which implies that the set of such lengths is nonempty. Since any nonempty set of natural numbers contains its infimum (`Nat.sInf_mem`), the inversion number is attained by some decycling family.
The set of lengths of decycling families of D is nonempty.
By `tournament_exists_decycling_family`, there exists at least one decycling family Xs for the tournament D. Taking the length of Xs as a witness, the set of lengths of decycling families of D is nonempty (hne).
uses
tournament_exists_decycling_familyobtain ⟨Xs, hXs⟩ := tournament_exists_decycling_family V D h have hne : Set.Nonempty {p | ∃ Xs : List (Set V), Xs.length = p ∧ digraph_is_acyclic (Xs.foldl digraph_invert D)} := ⟨Xs.length, Xs, rfl, hXs⟩
There exists a decycling family of D whose length equals the inversion number of D.
By definition, the inversion number of D is the infimum of the set of lengths of decycling families. Applying `Nat.sInf_mem` to the nonempty set established in the previous step guarantees that this infimum belongs to the set, which means there exists a decycling family achieving this minimal length.
uses
Nat.sInf_memexact Nat.sInf_mem hne
tournament_exists_decycling_family- Every finite tournament admits a decycling family (a list of vertex sets whose sequential inversion yields an acyclic digraph).
Nat.sInf_mem- Any nonempty set of natural numbers contains its infimum (minimum).
- The goal definitionally matches the assertion that the infimum belongs to the set, because `digraph_inversion_number D` is defined directly as `sInf` of the set of lengths of decycling families.
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_exists_family_length_eq_inversion_number (V : Type) [Fintype V] (D : Digraph V) (h : digraph_is_tournament D) : ∃ Xs : List (Set V), Xs.length = digraph_inversion_number D ∧ digraph_is_acyclic (Xs.foldl digraph_invert D) := by obtain ⟨Xs, hXs⟩ := tournament_exists_decycling_family V D h have hne : Set.Nonempty {p | ∃ Xs : List (Set V), Xs.length = p ∧ digraph_is_acyclic (Xs.foldl digraph_invert D)} := ⟨Xs.length, Xs, rfl, hXs⟩ exact Nat.sInf_mem hne