AFTD Auto-Formalizing Theoretical Domains

cutCapacity

def

The total capacity of the edges of the network leaving a vertex set S: the sum over u ∈ S and all v of cap({u,v}), with the terms where v ∈ S set to zero.

Statement

def cutCapacity {V : Type} [Fintype V] [DecidableEq V] (net : CapacitatedNetwork V) (S : Finset V) : ℝ
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • 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…
Used by 5
  • linear_code_rate_le_cut_cone_boundIf a linear network code over a field F supports the common rate r, then for any finite family of vertex sets cuts and any nonnegative…
  • code_transmissions_cross_cut_leIn a causal linear network code on net, the number of transmissions whose endpoints are separated by a vertex set S is at most T *…
  • 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…
  • linear_code_supports_rate_cut_boundIf a linear network code over a field F supports the common rate r on net with sessions sess, then for every vertex set S, r times the…
  • one_slot_code_rate_le_cut_ratioA one-slot (T = 1) causal linear code over any field satisfies L * (number of sessions separated by S) ≤ (capacity leaving S) for every…

Lean source view module on GitHub

/-- Total capacity leaving the cut S. -/
def cutCapacity {V : Type} [Fintype V] [DecidableEq V] (net : CapacitatedNetwork V) (S : Finset V) : ℝ := ∑ u ∈ S, ∑ v, if v ∈ S then 0 else net.cap s(u, v)
See it in the graphDiscuss this resultChallenge it