digraph_dijoin
def
The dijoin D₁ → D₂: disjoint copies of D₁ and D₂ together with every arc from a vertex of D₁ to a vertex of D₂.
Statement
def digraph_dijoin {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) : Digraph (V ⊕ W)
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 (definition of the dijoin).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 16
- digraph_dijoin_is_tournamentThe dijoin of two tournaments is a tournament.
- digraph_dijoin_reverse_eq_invertsThe dijoin D̄₁ → D̄₂ equals D₁ → D₂ after inverting the two vertex sets Set.range Sum.inl and Set.range Sum.inr.
- 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_reverse_inversion_number_eq_of_is_acyclic_leftWhen D₁ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- 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₂.
- 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₁).
- 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_dijoin_reverse_inversion_number_eq_of_is_acyclic_rightWhen D₂ is acyclic, the inversion numbers of D₁ → D₂ and D̄₁ → D̄₂ are equal.
- 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_dijoinFor finite tournaments D₁, D₂: tmr(D₁ → D₂) ≥ max(tmr(D₁), tmr(D₂)) (hence ≥ (tmr(D₁) + tmr(D₂))/2), because the principal submatrix of a…
- 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.
- 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…
- tournament_dijoin_reverse_inversion_number_le_add_twoFor finite tournaments D₁ and D₂, inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) + 2.
- tournament_min_rank_dijoin_le_of_symm_invLet B be an invertible symmetric n × n matrix over F₂, L the lower triangular all-ones matrix, and A = L B⁻¹ Lᵀ. Then the tournaments 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…
- 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.
Lean source view module on GitHub
/-- The dijoin `D₁ → D₂`: disjoint copies of `D₁` and `D₂` with every arc from a vertex of `D₁` to a vertex of `D₂`. -/ def digraph_dijoin {V W : Type*} (D₁ : Digraph V) (D₂ : Digraph W) : Digraph (V ⊕ W) where Adj | .inl a, .inl b => D₁.Adj a b | .inl _, .inr _ => True | .inr _, .inl _ => False | .inr a, .inr b => D₂.Adj a b