AFTD Auto-Formalizing Theoretical Domains

op869_orient_pairs_half

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

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.

  1. 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).

    lines 7–13

    uses Finset.exists_max_image

      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
  2. 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).

    lines 14–34

    uses Ne.symm, Finset.mem_symmDiff, Finset.mem_singleton, Finset.card_bij', Finset.mem_filter, Finset.card_filter_add_card_filter_not

      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
  3. 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).

    lines 35–50

    uses mul_comm, Finset.sum_congr, Finset.sum_boole, Finset.mul_sum, Finset.sum_comm

      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]
  4. 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).

    lines 51–56

    uses Finset.sum_le_card_nsmul, Finset.card_pos.mpr

      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
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

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
See it in the graphDiscuss this resultChallenge it