op_1355_claw_neighborhood_sum_upper_bound
The closed-neighborhood activity sum at the center is at most 31+1/16 for the explicit embedded-claw profile.
Statement
open scoped Classical BigOperators in theorem op_1355_claw_neighborhood_sum_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)) : (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ (31 : ℝ) + 1 / 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 partitions the closed neighborhood S = {c} ∪ N(c) of the claw center c into the four claw vertices B = {c, u, v, w} and the remaining neighbors S \ B. Because c is adjacent to u, v, w and all four vertices are distinct, the sum of λ over B evaluates exactly to 1 + 10 + 10 + 10 = 31. On the remaining vertices in S \ B, each vertex has the small activity 1 / (16 * 2^|V|), giving a sum bounded by |V| * (1 / (16 * 2^|V|)) ≤ 1/16 using |V| ≤ 2^|V|. Combining these two contributions yields the upper bound 31 + 1/16.
Define the closed neighborhood S and claw vertex set B, and establish that c, u, v, w are pairwise distinct.
We define S = {c} ∪ N(c) for the closed neighborhood of c, and B = {c, u, v, w} for the vertices of the claw. Since c is adjacent to u, v, and w in the simple graph G (which has no self-loops), c cannot equal u, v, or w. Combining this with the hypothesis hdist that u, v, w are pairwise distinct ensures that all four vertices in B are distinct.
classical set S := insert c (G.neighborFinset c) with hS set B : Finset V := {c, u, v, w} with hB have hcu : c ≠ u := hadj.1.ne have hcv : c ≠ v := hadj.2.1.ne have hcw : c ≠ w := hadj.2.2.ne have huc : u ≠ c := hadj.1.ne' have hvc : v ≠ c := hadj.2.1.ne' have hwc : w ≠ c := hadj.2.2.ne' have huv : u ≠ v := hdist.1 have huw : u ≠ w := hdist.2.1 have hvw : v ≠ w := hdist.2.2
B is a subset of S.
For any vertex x ∈ B = {c, u, v, w}, either x = c (which is in S by definition), or x is one of u, v, w, in which case x is adjacent to c and hence lies in the neighborhood N(c) ⊆ S.
uses
Finset.mem_insert,Finset.mem_singleton,SimpleGraph.mem_neighborFinsethave hBsub : B ⊆ S := by intro x hx rw [hB] at hx rw [hS] simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢ rcases hx with hxc | hxu | hxv | hxw · exact Or.inl hxc · exact Or.inr (hxu.symm ▸ (SimpleGraph.mem_neighborFinset G c u).mpr hadj.1) · exact Or.inr (hxv.symm ▸ (SimpleGraph.mem_neighborFinset G c v).mpr hadj.2.1) · exact Or.inr (hxw.symm ▸ (SimpleGraph.mem_neighborFinset G c w).mpr hadj.2.2)
The activity values on B are λ(c) = 1 and λ(u) = λ(v) = λ(w) = 10.
Evaluating the piecewise definition of λ at c triggers the first branch, giving 1. At u, v, and w, each vertex is distinct from c, which bypasses the first branch and satisfies the second condition x ∈ {u, v, w}, resulting in the value 10 for each.
have hlamc : lam c = 1 := by rw [hlam c]; simp have hlamu : lam u = 10 := by rw [hlam u]; simp [huc] have hlamv : lam v = 10 := by rw [hlam v]; simp [hvc] have hlamw : lam w = 10 := by rw [hlam w]; simp [hwc]
The sum of λ over B equals 31.
Because the four vertices c, u, v, w are pairwise distinct, the finite set sum over B decomposes into the sum of the four individual values λ(c) + λ(u) + λ(v) + λ(w) = 1 + 10 + 10 + 10 = 31.
uses
Finset.sum_insert,Finset.sum_singletonhave hsumB : ∑ x ∈ B, lam x = 31 := by rw [hB] rw [Finset.sum_insert (by simp [hcu, hcv, hcw])] rw [Finset.sum_insert (by simp [huv, huw])] rw [Finset.sum_insert (by simp [hvw])] rw [Finset.sum_singleton] rw [hlamc, hlamu, hlamv, hlamw] norm_num
For every vertex x ∈ S \ B, λ(x) = 1 / (16 * 2^|V|).
Any vertex x in the difference S \ B does not belong to B, so x ≠ c, x ≠ u, x ≠ v, and x ≠ w. Consequently, evaluating λ(x) bypasses both the c branch and the {u, v, w} branch, falling into the default branch.
uses
Finset.mem_sdiff,Finset.mem_insert,Finset.mem_singleton,not_orhave hsmall : ∀ x ∈ S \ B, lam x = 1 / (16 * (2:ℝ) ^ Fintype.card V) := by intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨hxS, hxB⟩ := hx rw [hB] at hxB simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hxB obtain ⟨hxc, hxu, hxv, hxw⟩ := hxB rw [hlam x] simp [hxc, hxu, hxv, hxw]
The sum of λ over S \ B is at most |V| * (1 / (16 * 2^|V|)).
Since λ is constant on S \ B, the sum equals |S \ B| * (1 / (16 * 2^|V|)). Bounding the size of S \ B by the total number of vertices |V| yields the upper bound.
uses
Finset.sum_congr,Finset.sum_const,nsmul_eq_mul,mul_le_mul_of_nonneg_right,Finset.card_le_univhave hstep7 : ∑ x ∈ S \ B, lam x ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by have hcongr : ∑ x ∈ S \ B, lam x = ∑ x ∈ S \ B, (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by apply Finset.sum_congr rfl intro x hx exact hsmall x hx rw [hcongr, Finset.sum_const, nsmul_eq_mul] apply mul_le_mul_of_nonneg_right _ (by positivity) exact_mod_cast Finset.card_le_univ (S \ B)
|V| * (1 / (16 * 2^|V|)) ≤ 1/16.
By the standard inequality n < 2^n for natural numbers, we have |V| ≤ 2^|V| in the reals. Multiplying both sides by the positive factor 1 / (16 * 2^|V|) gives at most 2^|V| * (1 / (16 * 2^|V|)) = 1/16.
uses
Nat.lt_two_pow_self,Nat.cast_le,Nat.cast_pow,mul_le_mul_of_nonneg_right,le_of_lthave hfinal : (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ 1/16 := by have hnlt_nat : Fintype.card V ≤ 2 ^ Fintype.card V := (Nat.lt_two_pow_self).le have hnlt : (Fintype.card V : ℝ) ≤ (2:ℝ) ^ Fintype.card V := by have := Nat.cast_le (α := ℝ).mpr hnlt_nat rwa [Nat.cast_pow] at this have hpos : (0:ℝ) < 1 / (16 * (2:ℝ) ^ Fintype.card V) := by positivity calc (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ (2:ℝ) ^ Fintype.card V * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := mul_le_mul_of_nonneg_right hnlt (le_of_lt hpos) _ = 1/16 := by field_simp
The total neighborhood sum of λ over S is at most 31 + 1/16.
Because B ⊆ S, the sum over S splits into the sum over S \ B plus the sum over B. Substituting the value 31 for B and the bound 1/16 for S \ B gives at most 31 + 1/16.
uses
Finset.sum_sdiffcalc ∑ x ∈ S, lam x = ∑ x ∈ S \ B, lam x + ∑ x ∈ B, lam x := (Finset.sum_sdiff hBsub).symm _ = ∑ x ∈ S \ B, lam x + 31 := by rw [hsumB] _ ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) + 31 := by linarith [hstep7] _ ≤ 1/16 + 31 := by linarith [hfinal] _ = 31 + 1/16 := by ring
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
Finset.mem_insert- An element is in insert a s if and only if it equals a or is in s.
Finset.mem_sdiff- An element is in the set difference s \ t if and only if it is in s and not in t.
Finset.mem_singleton- An element is in {a} if and only if it equals a.
Finset.sum_congr- Two sums over finite sets are equal if the index sets are equal and the summands agree on every element.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set times the constant.
Finset.sum_insert- If a ∉ s, the sum of a function over insert a s equals its value at a plus its sum over s.
Finset.sum_sdiff- For a subset s₁ ⊆ s₂, the sum over s₂ equals the sum over s₂ \ s₁ plus the sum over s₁.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the function evaluated at a.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
mul_le_mul_of_nonneg_right- If b ≤ c and a ≥ 0, then b * a ≤ c * a.
Nat.cast_le- For natural numbers m and n, m ≤ n if and only if their casts to an ordered semiring satisfy ↑m ≤ ↑n.
Nat.cast_pow- The cast of a power of natural numbers m^n into a semiring equals (↑m)^n.
Nat.lt_two_pow_self- For every natural number n, n < 2^n.
not_or- The negation ¬(p ∨ q) is logically equivalent to ¬p ∧ ¬q.
nsmul_eq_mul- Natural scalar multiplication n • a in a semiring equals the product of the cast of n with a.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent in the graph.
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_neighborhood_sum_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)) : (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ (31 : ℝ) + 1 / 16 := by classical set S := insert c (G.neighborFinset c) with hS set B : Finset V := {c, u, v, w} with hB have hcu : c ≠ u := hadj.1.ne have hcv : c ≠ v := hadj.2.1.ne have hcw : c ≠ w := hadj.2.2.ne have huc : u ≠ c := hadj.1.ne' have hvc : v ≠ c := hadj.2.1.ne' have hwc : w ≠ c := hadj.2.2.ne' have huv : u ≠ v := hdist.1 have huw : u ≠ w := hdist.2.1 have hvw : v ≠ w := hdist.2.2 have hBsub : B ⊆ S := by intro x hx rw [hB] at hx rw [hS] simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢ rcases hx with hxc | hxu | hxv | hxw · exact Or.inl hxc · exact Or.inr (hxu.symm ▸ (SimpleGraph.mem_neighborFinset G c u).mpr hadj.1) · exact Or.inr (hxv.symm ▸ (SimpleGraph.mem_neighborFinset G c v).mpr hadj.2.1) · exact Or.inr (hxw.symm ▸ (SimpleGraph.mem_neighborFinset G c w).mpr hadj.2.2) have hlamc : lam c = 1 := by rw [hlam c]; simp have hlamu : lam u = 10 := by rw [hlam u]; simp [huc] have hlamv : lam v = 10 := by rw [hlam v]; simp [hvc] have hlamw : lam w = 10 := by rw [hlam w]; simp [hwc] have hsumB : ∑ x ∈ B, lam x = 31 := by rw [hB] rw [Finset.sum_insert (by simp [hcu, hcv, hcw])] rw [Finset.sum_insert (by simp [huv, huw])] rw [Finset.sum_insert (by simp [hvw])] rw [Finset.sum_singleton] rw [hlamc, hlamu, hlamv, hlamw] norm_num have hsmall : ∀ x ∈ S \ B, lam x = 1 / (16 * (2:ℝ) ^ Fintype.card V) := by intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨hxS, hxB⟩ := hx rw [hB] at hxB simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hxB obtain ⟨hxc, hxu, hxv, hxw⟩ := hxB rw [hlam x] simp [hxc, hxu, hxv, hxw] have hstep7 : ∑ x ∈ S \ B, lam x ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by have hcongr : ∑ x ∈ S \ B, lam x = ∑ x ∈ S \ B, (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by apply Finset.sum_congr rfl intro x hx exact hsmall x hx rw [hcongr, Finset.sum_const, nsmul_eq_mul] apply mul_le_mul_of_nonneg_right _ (by positivity) exact_mod_cast Finset.card_le_univ (S \ B) have hfinal : (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ 1/16 := by have hnlt_nat : Fintype.card V ≤ 2 ^ Fintype.card V := (Nat.lt_two_pow_self).le have hnlt : (Fintype.card V : ℝ) ≤ (2:ℝ) ^ Fintype.card V := by have := Nat.cast_le (α := ℝ).mpr hnlt_nat rwa [Nat.cast_pow] at this have hpos : (0:ℝ) < 1 / (16 * (2:ℝ) ^ Fintype.card V) := by positivity calc (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ (2:ℝ) ^ Fintype.card V * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := mul_le_mul_of_nonneg_right hnlt (le_of_lt hpos) _ = 1/16 := by field_simp calc ∑ x ∈ S, lam x = ∑ x ∈ S \ B, lam x + ∑ x ∈ B, lam x := (Finset.sum_sdiff hBsub).symm _ = ∑ x ∈ S \ B, lam x + 31 := by rw [hsumB] _ ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) + 31 := by linarith [hstep7] _ ≤ 1/16 + 31 := by linarith [hfinal] _ = 31 + 1/16 := by ring