AFTD Auto-Formalizing Theoretical Domains

SatisfiesC4

def

Real-valued capacities u : E → ℝ and demands d : K → ℝ satisfy condition (C4) on topology (G, H) if for every binary edge-length function ℓ : E → ENNReal with ℓ e = 0 ∨ ℓ e = 1 for all e, the demand-weighted shortest path sum ∑ i, ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i) is at most the capacity-weighted sum ∑ e, ENNReal.ofReal (u e) * ℓ e.

Statement

noncomputable def SatisfiesC4 {V E K : Type*} [Fintype E] [Fintype K]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K)
    (u : E → ℝ) (d : K → ℝ) : Prop
Defined in
arXiv:2611.12330 Section 3, Condition (C4)
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • DirectedMultigraphA directed multigraph parameterized by vertex type V and edge type E, with source and target maps src : E → V and tgt : E → V.
  • directedDistENNThe shortest path distance directedDistENN G ℓ u v from vertex u to vertex v in a directed multigraph G with edge lengths ℓ : E → ENNReal,…
Used by 1
  • BelongsToS4A directed multiflow topology (G, H) belongs to S_4 if for every non-negative capacities u : E → ℝ and demands d : K → ℝ, satisfying…

Read back from the Lean

For finite types E and K, an arbitrary type V, directed multigraphs G on (V, E) and H on (V, K), and real-valued functions u : E → ℝ and d : K → ℝ, SatisfiesC4 G H u d asserts that: For every length function ℓ : E → ENNReal such that for all e : E, ℓ e = 0 or ℓ e = 1, the sum over i : K of ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i) is less than or equal to the sum over e : E of ENNReal.ofReal (u e) * ℓ e.

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

/-- Binary edge-length condition (C4) for directed multiflows. -/
noncomputable def SatisfiesC4 {V E K : Type*} [Fintype E] [Fintype K]
    (G : DirectedMultigraph V E) (H : DirectedMultigraph V K)
    (u : E → ℝ) (d : K → ℝ) : Prop :=
  ∀ ℓ : E → ENNReal, (∀ e, ℓ e = 0 ∨ ℓ e = 1) →
    (∑ i : K, ENNReal.ofReal (d i) * directedDistENN G ℓ (H.src i) (H.tgt i)) ≤
      (∑ e : E, ENNReal.ofReal (u e) * ℓ e)
See it in the graphDiscuss this resultChallenge it