AFTD Auto-Formalizing Theoretical Domains

FlowSupportsRate

def

A common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a flow function f satisfying IsMulticommodityFlow net sess r f.

Statement

def FlowSupportsRate {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) (r : ℝ) : Prop
Defined in
arXiv:2610.10108, Sec. 2
Verified
19 Oct 2026
Axioms
none listed
Built on 3
  • IsMulticommodityFlowGiven a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with…
  • CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
  • UnicastSessionsA collection of unicast communication sessions indexed by a type K on an arbitrary vertex type V, consisting of a source map src : K → V,…
Used by 7
  • flow_rate_mul_sep_le_cut_capacityIf a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is…
  • single_slot_advantage_of_multislot_advantageAny multi-slot coding advantage yields a one-slot coding advantage: if on some instance the code rate strictly exceeds every supported…
  • flow_supports_rate_zeroOn any capacitated network net with unicast sessions sess, the common rate zero is always supported by fractional multicommodity flow.
  • flow_rate_lt_of_strict_metric_boundIf a fractional multicommodity flow supports common rate r on net with sessions sess, and d is a nonnegative, symmetric,…
  • flow_supports_rate_scaled_capacitiesFractional multicommodity flow feasibility is homogeneous of degree one in (flow, rate, capacities): for T > 0, a flow of common rate T*r…
  • flow_supports_rate_monoIf a fractional multicommodity flow on net with sessions sess supports common rate r, then for any non-negative rate r' ≤ r, rate r' is…
  • flow_rate_mul_two_le_sum_cap_mul_distIf a fractional multicommodity flow on net supports the common rate r, and d is a symmetric, nonnegative, triangle-satisfying function on…

Read back from the Lean

Given finite types $V$ and $K$ with decidable equality, a capacitated network net on vertex set $V$, a family of unicast sessions sess indexed by $K$, and a real number $r$, FlowSupportsRate net sess r asserts that there exists a multicommodity flow function $f : K \to V \to V \to \mathbb{R}$ satisfying IsMulticommodityFlow net sess r f.

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

/-- Common rate r is supported by fractional multicommodity flow on the capacitated network. -/
def FlowSupportsRate {V : Type} [Fintype V] [DecidableEq V] {K : Type} [Fintype K] [DecidableEq K]
    (net : CapacitatedNetwork V) (sess : UnicastSessions V K) (r : ℝ) : Prop := ∃ f, IsMulticommodityFlow net sess r f
See it in the graphDiscuss this resultChallenge it