AFTD Auto-Formalizing Theoretical Domains

op_1355_claw_center_partition_upper_bound

theoremverified

The total weight of independent sets containing the center is at most 17/16 for the explicit embedded-claw activity profile.

Statement

open scoped Classical BigOperators in
theorem op_1355_claw_center_partition_upper_bound
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (c u v w : V)
    (hadj : G.Adj c u ∧ G.Adj c v ∧ G.Adj c w)
    (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w)
    (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w)
    (lam : V → ℝ)
    (hlam : ∀ x, lam x = if x = c then 1 else if x = u ∨ x = v ∨ x = w then 10 else 1 / (16 * (2 : ℝ) ^ Fintype.card V)) :
    (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) ≤ (17 : ℝ) / 16
Source
OP-1355, explicit induced-claw witness for necessity
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • op_1355_claw_free_of_weighted_boundIf a finite simple graph G on a finite type V with decidable equality satisfies the weighted hard-core closed-neighborhood variance bound…

The proof, explained

The proof bounds the total weight of independent sets containing the claw center c under the activity profile λ. Because c is adjacent to the claw leaves u, v, and w, no independent set containing c can contain any of these high-weight vertices (where λ = 10). Consequently, the singleton set {c} has weight λ(c) = 1, while every other independent set containing c must contain at least one vertex outside {c, u, v, w}, which has weight ε = 1 / (16 * 2^|V|). Summing over all remaining independent sets (at most 2^|V| of them) contributes at most 2^|V| * ε = 1/16, yielding the upper bound 1 + 1/16 = 17/16.

  1. Define ε = 1 / (16 * 2^|V|) and show that 0 < ε ≤ 1.

    We set ε = 1 / (16 * 2^|V|). Since powers of 2 and 16 are positive, positivity shows 0 < ε. By one_le_pow₀, 2^|V| ≥ 1, so the denominator satisfies 16 * 2^|V| ≥ 16 ≥ 1, and div_le_one yields ε ≤ 1.

    lines 11–20

    uses div_le_one, one_le_pow₀

      classical
      let eps : ℝ := 1 / (16 * (2 : ℝ) ^ Fintype.card V)
      have heps_pos : 0 < eps := by
        dsimp [eps]
        positivity
      have heps_le_one : eps ≤ 1 := by
        dsimp [eps]
        rw [div_le_one (by positivity)]
        have h2 : (1 : ℝ) ≤ (2 : ℝ) ^ Fintype.card V := one_le_pow₀ (by norm_num)
        nlinarith
  2. Show that λ(c) = 1, λ(x) = ε for all x ∉ {c, u, v, w}, and λ is everywhere non-negative.

    By definition of λ, evaluating at c yields 1. For any x distinct from c, u, v, w, both conditional branches evaluate to false, giving λ(x) = ε. Since the possible values of λ are 1, 10, and ε, and 0 < ε, λ(x) ≥ 0 for all x.

    lines 21–34

      have hlam_c : lam c = 1 := by
        rw [hlam c]
        simp
      have hlam_eps : ∀ x, x ≠ c → x ≠ u → x ≠ v → x ≠ w → lam x = eps := by
        intro x hxc hxu hxv hxw
        rw [hlam x]
        simp [hxc, hxu, hxv, hxw, eps]
      have hlam_nonneg : ∀ x, 0 ≤ lam x := by
        intro x
        rw [hlam x]
        split_ifs with h1 h2
        · norm_num
        · norm_num
        · exact heps_pos.le
  3. Every vertex in an independent set containing c has activity λ(x) ≤ 1.

    Let I be an independent set with c ∈ I, and let x ∈ I. If x = c, then λ(x) = 1 ≤ 1. If x ≠ c, then x cannot be adjacent to c because I is independent. But c is adjacent to u, v, and w, so by Ne.symm, x cannot be any of u, v, or w. Hence x ∉ {c, u, v, w}, which implies λ(x) = ε ≤ 1.

    lines 35–53

    uses Ne.symm

      have hlam_le_one : ∀ {I : Finset V}, G.IsIndepSet (I : Set V) → c ∈ I → ∀ x ∈ I, lam x ≤ 1 := by
        intro I hInd hc x hx
        by_cases hxc : x = c
        · subst hxc
          exact hlam_c.le
        · have hxu : x ≠ u := by
            intro h
            subst h
            exact (hInd hc hx (Ne.symm hxc)) hadj.1
          have hxv : x ≠ v := by
            intro h
            subst h
            exact (hInd hc hx (Ne.symm hxc)) hadj.2.1
          have hxw : x ≠ w := by
            intro h
            subst h
            exact (hInd hc hx (Ne.symm hxc)) hadj.2.2
          rw [hlam_eps x hxc hxu hxv hxw]
          exact heps_le_one
  4. Define T as the finset of independent sets containing c, and observe that {c} ∈ T.

    We define T as the collection of all independent sets containing c, restating the goal as bounding the sum over T. The singleton {c} is an independent set (any two elements are both c, hence equal) and contains c, so {c} ∈ T.

    lines 54–63

    uses Finset.mem_filter, Finset.mem_univ, true_and

      let T : Finset (Finset V) := Finset.univ.filter (fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I)
      change (∑ I ∈ T, (∏ x ∈ I, lam x)) ≤ (17 : ℝ) / 16
      have hsingle_mem : ({c} : Finset V) ∈ T := by
        dsimp [T]
        simp only [Finset.mem_filter, Finset.mem_univ, true_and]
        constructor
        · intro x hx y hy hxy
          simp at hx hy
          exact absurd (hx.trans hy.symm) hxy
        · simp
  5. For every independent set I ∈ T other than {c}, the weight product is at most ε.

    Since I ∈ T and I ≠ {c}, there must exist some vertex x ∈ I with x ≠ c by Finset.eq_singleton_iff_unique_mem. Because I is independent and c ∈ I, x cannot be adjacent to c, hence x ∉ {u, v, w} by Ne.symm, giving λ(x) = ε. For all remaining vertices y ∈ I \ {x}, 0 ≤ λ(y) ≤ 1, so the product over I \ {x} is at most 1 by Finset.prod_le_one and Finset.mem_of_mem_erase. Factoring the product with Finset.mul_prod_erase and bounding via mul_le_mul_of_nonneg_left gives ∏ y ∈ I, λ(y) = λ(x) * ∏ y ∈ I \ {x}, λ(y) ≤ ε * 1 = ε.

    lines 64–108

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.eq_singleton_iff_unique_mem, Ne.symm, Finset.prod_le_one, Finset.mem_of_mem_erase, Finset.mul_prod_erase, mul_le_mul_of_nonneg_left

      have hbound : ∀ I ∈ T, I ≠ {c} → (∏ x ∈ I, lam x) ≤ eps := by
        intro I hI hne
        dsimp [T] at hI
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hI
        obtain ⟨hInd, hc⟩ := hI
        have hx_exists : ∃ x ∈ I, x ≠ c := by
          by_contra h
          have h' : ∀ x ∈ I, x = c := by
            intro x hx
            by_contra hxnc
            exact h ⟨x, hx, hxnc⟩
          have h_eq : I = {c} := by
            rw [Finset.eq_singleton_iff_unique_mem]
            exact ⟨hc, h'⟩
          exact hne h_eq
        obtain ⟨x, hxI, hxc⟩ := hx_exists
        have hxu : x ≠ u := by
          intro h
          subst h
          exact (hInd hc hxI (Ne.symm hxc)) hadj.1
        have hxv : x ≠ v := by
          intro h
          subst h
          exact (hInd hc hxI (Ne.symm hxc)) hadj.2.1
        have hxw : x ≠ w := by
          intro h
          subst h
          exact (hInd hc hxI (Ne.symm hxc)) hadj.2.2
        have hxlam : lam x = eps := hlam_eps x hxc hxu hxv hxw
        have hprod_le : (∏ y ∈ I.erase x, lam y) ≤ 1 := by
          apply Finset.prod_le_one
          · intro y _
            exact hlam_nonneg y
          · intro y hy
            exact hlam_le_one hInd hc y (Finset.mem_of_mem_erase hy)
        calc
          ∏ y ∈ I, lam y = lam x * ∏ y ∈ I.erase x, lam y := by
            rw [Finset.mul_prod_erase I lam hxI]
          _ ≤ lam x * 1 := by
            apply mul_le_mul_of_nonneg_left hprod_le
            rw [hxlam]
            exact heps_pos.le
          _ = eps := by
            rw [hxlam]
            ring
  6. The sum over T splits into 1 (from {c}) plus the sum over T \ {{c}}.

    Using Finset.add_sum_erase, the sum over T splits into the contribution from {c} and the sum over T \ {{c}}. By Finset.prod_singleton, the singleton product is λ(c) = 1.

    lines 109–112

    uses Finset.add_sum_erase, Finset.prod_singleton

      have hsplit : ∑ I ∈ T, (∏ x ∈ I, lam x) = 1 + ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) := by
        rw [← Finset.add_sum_erase T (fun I => ∏ x ∈ I, lam x) hsingle_mem]
        congr 1
        rw [Finset.prod_singleton, hlam_c]
  7. The sum over all remaining sets in T \ {{c}} is at most 1/16.

    By Finset.sum_le_sum and the bound on each I ∈ T \ {{c}}, the sum is bounded by |T \ {{c}}| * ε (using Finset.sum_const, nsmul_eq_mul, mul_comm, and Finset.mem_erase.mp). Since the total number of subsets of V is 2^|V| by Fintype.card_finset, Finset.card_le_univ bounds the cardinality by 2^|V|. Multiplying by ε using mul_le_mul_of_nonneg_left gives ε * 2^|V| = (1 / (16 * 2^|V|)) * 2^|V| = 1/16.

    lines 113–136

    uses Finset.sum_le_sum, Finset.mem_erase.mp, Finset.sum_const, nsmul_eq_mul, mul_comm, Finset.card_le_univ, Fintype.card_finset, mul_le_mul_of_nonneg_left

      have hrest : ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ (1 : ℝ) / 16 := by
        have h1 : ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ ∑ I ∈ T.erase {c}, eps := by
          apply Finset.sum_le_sum
          intro I hI
          have hI' : I ∈ T := (Finset.mem_erase.mp hI).2
          have hne : I ≠ {c} := (Finset.mem_erase.mp hI).1
          exact hbound I hI' hne
        have h2 : ∑ I ∈ T.erase {c}, eps = eps * ((T.erase {c}).card : ℝ) := by
          rw [Finset.sum_const, nsmul_eq_mul, mul_comm]
        have hcard : ((T.erase {c}).card : ℝ) ≤ (2 : ℝ) ^ Fintype.card V := by
          have h := Finset.card_le_univ (T.erase {c})
          rw [Fintype.card_finset] at h
          exact_mod_cast h
        have h3 : eps * ((T.erase {c}).card : ℝ) ≤ eps * (2 : ℝ) ^ Fintype.card V :=
          mul_le_mul_of_nonneg_left hcard heps_pos.le
        have h4 : eps * (2 : ℝ) ^ Fintype.card V = (1 : ℝ) / 16 := by
          dsimp [eps]
          field_simp
        calc
          ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ ∑ I ∈ T.erase {c}, eps := h1
          _ = eps * ((T.erase {c}).card : ℝ) := h2
          _ ≤ eps * (2 : ℝ) ^ Fintype.card V := h3
          _ = (1 : ℝ) / 16 := h4
      calc
  8. The total sum over independent sets containing c is at most 17/16.

    Adding the contribution 1 of the singleton {c} to the bound 1/16 for the remaining independent sets gives 1 + 1/16 = 17/16.

    lines 137–139

        ∑ I ∈ T, (∏ x ∈ I, lam x) = 1 + ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) := hsplit
        _ ≤ 1 + (1 : ℝ) / 16 := by linarith [hrest]
        _ = (17 : ℝ) / 16 := by norm_num
