op_1355_claw_center_partition_upper_bound
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.
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.
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
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.
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
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.
uses
Ne.symmhave 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
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.
uses
Finset.mem_filter,Finset.mem_univ,true_andlet 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
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 = ε.
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_lefthave 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
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.
uses
Finset.add_sum_erase,Finset.prod_singletonhave 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]
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.
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_lefthave 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
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.
∑ 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 α).
- Although the theorem assumes the vertices u, v, w are pairwise distinct and non-adjacent, these hypotheses (hdist and hnon) are unused in the proof; only the adjacency of c to u, v, w (hadj) is needed to exclude the high-weight vertices.
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 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