digraph_ssat_le_of_semisaturating
If 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 n G ≤ digraph_edge_count H.
Statement
theorem digraph_ssat_le_of_semisaturating {V : Type*} (n : ℕ) (G : Digraph V) (H : Digraph (Fin n)) [d : DecidableRel H.Adj] (hH : digraph_is_semisaturating H G) : digraph_ssat n G ≤ digraph_edge_count H
- Source
- arXiv:2610.18600 Definition 1.2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- digraph_ssatFor 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 :…
- 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.
Read back from the Lean
Given a type V, a natural number n, a directed graph G on V, and a directed graph H on Fin n with decidable adjacency relation d: if H is semisaturating for G (hH : digraph_is_semisaturating H G), then the semisaturation number of G on n vertices, digraph_ssat n G, is less than or equal to the edge count of H, digraph_edge_count H.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof shows that any host digraph H on Fin n that semisaturates G provides an upper bound on digraph_ssat n G. By definition, digraph_ssat n G is the infimum of the edge counts of all such host digraphs. Because H is an explicit witness whose edge count belongs to this set, the infimum is at most the edge count of H.
digraph_ssat n G ≤ digraph_edge_count H
By definition, digraph_ssat n G is the infimum in ℕ of the set of edge counts of all host digraphs on Fin n that semisaturate G. The host digraph H, equipped with its decidability instance d and the semisaturation hypothesis hH, witnesses that digraph_edge_count H is an element of this set. By Nat.sInf_le, the infimum of the set is at most this member.
uses
Nat.sInf_leunfold digraph_ssat exact Nat.sInf_le ⟨H, d, hH, rfl⟩
Nat.sInf_le- If a natural number m belongs to a set of natural numbers s, then the infimum of s is at most m.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Any host digraph semisaturating G gives an upper bound on digraph_ssat. -/theorem digraph_ssat_le_of_semisaturating {V : Type*} (n : ℕ) (G : Digraph V) (H : Digraph (Fin n)) [d : DecidableRel H.Adj] (hH : digraph_is_semisaturating H G) : digraph_ssat n G ≤ digraph_edge_count H := by unfold digraph_ssat exact Nat.sInf_le ⟨H, d, hH, rfl⟩