digraph_is_semicomplete_multipartite
def
A digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e., its vertex set is partitioned into independent sets with all cross-pairs having at least one directed edge).
Statement
def digraph_is_semicomplete_multipartite {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.36895 Sec. 5
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 5
- digraph_semicomplete_multipartite_nonadj_transIn a semicomplete multipartite digraph D, non-adjacency in both directions is transitive among pairwise distinct vertices.
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linkedLet D be a 4-strong semicomplete multipartite digraph on a finite type V. If s₁, t₁, s₂, t₂ are pairwise distinct vertices of D such that…
- digraph_exists_four_strong_semicomplete_multipartite_not_unilaterally_two_linked_eightThere exists a finite type V with exactly 8 elements and a digraph D on V such that D is 4-strong, semicomplete multipartite, and not…
- digraph_bot_is_semicomplete_multipartiteThe empty digraph on any vertex type is semicomplete multipartite.
- digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked_rightLet D be a 4-strong semicomplete multipartite digraph. If s₁, t₁, s₂, t₂ are pairwise distinct vertices such that there is an arc between…
Read back from the Lean
Given a type V and a directed graph D : Digraph V, digraph_is_semicomplete_multipartite D asserts that:
1. For every vertex v : V, there is no directed loop from v to itself (¬ D.Adj v v).
2. The simple graph associated to D by toSimpleGraphInclusive is complete multipartite (D.toSimpleGraphInclusive.IsCompleteMultipartite).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A digraph is semicomplete multipartite if loopless and its underlying graph is complete multipartite. -/ def digraph_is_semicomplete_multipartite {V : Type*} (D : Digraph V) : Prop := (∀ v : V, ¬ D.Adj v v) ∧ D.toSimpleGraphInclusive.IsCompleteMultipartite