cutSeparation_eq_sum
Express cutSeparation as a sum of real indicator functions over sessions k in K.
Statement
theorem cutSeparation_eq_sum {V : Type} [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (S : Finset V) : (cutSeparation sess S : ℝ) = ∑ k : K, if (sess.src k ∈ S) ≠ (sess.tgt k ∈ S) then (1 : ℝ) else 0
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cutSeparationThe 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…
- 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 1
- 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…
The proof, explained
The proof unfolds the definition of `cutSeparation` as the cardinality of the subset of sessions separated by the cut S, expresses this cardinality as a sum of 1s, and converts the sum over the filtered set to a sum of indicator functions over all sessions in K. Finally, it pushes the coercion from the natural numbers to the real numbers into the sum.
The cut separation is expressed as the natural-number sum over all sessions of an indicator function that is 1 when the session endpoints are separated by S and 0 otherwise.
By definition, `cutSeparation sess S` is the cardinality of the subset of sessions whose source and target do not both lie on the same side of S. We rewrite this cardinality as a sum of 1s over the subset using `Finset.card_eq_sum_ones`, and then rewrite the sum over the filtered subset as a sum over all of K using `Finset.sum_filter`, inserting a conditional that yields 1 if the session is separated and 0 otherwise.
uses
Finset.card_eq_sum_ones,Finset.sum_filtersimp only [cutSeparation] rw [Finset.card_eq_sum_ones] rw [Finset.sum_filter]
The equality holds for the sum of real indicators. automation
The simplification tactic distributes the natural-to-real coercion through the finite sum and the if-then-else branch, turning the integer 1 and 0 into the real numbers 1 and 0.
simp
Finset.card_eq_sum_ones- The cardinality of a finite set is the sum of 1 over all its elements.
Finset.sum_filter- The sum of a function over a filtered subset equals the sum over the whole set with an indicator function that is 0 outside the subset.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Express cutSeparation as a sum of real indicator functions over sessions k in K. -/theorem cutSeparation_eq_sum {V : Type} [DecidableEq V] {K : Type} [Fintype K] (sess : UnicastSessions V K) (S : Finset V) : (cutSeparation sess S : ℝ) = ∑ k : K, if (sess.src k ∈ S) ≠ (sess.tgt k ∈ S) then (1 : ℝ) else 0 := by simp only [cutSeparation] rw [Finset.card_eq_sum_ones] rw [Finset.sum_filter] simp