digraph_semisaturation_bounded_of_isolated_edge
Let 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 and digraph_has_isolated_edge G hold. Then the semisaturation function is bounded: there exist C : ℕ and n₀ : ℕ such that for all n ≥ n₀, digraph_ssat n G ≤ C.
Statement
theorem digraph_semisaturation_bounded_of_isolated_edge {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ C : ℕ, ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ C
- Formalizes
- arXiv:2610.18600 Lemma 2.1
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_has_isolated_edgeA digraph G on vertex type V has an isolated edge if there exist vertices u and v such that G has a directed edge from u to v, and every…
- digraph_is_orientedA digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.
- digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
- 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 :…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a directed graph on $V$ with decidable adjacency relation. Assume that:
1. $G$ is oriented (for all $u, v \in V$, if $u \to v$ in $G$, then $v \not\to u$ in $G$, which also precludes self-loops);
2. $G$ has an isolated directed edge: there exist vertices $u, v \in V$ such that $u \to v$ in $G$, and any vertex incident to $u$ or $v$ (in either direction) must be $u$ or $v$ (meaning the connected component of $\{u, v\}$ contains only the edge $u \to v$).
Then there exist natural numbers $C$ and $n_0$ such that for all $n \ge n_0$, the semisaturation number digraph_ssat n G is at most $C$.
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 theorem asserts that the semisaturation number of any finite oriented digraph G containing an isolated edge is eventually bounded by a constant. The proof directly applies digraph_semisaturation_isolated_edge_bound, which provides an explicit threshold n₀ beyond which digraph_ssat n G ≤ 3 * (|E(G)| - 1). Choosing C = 3 * (|E(G)| - 1) and this threshold n₀ witnesses the required existential bound.
For all n at or beyond an explicit threshold n₀, the semisaturation number digraph_ssat n G is bounded by the constant C = 3 * (|E(G)| - 1).
Applying digraph_semisaturation_isolated_edge_bound to the oriented digraph G with an isolated edge yields a threshold n₀ such that digraph_ssat n G ≤ 3 * (|E(G)| - 1) for all n ≥ n₀. Choosing the constant bound C = 3 * (|E(G)| - 1) together with this threshold n₀ satisfies the existential statement.
uses
digraph_semisaturation_isolated_edge_boundobtain ⟨n₀, hn₀⟩ := digraph_semisaturation_isolated_edge_bound G hG he exact ⟨3 * (digraph_edge_count G - 1), n₀, hn₀⟩
digraph_semisaturation_isolated_edge_bound- For any finite oriented digraph G with an isolated edge, there exists an integer threshold n₀ such that for all n ≥ n₀, the semisaturation number digraph_ssat n G is at most 3 * (|E(G)| - 1).
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.
/-- Bounded semisaturation for oriented graphs containing an isolated edge (Lemma 2.1). -/theorem digraph_semisaturation_bounded_of_isolated_edge {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ C : ℕ, ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ C := by obtain ⟨n₀, hn₀⟩ := digraph_semisaturation_isolated_edge_bound G hG he exact ⟨3 * (digraph_edge_count G - 1), n₀, hn₀⟩