digraph_ssat
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
- digraph_ssat_le_of_semisaturatingIf H : Digraph (Fin n) is a host digraph on Fin n with DecidableRel H.Adj such that digraph_is_semisaturating H G holds, then digraph_ssat…
- digraph_semisaturation_isolated_edge_boundIf G : Digraph V is a finite oriented digraph with DecidableEq V and DecidableRel G.Adj satisfying digraph_is_oriented G and…
- digraph_semisaturation_bounded_of_isolated_edgeLet G : Digraph V be a finite oriented digraph on vertex type V with DecidableEq V and DecidableRel G.Adj such that digraph_is_oriented G…
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 }