op_1355_independent_triple_partition_lower_bound
If three distinct pairwise nonadjacent vertices have activity 10 and every activity is nonnegative, the hard-core partition function is at least 1331.
Statement
open scoped Classical BigOperators in theorem op_1355_independent_triple_partition_lower_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v w : V) (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w) (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w) (lam : V → ℝ) (hpos : ∀ x, 0 ≤ lam x) (hleaves : lam u = 10 ∧ lam v = 10 ∧ lam w = 10) : (1331 : ℝ) ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), ∏ x ∈ I, lam x
- 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 restricts the partition function sum—which runs over all independent sets of G—to the subsets of the three given vertices L = {u, v, w}. Because u, v, w are pairwise nonadjacent, L is an independent set, and every subset of L is independent as well. By nonnegativity of vertex activities, the full partition function is bounded below by the sum over subsets of L, which factors as ∏_{x ∈ L} (1 + lam x) = (1 + 10)³ = 1331.
The triple L = {u, v, w} forms an independent set in G
We define L = {u, v, w}. To show that L is an independent set, we consider any two distinct elements a, b ∈ L and show that they are not adjacent. Since each of a and b is u, v, or w, case analysis yields nine cases. The three diagonal cases a = b contradict distinctness (a ≠ b). The remaining six cases follow directly from the hypothesis that u, v, and w are pairwise nonadjacent, applying the symmetry of adjacency (G.adj_comm).
uses
Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,G.adj_commclassical let L : Finset V := {u,v,w} have hL : G.IsIndepSet (L : Set V) := by intro a ha b hb hab simp only [Finset.mem_coe, L, Finset.mem_insert, Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;> simp_all [G.adj_comm]
Every subset of L is an independent set of G, so the powerset of L is contained in the family F of all independent sets
Let F be the family of all independent sets in G. Any subset I of L belongs to L.powerset (by Finset.mem_powerset.mp). Because independent sets are hereditary under taking subsets (hL.mono), every subset I ⊆ L is also independent, and hence I ∈ F (by Finset.mem_filter.mpr and Finset.mem_univ).
uses
Finset.mem_powerset.mp,Finset.mem_filter.mpr,Finset.mem_univlet F : Finset (Finset V) := Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) have hsub : L.powerset ⊆ F := by intro I hI have hIL : I ⊆ L := Finset.mem_powerset.mp hI apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, hL.mono (by exact_mod_cast hIL)⟩
For every subset of vertices I, the product of vertex activities ∏ x ∈ I, lam x is nonnegative
Since all vertex activities are nonnegative by assumption (hpos), any finite product of vertex activities is nonnegative by Finset.prod_nonneg.
uses
Finset.prod_nonneghave hn (I : Finset V) : 0 ≤ ∏ x ∈ I, lam x := by exact Finset.prod_nonneg fun x hx => hpos x
The sum of the weights ∏ x ∈ I, lam x over all subsets I ⊆ L equals 1331
By the identity Finset.prod_one_add, the sum of products over all subsets of L equals the product ∏ x ∈ L, (1 + lam x). Since u, v, w are three distinct vertices with activity 10, this product simplifies to (1 + 10) * (1 + 10) * (1 + 10) = 11³ = 1331.
uses
Finset.prod_one_addhave hweight : (∑ I ∈ L.powerset, ∏ x ∈ I, lam x) = 1331 := by rw [← Finset.prod_one_add] simp [L, hdist.1, hdist.2.1, hdist.2.2, hdist.1.symm, hdist.2.1.symm, hdist.2.2.symm, hleaves.1, hleaves.2.1, hleaves.2.2] <;> norm_num
The total partition function is at least 1331
Because L.powerset is a subcollection of all independent sets F and every term in the sum is nonnegative, Finset.sum_le_sum_of_subset_of_nonneg shows that the sum over all independent sets is at least the sum over the powerset of L. Combining this with the value 1331 from the previous step via linear arithmetic establishes the lower bound.
uses
Finset.sum_le_sum_of_subset_of_nonneghave hmono := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun I _ _ => hn I) change (1331 : ℝ) ≤ ∑ I ∈ F, ∏ x ∈ I, lam x linarith
Finset.mem_coe- an element belongs to a coerced finset if and only if it belongs to the finset
Finset.mem_insert- an element belongs to insert b s if and only if it equals b or belongs to s
Finset.mem_singleton- an element belongs to the singleton {a} if and only if it equals a
G.adj_comm- adjacency in a simple graph is symmetric: u is adjacent to v if and only if v is adjacent to u
Finset.mem_powerset.mp- an element belongs to the powerset of s only if it is a subset of s
Finset.mem_filter.mpr- an element belongs to the filtered sub-finset if it belongs to the original finset and satisfies the predicate
Finset.mem_univ- every element of a finite type belongs to the universal finset Finset.univ
Finset.prod_nonneg- a finite product of nonnegative terms is nonnegative
Finset.prod_one_add- the product of (1 + f(x)) over a finite set s equals the sum over all subsets of s of the product of f(x)
Finset.sum_le_sum_of_subset_of_nonneg- if s is a subset of t and all terms on t \\ s are nonnegative, then the sum over s is at most the sum over t
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_independent_triple_partition_lower_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v w : V) (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w) (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w) (lam : V → ℝ) (hpos : ∀ x, 0 ≤ lam x) (hleaves : lam u = 10 ∧ lam v = 10 ∧ lam w = 10) : (1331 : ℝ) ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), ∏ x ∈ I, lam x := by classical let L : Finset V := {u,v,w} have hL : G.IsIndepSet (L : Set V) := by intro a ha b hb hab simp only [Finset.mem_coe, L, Finset.mem_insert, Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl <;> simp_all [G.adj_comm] let F : Finset (Finset V) := Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) have hsub : L.powerset ⊆ F := by intro I hI have hIL : I ⊆ L := Finset.mem_powerset.mp hI apply Finset.mem_filter.mpr exact ⟨Finset.mem_univ _, hL.mono (by exact_mod_cast hIL)⟩ have hn (I : Finset V) : 0 ≤ ∏ x ∈ I, lam x := by exact Finset.prod_nonneg fun x hx => hpos x have hweight : (∑ I ∈ L.powerset, ∏ x ∈ I, lam x) = 1331 := by rw [← Finset.prod_one_add] simp [L, hdist.1, hdist.2.1, hdist.2.2, hdist.1.symm, hdist.2.1.symm, hdist.2.2.symm, hleaves.1, hleaves.2.1, hleaves.2.2] <;> norm_num have hmono := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun I _ _ => hn I) change (1331 : ℝ) ≤ ∑ I ∈ F, ∏ x ∈ I, lam x linarith