div_le_one
For a positive denominator b, a / b ≤ 1 if and only if a ≤ b.
one_le_pow₀
If 1 ≤ a, then 1 ≤ a^n for every natural number n.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
true_and
The proposition True ∧ p is equivalent to p.
Finset.eq_singleton_iff_unique_mem
A finset equals {a} if and only if it contains a and all its elements equal a.
Finset.prod_le_one
A product over a finset whose terms all lie in [0, 1] is at most 1.
Finset.mem_of_mem_erase
If an element belongs to s with a removed, it belongs to s.
Finset.mul_prod_erase
For an element a in a finset s, the product over s equals f(a) times the product over s with a removed.
mul_le_mul_of_nonneg_left
Multiplying an inequality on the left by a non-negative element preserves the inequality.
Finset.add_sum_erase
For an element a in a finset s, the sum over s equals f(a) plus the sum over s with a removed.
Finset.prod_singleton
The product of a function over a singleton set {a} equals f(a).
Finset.sum_le_sum
A sum of terms is bounded by the sum of their pointwise upper bounds.
Finset.mem_erase.mp
If an element belongs to s with a removed, it is not equal to a and belongs to s.
Finset.sum_const
The sum of a constant value b over a finset s equals |s| • b.
nsmul_eq_mul
Natural scalar multiplication in a semiring equals multiplication by the natural number cast to the scalar ring.
mul_comm
Multiplication is commutative.
Finset.card_le_univ
The cardinality of any finset of elements of type α is at most the total cardinality of α.
Fintype.card_finset
The number of finite subsets of a finite type α is 2^(card α).

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 Classical BigOperators intheorem op_1355_claw_center_partition_upper_bound    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (c u v w : V)    (hadj : G.Adj c u ∧ G.Adj c v ∧ G.Adj c w)    (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w)    (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w)    (lam : V → ℝ)    (hlam : ∀ x, lam x = if x = c then 1 else if x = u ∨ x = v ∨ x = w then 10 else 1 / (16 * (2 : ℝ) ^ Fintype.card V)) :    (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) ≤ (17 : ℝ) / 16 := by  classical  let eps : ℝ := 1 / (16 * (2 : ℝ) ^ Fintype.card V)  have heps_pos : 0 < eps := by    dsimp [eps]    positivity  have heps_le_one : eps ≤ 1 := by    dsimp [eps]    rw [div_le_one (by positivity)]    have h2 : (1 : ℝ) ≤ (2 : ℝ) ^ Fintype.card V := one_le_pow₀ (by norm_num)    nlinarith  have hlam_c : lam c = 1 := by    rw [hlam c]    simp  have hlam_eps : ∀ x, x ≠ c → x ≠ u → x ≠ v → x ≠ w → lam x = eps := by    intro x hxc hxu hxv hxw    rw [hlam x]    simp [hxc, hxu, hxv, hxw, eps]  have hlam_nonneg : ∀ x, 0 ≤ lam x := by    intro x    rw [hlam x]    split_ifs with h1 h2    · norm_num    · norm_num    · exact heps_pos.le  have hlam_le_one : ∀ {I : Finset V}, G.IsIndepSet (I : Set V) → c ∈ I → ∀ x ∈ I, lam x ≤ 1 := by    intro I hInd hc x hx    by_cases hxc : x = c    · subst hxc      exact hlam_c.le    · have hxu : x ≠ u := by        intro h        subst h        exact (hInd hc hx (Ne.symm hxc)) hadj.1      have hxv : x ≠ v := by        intro h        subst h        exact (hInd hc hx (Ne.symm hxc)) hadj.2.1      have hxw : x ≠ w := by        intro h        subst h        exact (hInd hc hx (Ne.symm hxc)) hadj.2.2      rw [hlam_eps x hxc hxu hxv hxw]      exact heps_le_one  let T : Finset (Finset V) := Finset.univ.filter (fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I)  change (∑ I ∈ T, (∏ x ∈ I, lam x)) ≤ (17 : ℝ) / 16  have hsingle_mem : ({c} : Finset V) ∈ T := by    dsimp [T]    simp only [Finset.mem_filter, Finset.mem_univ, true_and]    constructor    · intro x hx y hy hxy      simp at hx hy      exact absurd (hx.trans hy.symm) hxy    · simp  have hbound : ∀ I ∈ T, I ≠ {c} → (∏ x ∈ I, lam x) ≤ eps := by    intro I hI hne    dsimp [T] at hI    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hI    obtain ⟨hInd, hc⟩ := hI    have hx_exists : ∃ x ∈ I, x ≠ c := by      by_contra h      have h' : ∀ x ∈ I, x = c := by        intro x hx        by_contra hxnc        exact h ⟨x, hx, hxnc⟩      have h_eq : I = {c} := by        rw [Finset.eq_singleton_iff_unique_mem]        exact ⟨hc, h'⟩      exact hne h_eq    obtain ⟨x, hxI, hxc⟩ := hx_exists    have hxu : x ≠ u := by      intro h      subst h      exact (hInd hc hxI (Ne.symm hxc)) hadj.1    have hxv : x ≠ v := by      intro h      subst h      exact (hInd hc hxI (Ne.symm hxc)) hadj.2.1    have hxw : x ≠ w := by      intro h      subst h      exact (hInd hc hxI (Ne.symm hxc)) hadj.2.2    have hxlam : lam x = eps := hlam_eps x hxc hxu hxv hxw    have hprod_le : (∏ y ∈ I.erase x, lam y) ≤ 1 := by      apply Finset.prod_le_one      · intro y _        exact hlam_nonneg y      · intro y hy        exact hlam_le_one hInd hc y (Finset.mem_of_mem_erase hy)    calc      ∏ y ∈ I, lam y = lam x * ∏ y ∈ I.erase x, lam y := by        rw [Finset.mul_prod_erase I lam hxI]      _ ≤ lam x * 1 := by        apply mul_le_mul_of_nonneg_left hprod_le        rw [hxlam]        exact heps_pos.le      _ = eps := by        rw [hxlam]        ring  have hsplit : ∑ I ∈ T, (∏ x ∈ I, lam x) = 1 + ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) := by    rw [← Finset.add_sum_erase T (fun I => ∏ x ∈ I, lam x) hsingle_mem]    congr 1    rw [Finset.prod_singleton, hlam_c]  have hrest : ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ (1 : ℝ) / 16 := by    have h1 : ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ ∑ I ∈ T.erase {c}, eps := by      apply Finset.sum_le_sum      intro I hI      have hI' : I ∈ T := (Finset.mem_erase.mp hI).2      have hne : I ≠ {c} := (Finset.mem_erase.mp hI).1      exact hbound I hI' hne    have h2 : ∑ I ∈ T.erase {c}, eps = eps * ((T.erase {c}).card : ℝ) := by      rw [Finset.sum_const, nsmul_eq_mul, mul_comm]    have hcard : ((T.erase {c}).card : ℝ) ≤ (2 : ℝ) ^ Fintype.card V := by      have h := Finset.card_le_univ (T.erase {c})      rw [Fintype.card_finset] at h      exact_mod_cast h    have h3 : eps * ((T.erase {c}).card : ℝ) ≤ eps * (2 : ℝ) ^ Fintype.card V :=      mul_le_mul_of_nonneg_left hcard heps_pos.le    have h4 : eps * (2 : ℝ) ^ Fintype.card V = (1 : ℝ) / 16 := by      dsimp [eps]      field_simp    calc      ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) ≤ ∑ I ∈ T.erase {c}, eps := h1      _ = eps * ((T.erase {c}).card : ℝ) := h2      _ ≤ eps * (2 : ℝ) ^ Fintype.card V := h3      _ = (1 : ℝ) / 16 := h4  calc    ∑ I ∈ T, (∏ x ∈ I, lam x) = 1 + ∑ I ∈ T.erase {c}, (∏ x ∈ I, lam x) := hsplit    _ ≤ 1 + (1 : ℝ) / 16 := by linarith [hrest]    _ = (17 : ℝ) / 16 := by norm_num
See it in the graphDiscuss this resultChallenge it