AFTD Auto-Formalizing Theoretical Domains

tournament_min_rank_le_dijoin

theoremverifiedformalization

For finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a decycling matrix on an induced subtournament decycles it and has no larger rank.

Statement

theorem tournament_min_rank_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 (tournament_min_rank D₁) (tournament_min_rank D₂) ≤
      tournament_min_rank (digraph_dijoin D₁ D₂)
Formalizes
arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Observation 2.3 (stated here for the two sides of a dijoin; the average bound follows from the max).
Verified
13 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • tournament_min_rankThe tournament minimum rank tmr(D): the least F₂-rank of a symmetric matrix M over F₂ that decycles D, i.e. such that reversing every 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₂.
  • tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
  • digraph_dijoin_is_tournamentThe dijoin of two tournaments is a tournament.
  • 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_flip_by_matrixGiven a digraph D and a (symmetric) matrix M over F₂ indexed by its vertices, the digraph obtained by reversing every arc uv with M_uv = 1…
  • digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.

The proof, explained

To show that tournament_min_rank(D₁ → D₂) ≥ max(tournament_min_rank(D₁), tournament_min_rank(D₂)), we first select an optimal symmetric decycling matrix M for the dijoin D₁ → D₂. We then establish that any induced subtournament D inherits a decycling matrix by restricting M to the corresponding principal submatrix: any directed cycle in the flipped induced subgraph would push forward to a directed cycle in the flipped dijoin, which is impossible since M decycled the dijoin. Since the rank of a principal submatrix is at most that of the full matrix, tournament_min_rank(D) is bounded by that of the dijoin; applying this to the induced subtournaments D₁ and D₂ yields the result.

  1. There exists an optimal symmetric decycling matrix M for the dijoin D₁ → D₂, whose rank equals tournament_min_rank(D₁ → D₂).

    Because the dijoin of two tournaments is a tournament (digraph_dijoin_is_tournament), it admits a symmetric decycling matrix M₀ by tournament_exists_decycling_matrix. Thus the set of ranks of symmetric decycling matrices for the dijoin is non-empty (hne). By Nat.sInf_mem, this non-empty set of natural numbers contains its infimum, providing an optimal symmetric decycling matrix M with rank equal to tournament_min_rank(D₁ → D₂).

    lines 6–11

    uses tournament_exists_decycling_matrix, digraph_dijoin_is_tournament, Nat.sInf_mem

      obtain ⟨M0, hM0s, hM0a⟩ := tournament_exists_decycling_matrix (V ⊕ W) _
        (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂)
      have hne : Set.Nonempty {r | ∃ M : Matrix (V ⊕ W) (V ⊕ W) (ZMod 2), M.IsSymm ∧
          digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M) ∧ M.rank = r} :=
        ⟨_, M0, hM0s, hM0a, rfl⟩
      obtain ⟨M, hMs, hMa, hMr⟩ := Nat.sInf_mem hne
  2. For any induced subgraph D on vertex set U under an embedding f : U → V ⊕ W, edges in D flipped by the principal submatrix M[f, f] map to edges in D₁ → D₂ flipped by M.

    We begin proving the general lemma lower for an arbitrary induced subgraph D. Unfolding the definition of edge-flipping by a matrix, an edge between x and y in D flipped by M[f, f] corresponds to the matrix entry (M[f, f])_{x, y} and adjacency in D. By Matrix.submatrix_apply, (M[f, f])_{x, y} = M_{f(x), f(y)}, and by the induced subgraph hypothesis hD, adjacency in D matches adjacency in the dijoin. Thus the edge condition in the flipped subgraph matches the edge condition between f(x) and f(y) in the flipped dijoin.

    lines 12–20

    uses Matrix.submatrix_apply

      have lower : ∀ (U : Type) [Fintype U] (f : U → V ⊕ W) (D : Digraph U),
          (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) →
          tournament_min_rank D ≤ tournament_min_rank (digraph_dijoin D₁ D₂) := by
        intro U _ f D hD
        have step : ∀ x y, (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y →
            (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by
          intro x y hxy
          simp only [digraph_flip_by_matrix, Matrix.submatrix_apply, hD] at hxy ⊢
          exact hxy
  3. The graph D flipped by the principal submatrix M[f, f] is acyclic.

    Suppose for contradiction that D flipped by M[f, f] contains a directed cycle from a vertex a to itself. By induction on path length, the previous edge-mapping step shows that any directed path in the flipped subgraph maps to a directed path in the flipped dijoin. Thus f(a) would have a directed cycle to itself in the dijoin flipped by M, contradicting the fact that M decycles the dijoin (hMa).

    lines 21–30

        have hac : digraph_is_acyclic (digraph_flip_by_matrix D (M.submatrix f f)) := by
          intro a ha
          apply hMa (f a)
          have key : ∀ x y, Relation.TransGen (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y →
              Relation.TransGen (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by
            intro x y hxy
            induction hxy with
            | single h => exact .single (step _ _ h)
            | tail _ h ih => exact .tail ih (step _ _ h)
          exact key a a ha
  4. Any induced subgraph D of the dijoin satisfies tournament_min_rank(D) ≤ tournament_min_rank(D₁ → D₂).

    Because M is symmetric, its principal submatrix M[f, f] is symmetric, and by the previous step it decycles D. Thus the rank of M[f, f] belongs to the set of decycling ranks for D, giving tournament_min_rank(D) ≤ rank(M[f, f]) by Nat.sInf_le. Furthermore, the rank of a submatrix cannot exceed the rank of the ambient matrix (Matrix.rank_submatrix_le), which equals tournament_min_rank(D₁ → D₂).

    lines 31–34

    uses Nat.sInf_le, Matrix.rank_submatrix_le

        calc tournament_min_rank D ≤ (M.submatrix f f).rank :=
              Nat.sInf_le ⟨M.submatrix f f, hMs.submatrix f, hac, rfl⟩
          _ ≤ M.rank := Matrix.rank_submatrix_le _ _ _
          _ = _ := hMr
  5. max(tournament_min_rank(D₁), tournament_min_rank(D₂)) ≤ tournament_min_rank(D₁ → D₂).

    By max_le, it suffices to prove the bound for D₁ and D₂ separately. Since D₁ and D₂ are the canonically induced subgraphs of the dijoin on the left and right summands via Sum.inl and Sum.inr (both equivalences hold reflexively by Iff.rfl), applying the induced subgraph lemma lower to each case completes the proof.

    lines 35–37

    uses max_le, Sum.inl, Sum.inr, Iff.rfl

      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)
tournament_exists_decycling_matrix
Every finite tournament admits a symmetric decycling matrix over ℤ/2ℤ whose edge-flip yields an acyclic digraph.
digraph_dijoin_is_tournament
The directed join (dijoin) of two tournaments is itself a tournament.
Nat.sInf_mem
Any non-empty set of natural numbers contains its infimum (minimum).
Matrix.submatrix_apply
The entry of a submatrix at indices (i, j) is the entry of the ambient matrix at (r(i), c(j)).
Nat.sInf_le
Any member of a set of natural numbers is greater than or equal to the infimum of the set.
Matrix.rank_submatrix_le
The rank of any submatrix is at most the rank of the original matrix.
max_le
If a ≤ c and b ≤ c, then max(a, b) ≤ c.
Sum.inl
The canonical inclusion of the first component into a disjoint sum type V ⊕ W.
Sum.inr
The canonical inclusion of the second component into a disjoint sum type V ⊕ W.
Iff.rfl
Reflexivity of logical equivalence: P ↔ P for any proposition P.

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 tournament_min_rank_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 (tournament_min_rank D₁) (tournament_min_rank D₂) ≤      tournament_min_rank (digraph_dijoin D₁ D₂) := by  obtain ⟨M0, hM0s, hM0a⟩ := tournament_exists_decycling_matrix (V ⊕ W) _    (digraph_dijoin_is_tournament D₁ D₂ h₁ h₂)  have hne : Set.Nonempty {r | ∃ M : Matrix (V ⊕ W) (V ⊕ W) (ZMod 2), M.IsSymm ∧      digraph_is_acyclic (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M) ∧ M.rank = r} :=    ⟨_, M0, hM0s, hM0a, rfl⟩  obtain ⟨M, hMs, hMa, hMr⟩ := Nat.sInf_mem hne  have lower : ∀ (U : Type) [Fintype U] (f : U → V ⊕ W) (D : Digraph U),      (∀ a b, (digraph_dijoin D₁ D₂).Adj (f a) (f b) ↔ D.Adj a b) →      tournament_min_rank D ≤ tournament_min_rank (digraph_dijoin D₁ D₂) := by    intro U _ f D hD    have step : ∀ x y, (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y →        (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by      intro x y hxy      simp only [digraph_flip_by_matrix, Matrix.submatrix_apply, hD] at hxy ⊢      exact hxy    have hac : digraph_is_acyclic (digraph_flip_by_matrix D (M.submatrix f f)) := by      intro a ha      apply hMa (f a)      have key : ∀ x y, Relation.TransGen (digraph_flip_by_matrix D (M.submatrix f f)).Adj x y →          Relation.TransGen (digraph_flip_by_matrix (digraph_dijoin D₁ D₂) M).Adj (f x) (f y) := by        intro x y hxy        induction hxy with        | single h => exact .single (step _ _ h)        | tail _ h ih => exact .tail ih (step _ _ h)      exact key a a ha    calc tournament_min_rank D ≤ (M.submatrix f f).rank :=          Nat.sInf_le ⟨M.submatrix f f, hMs.submatrix f, hac, rfl⟩      _ ≤ M.rank := Matrix.rank_submatrix_le _ _ _      _ = _ := hMr  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)
See it in the graphDiscuss this resultChallenge it