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