BelongsToS4
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