AFTD Auto-Formalizing Theoretical Domains

cutSeparation

def

The number of sessions (out of the unicast session set sess) with exactly one endpoint in the vertex set S, i.e. the number of sessions separated by the cut S.

Statement

def cutSeparation {V : Type} [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (S : Finset V) : ℕ
Source
step towards undirected_binary_linear_unicast_advantage
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • 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 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…
  • cutSeparation_eq_sumExpress cutSeparation as a sum of real indicator functions over sessions k in K.
  • 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

/-- Number of sessions crossing the cut S. -/
def cutSeparation {V : Type} [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (S : Finset V) : ℕ := (Finset.univ.filter (fun k => (sess.src k ∈ S) ≠ (sess.tgt k ∈ S))).card
See it in the graphDiscuss this resultChallenge it