AFTD Auto-Formalizing Theoretical Domains

tournament_is_universal

def

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
See it in the graphDiscuss this resultChallenge it