digraph_is_tournament
def
A digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Statement
def digraph_is_tournament {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.13798 (On the failure of additivity of inversion numbers for dijoins), Sec. 2.1 (tournaments).
- Verified
- 13 Oct 2026
- Axioms
- none listed
- Used by 51
- tournament_inversion_number_reverseFor a finite tournament D: inv(D̄) = inv(D), where D̄ is D with every arc reversed.
- 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.
- tournament_strong_king_iff_in_neighbor_out_degree_leIn any finite tournament T, a vertex v is a strong king if and only if every in-neighbor u of v (that is, every vertex u with an arc from…
- regular_tournament_five_nearly_doubly_regularThe case k = 1 of the conjecture, in a stronger form: every regular tournament of order 5 is nearly doubly regular (any two distinct…
- tournament_not_king_of_coveredIf a vertex w covers another vertex v in a tournament T (that is, w -> v and w -> x for every out-neighbor x of v), then v is not a king…
- tournament_max_out_degree_is_strong_kingIn any finite tournament T, every vertex v of maximum out-degree is a strong king.
- tournament_reverse_arc_through_root_endpoint_eqIn a tournament T with arc u → v, the number of arborescences rooted at v using u → v equals the number of arborescences of reverse(T, u,…
- 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.
- digraph_four_strong_tournament_unilaterally_two_linkedLet D be a digraph on a finite type V. If D is a tournament and D is 4-strong, then D is unilaterally 2-linked.
- tournament_reverse_arc_laplacian_diffReversing an arc u → v of a tournament updates the out-degree Laplacian by an explicit rank-one matrix (e_u + e_v)(e_v - e_u)^T.
- tournament_exists_covering_realizationLet d be a realizable degree vector of an n-vertex tournament, and let v, w be vertices satisfying d v < d w. Then there exists a…
- 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_universal_kings_iff_max_outdegreeFor every realizable degree vector d of an n-vertex tournament and every vertex v, v is a king in every tournament realizing d if and only…
- tournament_is_universalA directed graph T on vertex type V is k-universal if for every tournament H on Fin k, there exists an embedding f : Fin k ↪ V such that…
- digraph_arborescence_count_reverse_arc_add_throughReversing a single arc u → v of a tournament satisfies tau(T) + through(T', v → u) = tau(T') + through(T, u → v), so the gain in the…
- tournament_reverse_arc_through_lt_iff_arborescence_ltIn a tournament T with an arc u → v, the total through-count strictly increases upon reversing u → v if and only if the total number of…
- 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_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_reverse_arc_is_tournamentIf T is a tournament with an arc u → v, reversing that arc gives another tournament.
- 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_near_regular_card_degreesIn any near-regular tournament on 2m vertices with m ≥ 1, exactly m vertices have out-degree m - 1 and exactly m vertices have out-degree m.
- 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_directed_cut_eq_of_outdegrees_eqLet T₁ and T₂ be tournaments on vertex set Fin n such that every vertex v has the same outdegree in T₁ and T₂. Then for every subset S ⊆…
- exists_near_regular_tournament_fourThere exists a near-regular tournament on 4 vertices.
- tournament_four_not_near_regular_exists_improvingThe m = 2 case of the target, settled by finite computation: a non-near-regular tournament on 4 vertices has at most 9 arborescences while…
- 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).
- tournament_exists_covering_realization_of_realizesLet d be a degree vector on Fin n realized by a tournament T, and let v, w be vertices in Fin n satisfying d v < d w. Then there exists a…
- tournament_two_path_diff_eq_out_degree_diffIn any finite tournament T, if there is an arc from u to v, then the difference between the number of directed two-paths from v to u and…
- tournament_realizesA tournament T on Fin n realizes degree vector d if T is a tournament and the outdegree of every vertex i equals d i.
- 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.
- digraph_invert_is_tournamentInverting a vertex set of a tournament gives a tournament.
- 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…
- exists_not_near_regular_tournament_fourThere exists a tournament on 4 vertices that is not near-regular.
- tournament_four_arborescence_maximizer_is_near_regularEvery tournament on 4 vertices maximizing the total number of spanning arborescences among all tournaments on 4 vertices is near-regular.
- tournament_of_symm_matrix_is_tournamentT(G) is a tournament for every matrix G over F₂ (only the entries above the diagonal are read).
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- tournament_dijoin_reverse_inversion_number_le_add_twoFor finite tournaments D₁ and D₂, inv(D₁ → D₂) ≤ inv(D̄₁ → D̄₂) + 2.
- digraph_arborescence_count_at_reverse_arc_add_throughFor a tournament with an arc u → v and any root r, the number of arborescences towards r grows by exactly (through-count of v → u after…
- tournament_not_near_regular_exists_arc_degree_gapIn a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least…
- 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_cut_count_self_eq_choose_twoIn any tournament T on vertex set Fin n and for any subset S of vertices, the number of directed edges with both endpoints in S equals…
- tournament_degree_vector_realizableA degree vector d on Fin n is realizable if there exists a tournament T on Fin n whose outdegrees are given by 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.
- tournament_cut_count_eq_subIn any tournament T on vertex set Fin n and for any subset S of vertices, the directed cut size from S to its complement Sᶜ equals the sum…
- tournament_sum_out_countIn a tournament T on Fin n, the out-degrees sum to the number of unordered pairs: ∑_i d_i = n(n-1)/2.
- digraph_reverse_is_tournamentThe reverse of a tournament is a tournament.
- tournament_is_king_of_max_outdegreeIn every tournament on n vertices, every vertex of maximum outdegree is a king: every other vertex is reachable from it by a directed path…
- 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 tournament: no loops, and between two distinct vertices exactly one arc. -/ def digraph_is_tournament {V : Type*} (D : Digraph V) : Prop := (∀ x, ¬ D.Adj x x) ∧ ∀ x y, x ≠ y → (D.Adj x y ↔ ¬ D.Adj y x)