AFTD Auto-Formalizing Theoretical Domains

BelongsToS4

def

A directed multiflow topology (G, H) belongs to S_4 if for every non-negative capacities u : E → ℝ and demands d : K → ℝ, satisfying condition (C4) implies the existence of a feasible multiflow.

Statement

def BelongsToS4 {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) : Prop
Defined in
arXiv:2611.12330 Definition 1
Verified
13 Nov 2026
Axioms
none listed
Built on 3
  • DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
  • SatisfiesC4Real-valued capacities u : E → ℝ and demands d : K → ℝ satisfy condition (C4) on topology (G, H) if for every binary edge-length function…
  • HasFeasibleMultiflowAn instance (G, H, u, d) has a feasible multiflow if there exists some flow function f : K → E → ℝ satisfying IsFeasibleMultiflow G H u d f.

Read back from the Lean

For finite types $E$ and $K$, an arbitrary type $V$ with decidable equality, a directed multigraph $G$ on $V$ with edges $E$, and a demand multigraph $H$ on $V$ with edges/commodities $K$: BelongsToS4 G H asserts that for all non-negative edge capacity functions $u : E \to \mathbb{R}$ and non-negative demand functions $d : K \to \mathbb{R}$ (i.e., $\forall e, 0 \le u(e)$ and $\forall i, 0 \le d(i)$), if $(G, H, u, d)$ satisfies condition $C_4$ (SatisfiesC4 G H u d), then there exists a feasible multicommodity flow (HasFeasibleMultiflow G H u d). Here: 1. SatisfiesC4 G H u d means: for every edge length function $\ell : E \to [0, \infty]$ taking values only in $\{0, 1\}$ (i.e., $\forall e \in E, \ell(e) = 0 \lor \ell(e) = 1$), $$\sum_{i \in K} \mathrm{ofReal}(d(i)) \cdot \mathrm{dist}_{G, \ell}(H.\mathrm{src}(i), H.\mathrm{tgt}(i)) \le \sum_{e \in E} \mathrm{ofReal}(u(e)) \cdot \ell(e)$$ in $\overline{\mathbb{R}}_{\ge 0}$, where $\mathrm{dist}_{G, \ell}(u, v)$ is the infimum over all directed walks $p$ from $u$ to $v$ in $G$ of the sum of edge lengths along $p$ (which is $\infty$ if no directed walk exists). 2. HasFeasibleMultiflow G H u d means: there exists a flow function $f : K \to E \to \mathbb{R}$ such that: - $f$ is non-negative: $\forall i \in K, \forall e \in E, 0 \le f(i, e)$; - $f$ obeys edge capacities: $\forall e \in E, \sum_{i \in K} f(i, e) \le u(e)$; - $f$ satisfies flow conservation at every vertex: for all $i \in K$ and $v \in V$, $$\sum_{\substack{e \in E \\ G.\mathrm{src}(e) = v}} f(i, e) - \sum_{\substack{e \in E \\ G.\mathrm{tgt}(e) = v}} f(i, e) = (\text{if } H.\mathrm{src}(i) = v \text{ then } d(i) \text{ else } 0) - (\text{if } H.\mathrm{tgt}(i) = v \text{ then } d(i) \text{ else } 0).$$

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

/-- Class S_4 of directed multiflow topologies where condition (C4) implies feasibility. -/
def BelongsToS4 {V E K : Type*} [Fintype E] [Fintype K] [DecidableEq V]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K) : Prop :=
  ∀ (u : E → ℝ) (d : K → ℝ), (∀ e, 0 ≤ u e) → (∀ i, 0 ≤ d i) →
    SatisfiesC4 G H u d → HasFeasibleMultiflow G H u d
See it in the graphDiscuss this resultChallenge it