digraph_is_acyclic
def
A digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. For a tournament this means it is transitive.
Statement
def digraph_is_acyclic {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 1 (acyclic digraph: no directed cycle).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 21
- tournament_exists_decycling_matrixEvery finite tournament has a symmetric decycling matrix over F₂ (so its minimum rank is attained).
- 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_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_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_directed_triangle_not_acyclicThe directed triangle 0 → 1 → 2 → 0 is not acyclic.
- 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.
- 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_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…
- digraph_inversion_number_eq_zero_of_is_acyclicAn acyclic digraph has inversion number 0.
- 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_min_rank_le_inversion_numberFor a finite tournament D: tmr(D) ≤ inv(D).
- digraph_is_acyclic_of_rankA digraph with a numbering of the vertices that increases along every arc is acyclic.
- tournament_min_rank_eq_zero_of_is_acyclicAn acyclic digraph has tournament minimum rank 0 (the zero matrix decycles it).
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- 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_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.
Lean source view module on GitHub
/-- A digraph is acyclic when it has no directed cycle: no vertex reaches itself by a nonempty directed walk. -/ def digraph_is_acyclic {V : Type*} (D : Digraph V) : Prop := ∀ x, ¬ Relation.TransGen D.Adj x x