tournament_is_universal
A 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 for all vertices u, v of H, T has an arc from f u to f v if and only if H has an arc from u to v.
Statement
def tournament_is_universal (k : ℕ) {V : Type*} (T : Digraph V) : Prop
- Defined in
- arXiv:2610.06891 Section 1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Built on 1
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
Read back from the Lean
Given a natural number k, a type V, and a directed graph T on V, tournament_is_universal k T is the proposition that for every directed graph H on Fin k, if H is a tournament, then there exists an injective function f : Fin k ↪ V such that for all vertices u, v : Fin k, there is an edge from f u to f v in T if and only if there is an edge from u to v in H (i.e., f is an induced subgraph embedding of H into T).
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 T is k-universal if every tournament on Fin k embeds into T. -/ def tournament_is_universal (k : ℕ) {V : Type*} (T : Digraph V) : Prop := ∀ (H : Digraph (Fin k)), digraph_is_tournament H → ∃ f : Fin k ↪ V, ∀ u v, T.Adj (f u) (f v) ↔ H.Adj u v