AFTD Auto-Formalizing Theoretical Domains

CapacitatedNetwork

structure

An undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity and non-edges have zero capacity.

Statement

structure CapacitatedNetwork (V : Type) [Fintype V] [DecidableEq V]
Defined in
arXiv:2610.10108, Sec. 2
Verified
19 Oct 2026
Axioms
none listed
Used by 23
  • LinearCodeSupportsRateA common rate r is achievable by deterministic causal linear network coding over a field F on net with sessions sess if there exists a…
  • linear_code_supports_rate_monoIf LinearCodeSupportsRate F net sess r holds on net with sessions sess over field F, then for any r' ≤ r, LinearCodeSupportsRate F net…
  • causal_code_vals_zero_outsideLet a causal linear code on net have transmission values val satisfying the recurrence for a message msg, where msg vanishes on sessions…
  • 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…
  • CausalLinearNetworkCodeA structure CausalLinearNetworkCode parameterized by a finite vertex type V with decidable equality, a finite session type K with…
  • 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…
  • 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…
  • 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…
  • cutCapacityThe 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…
  • flow_supports_rate_zeroOn any capacitated network net with unicast sessions sess, the common rate zero is always supported by fractional multicommodity flow.
  • causal_code_val_uniqueFor a fixed message msg, any two assignments of transmission values satisfying the linear recurrence val m = sum alpha*msg + sum beta*val…
  • 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…
  • causal_linear_network_code_of_transfer_matrixThe construction half of the transfer-matrix criterion, returned as the code itself: explicit transmission endpoints, horizon T, message…
  • 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…
  • one_slot_code_of_scaled_capacitiesA deterministic causal linear code with T transmission slots on a capacitated network can be read as a one-slot (T = 1) code with the same…
  • IsMulticommodityFlowGiven a capacitated network on a finite vertex type V with decidable equality, and unicast sessions indexed by a finite type K with…
  • linear_code_supports_rate_unit_edgeNon-vacuity of LinearCodeSupportsRate: on the two-vertex graph with a single unit-capacity edge, with the single session 0 -> 1, a…
  • 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…
  • linear_code_supports_rate_of_transfer_matrixGiven M transmissions with endpoints snd, rcv on a capacitated network, a time horizon T > 0, a message dimension L > 0,…
  • FlowSupportsRateA common rate r is supported by fractional multicommodity flow on a capacitated network net with unicast sessions sess if there exists a…

Read back from the Lean

A structure CapacitatedNetwork parameterized by a finite type V with decidable equality ([Fintype V] and [DecidableEq V]), consisting of: 1. G: a simple graph with vertex type V (SimpleGraph V); 2. decAdj: a proof that the adjacency relation G.Adj is decidable (DecidableRel G.Adj); 3. cap: a capacity function from unordered pairs of vertices in V to the real numbers (Sym2 V → ℝ); 4. cap_pos: the hypothesis that for every unordered pair e ∈ Sym2 V, if e ∈ G.edgeSet, then 0 < cap e; 5. cap_zero: the hypothesis that for every unordered pair e ∈ Sym2 V, if e ∉ G.edgeSet, then cap e = 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

/-- An undirected network with positive edge capacities on the edges of a simple graph. -/
structure CapacitatedNetwork (V : Type) [Fintype V] [DecidableEq V] where
  G : SimpleGraph V
  decAdj : DecidableRel G.Adj
  cap : Sym2 V → ℝ
  cap_pos : ∀ e ∈ G.edgeSet, 0 < cap e
  cap_zero : ∀ e ∉ G.edgeSet, cap e = 0
See it in the graphDiscuss this resultChallenge it