op869_orient_pairs_half
Given finitely many marked pairs of distinct indices, there is a set of indices whose boundary crosses at least half the pairs, counting repetitions separately.
Statement
theorem op869_orient_pairs_half {γ : Type} [DecidableEq γ] (m : ℕ) (C : Finset γ) (u v : γ → Fin m) (huv : ∀ c ∈ C, u c ≠ v c) : ∃ s : Finset (Fin m), C.card ≤ 2 * (C.filter (fun c => (u c ∈ s ∧ v c ∉ s) ∨ (u c ∉ s ∧ v c ∈ s))).card
- Source
- arXiv:2610.41516, Lemma 2.4: the orientation step used to produce two-sided colors.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
The proof, explained
The theorem is proved by the first moment method via double counting. For any fixed pair of distinct endpoints, toggling the membership of one endpoint is an involution on the family of all vertex subsets that swaps whether the pair is crossed, meaning every pair is crossed by exactly half of all subsets. Double counting the pairs (subset, crossed pair) shows that the average number of crossed pairs over all subsets is |C| / 2. Therefore, a subset that maximizes the number of crossed pairs must cross at least |C| / 2 pairs.
Let F be the family of all subsets of Fin m; there exists a subset s ∈ F that maximizes the number of crossed pairs w(s).
We define F to be the set of all subsets of Fin m (line 8). A subset s crosses a pair c ∈ C if exactly one of its endpoints u(c), v(c) belongs to s (lines 9–10). For each subset s, w(s) counts how many pairs in C are crossed by s (line 11). Since F contains the empty set, it is nonempty (line 12), and by Finset.exists_max_image there is some subset s ∈ F achieving the maximal crossing count (line 13).
uses
Finset.exists_max_imageclassical let F : Finset (Finset (Fin m)) := Finset.univ let cross (s : Finset (Fin m)) (c : γ) : Prop := (u c ∈ s ∧ v c ∉ s) ∨ (u c ∉ s ∧ v c ∈ s) let w (s : Finset (Fin m)) : ℕ := (C.filter (cross s)).card have hF : F.Nonempty := ⟨∅, by simp [F]⟩ obtain ⟨s, hs, hmax⟩ := Finset.exists_max_image F w hF
For every pair c ∈ C, exactly half of all subsets in F cross c; that is, 2 * |{s ∈ F | cross s c}| = |F|.
Fix c ∈ C with distinct endpoints u(c) ≠ v(c), so v(c) ≠ u(c) by Ne.symm (line 18). Flipping the membership of u(c) via symmetric difference s ↦ s ∆ {u(c)} swaps whether c is crossed: s ∆ {u(c)} crosses c if and only if s does not (hflip, lines 16–20, using Finset.mem_symmDiff and Finset.mem_singleton). Because this flip is an involution on F, it provides a bijection between subsets crossing c and subsets not crossing c (hequal, lines 21–32, using Finset.card_bij' and Finset.mem_filter). Since crossing and non-crossing subsets partition F (Finset.card_filter_add_card_filter_not, line 33), their cardinalities are equal and sum to |F|, yielding the claim via linear integer arithmetic (omega, line 34).
uses
Ne.symm,Finset.mem_symmDiff,Finset.mem_singleton,Finset.card_bij',Finset.mem_filter,Finset.card_filter_add_card_filter_nothave hhalf (c : γ) (hc : c ∈ C) : 2 * (F.filter (fun s => cross s c)).card = F.card := by have hflip (s : Finset (Fin m)) : cross (s ∆ {u c}) c ↔ ¬ cross s c := by simp only [cross, Finset.mem_symmDiff, Finset.mem_singleton] have hne : v c ≠ u c := Ne.symm (huv c hc) simp only [hne, not_false_eq_true, and_true, and_false, or_false, or_true, not_true_eq_false] tauto have hequal : (F.filter (fun s => cross s c)).card = (F.filter (fun s => ¬ cross s c)).card := by apply Finset.card_bij' (fun s _ => s ∆ {u c}) (fun s _ => s ∆ {u c}) · intro s hs simp · intro s hs simp · intro s hs simp only [Finset.mem_filter] at hs ⊢ exact ⟨by simp [F], by simpa [hflip] using hs.2⟩ · intro s hs simp only [Finset.mem_filter] at hs ⊢ exact ⟨by simp [F], by simpa [hflip] using hs.2⟩ have htotal := Finset.card_filter_add_card_filter_not (s := F) (fun s => cross s c) omega
The total number of crossings over all subsets satisfies |F| * |C| = 2 * ∑ s ∈ F, w(s).
We rewrite |F| * |C| as the sum ∑ c ∈ C, |F| using mul_comm (line 37). By the previous step, each term |F| equals 2 * |{s ∈ F | cross s c}|, so their sums are equal by Finset.sum_congr (lines 38–41). Writing each subset cardinality as a sum of 0-1 indicators via Finset.sum_boole (lines 43–48) and distributing multiplication over the sum via Finset.mul_sum (line 49), swapping the order of summation with Finset.sum_comm (line 50) rewrites this as 2 * ∑ s ∈ F, w(s).
uses
mul_comm,Finset.sum_congr,Finset.sum_boole,Finset.mul_sum,Finset.sum_commhave hsum : F.card * C.card = 2 * ∑ s ∈ F, w s := by calc F.card * C.card = ∑ c ∈ C, F.card := by simp [mul_comm] _ = ∑ c ∈ C, 2 * (F.filter (fun s => cross s c)).card := by apply Finset.sum_congr rfl intro c hc exact (hhalf c hc).symm _ = 2 * ∑ s ∈ F, w s := by have hcount (c : γ) : (F.filter (fun s => cross s c)).card = ∑ s ∈ F, if cross s c then 1 else 0 := by exact (Finset.sum_boole (R := ℕ) (fun s => cross s c) F).symm have hcount' (s : Finset (Fin m)) : w s = ∑ c ∈ C, if cross s c then 1 else 0 := by exact (Finset.sum_boole (R := ℕ) (fun c => cross s c) C).symm simp_rw [hcount, hcount', Finset.mul_sum] rw [Finset.sum_comm]
The maximal subset s satisfies |C| ≤ 2 * w(s), meaning its boundary crosses at least half the pairs in C.
We choose the maximizer s as the witness (line 51). Because s maximizes w on F, the sum ∑ t ∈ F, w(t) is bounded by |F| * w(s) via Finset.sum_le_card_nsmul (lines 52–53). Since F is nonempty, |F| > 0 by Finset.card_pos.mpr (line 54). Combining this bound with the identity |F| * |C| = 2 * ∑ t ∈ F, w(t), nonlinear arithmetic (nlinarith, line 55) divides out the positive factor |F| to give |C| ≤ 2 * w(s), which completes the proof after unfolding w and cross (line 56).
uses
Finset.sum_le_card_nsmul,Finset.card_pos.mprrefine ⟨s, ?_⟩ have hbound : (∑ t ∈ F, w t) ≤ F.card * w s := by simpa using Finset.sum_le_card_nsmul F w (w s) (fun t ht => hmax t ht) have hpos : 0 < F.card := Finset.card_pos.mpr hF have : C.card ≤ 2 * w s := by nlinarith simpa [w, cross] using this
Finset.exists_max_image- A nonempty finite set has an element that maximizes any given linearly ordered function on it.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_symmDiff- An element belongs to the symmetric difference s ∆ t if and only if it belongs to s or t but not both.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
Finset.card_bij'- Two finite sets have equal cardinality if there are maps between them that are mutually inverse on the sets.
Finset.mem_filter- An element belongs to {x ∈ s | p x} if and only if x ∈ s and p x holds.
Finset.card_filter_add_card_filter_not- For any predicate p on a finite set s, the count of elements satisfying p plus the count of elements satisfying ¬p equals |s|.
mul_comm- Multiplication is commutative: a * b = b * a.
Finset.sum_congr- Two sums over equal finite sets are equal if their summands agree at every element.
Finset.sum_boole- The sum of the indicator (0-1) function of a predicate over a finite set equals the cardinality of the subset satisfying that predicate.
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_comm- The order of summation in a finite double sum can be swapped.
Finset.sum_le_card_nsmul- A finite sum ∑ x ∈ s, f x is bounded above by |s| * M whenever f x ≤ M for all x ∈ s.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if and only if it is nonempty.
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.
open scoped symmDifftheorem op869_orient_pairs_half {γ : Type} [DecidableEq γ] (m : ℕ) (C : Finset γ) (u v : γ → Fin m) (huv : ∀ c ∈ C, u c ≠ v c) : ∃ s : Finset (Fin m), C.card ≤ 2 * (C.filter (fun c => (u c ∈ s ∧ v c ∉ s) ∨ (u c ∉ s ∧ v c ∈ s))).card := by classical let F : Finset (Finset (Fin m)) := Finset.univ let cross (s : Finset (Fin m)) (c : γ) : Prop := (u c ∈ s ∧ v c ∉ s) ∨ (u c ∉ s ∧ v c ∈ s) let w (s : Finset (Fin m)) : ℕ := (C.filter (cross s)).card have hF : F.Nonempty := ⟨∅, by simp [F]⟩ obtain ⟨s, hs, hmax⟩ := Finset.exists_max_image F w hF have hhalf (c : γ) (hc : c ∈ C) : 2 * (F.filter (fun s => cross s c)).card = F.card := by have hflip (s : Finset (Fin m)) : cross (s ∆ {u c}) c ↔ ¬ cross s c := by simp only [cross, Finset.mem_symmDiff, Finset.mem_singleton] have hne : v c ≠ u c := Ne.symm (huv c hc) simp only [hne, not_false_eq_true, and_true, and_false, or_false, or_true, not_true_eq_false] tauto have hequal : (F.filter (fun s => cross s c)).card = (F.filter (fun s => ¬ cross s c)).card := by apply Finset.card_bij' (fun s _ => s ∆ {u c}) (fun s _ => s ∆ {u c}) · intro s hs simp · intro s hs simp · intro s hs simp only [Finset.mem_filter] at hs ⊢ exact ⟨by simp [F], by simpa [hflip] using hs.2⟩ · intro s hs simp only [Finset.mem_filter] at hs ⊢ exact ⟨by simp [F], by simpa [hflip] using hs.2⟩ have htotal := Finset.card_filter_add_card_filter_not (s := F) (fun s => cross s c) omega have hsum : F.card * C.card = 2 * ∑ s ∈ F, w s := by calc F.card * C.card = ∑ c ∈ C, F.card := by simp [mul_comm] _ = ∑ c ∈ C, 2 * (F.filter (fun s => cross s c)).card := by apply Finset.sum_congr rfl intro c hc exact (hhalf c hc).symm _ = 2 * ∑ s ∈ F, w s := by have hcount (c : γ) : (F.filter (fun s => cross s c)).card = ∑ s ∈ F, if cross s c then 1 else 0 := by exact (Finset.sum_boole (R := ℕ) (fun s => cross s c) F).symm have hcount' (s : Finset (Fin m)) : w s = ∑ c ∈ C, if cross s c then 1 else 0 := by exact (Finset.sum_boole (R := ℕ) (fun c => cross s c) C).symm simp_rw [hcount, hcount', Finset.mul_sum] rw [Finset.sum_comm] refine ⟨s, ?_⟩ have hbound : (∑ t ∈ F, w t) ≤ F.card * w s := by simpa using Finset.sum_le_card_nsmul F w (w s) (fun t ht => hmax t ht) have hpos : 0 < F.card := Finset.card_pos.mpr hF have : C.card ≤ 2 * w s := by nlinarith simpa [w, cross] using this