AFTD Auto-Formalizing Theoretical Domains

digraph_is_semisaturating

def

A 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_is_oriented H holds, and for any two distinct vertices x y : W with ¬ H.Adj x y and ¬ H.Adj y x, there exists an injective function f : V → W such that for all a b : V, G.Adj a b implies H.Adj (f a) (f b) ∨ (f a = x ∧ f b = y), and there exist a b : V with G.Adj a b and f a = x ∧ f b = y.

Statement

def digraph_is_semisaturating {V W : Type*} (H : Digraph W) (G : Digraph V) : Prop
Defined in
arXiv:2610.18600 Definition 1.2
Verified
23 Oct 2026
Axioms
none listed
Built on 1
  • 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.
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_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_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…

Read back from the Lean

Given types V and W, a directed graph H on W, and a directed graph G on V, digraph_is_semisaturating H G asserts that both of the following hold: 1. H is an oriented graph: for all vertices u, v : W, if there is an edge H.Adj u v, then there is no edge H.Adj v u. 2. For all distinct vertices x, y : W such that there is no edge between them in either direction (i.e., ¬ H.Adj x y and ¬ H.Adj y x), there exists an injective function f : V → W such that: - For all vertices a, b : V, if G.Adj a b, then either H.Adj (f a) (f b) holds or (f a = x ∧ f b = y) (that is, every directed edge of G is mapped to an edge of H or to the directed pair (x, y)). - There exist vertices a, b : V such that G.Adj a b and f a = x and f b = y (that is, the directed edge (x, y) is actively used by the embedding of G).

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 host digraph H semisaturates G if H is oriented and adding any non-edge creates a copy of G using that edge. -/
def digraph_is_semisaturating {V W : Type*} (H : Digraph W) (G : Digraph V) : Prop := digraph_is_oriented H ∧ ∀ x y : W, x ≠ y → ¬ H.Adj x y → ¬ H.Adj y x → ∃ f : V → W, Function.Injective f ∧ (∀ a b, G.Adj a b → (H.Adj (f a) (f b) ∨ (f a = x ∧ f b = y))) ∧ (∃ a b, G.Adj a b ∧ f a = x ∧ f b = y)
See it in the graphDiscuss this resultChallenge it