AFTD Auto-Formalizing Theoretical Domains

digraph_ssat

def

For a natural number n and a digraph G : Digraph V on vertex type V, digraph_ssat n G is the infimum of the set of all natural numbers k : ℕ for which there exists a digraph H : Digraph (Fin n) and an instance d : DecidableRel H.Adj such that digraph_is_semisaturating H G holds and digraph_edge_count H = k.

Statement

noncomputable def digraph_ssat {V : Type*} (n : ℕ) (G : Digraph V) : ℕ
Defined in
arXiv:2610.18600 Definition 1.2
Verified
23 Oct 2026
Axioms
none listed
Built on 2
  • digraph_is_semisaturatingA host digraph H : Digraph W on vertex type W semisaturates a digraph G : Digraph V on vertex type V (digraph_is_semisaturating H G) if…
  • digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
Used by 3

Read back from the Lean

digraph_ssat {V : Type*} (n : ℕ) (G : Digraph V) : ℕ defines the semi-saturation number of a directed graph G on n vertices as the infimum (sInf in ℕ, which defaults to 0 if the set is empty) of the set of natural numbers k for which there exists a directed graph H on the vertex set Fin n (with decidable adjacency) such that: 1. H is semisaturating for G (digraph_is_semisaturating H G), and 2. the directed edge count of H (digraph_edge_count H) equals k.

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

/-- The semisaturation function ssat(n, G) is the minimum number of edges in an n-vertex host graph semisaturating G. -/
noncomputable def digraph_ssat {V : Type*} (n : ℕ) (G : Digraph V) : ℕ := sInf { k : ℕ | ∃ H : Digraph (Fin n), ∃ _ : DecidableRel H.Adj, digraph_is_semisaturating H G ∧ digraph_edge_count H = k }
See it in the graphDiscuss this resultChallenge it