AFTD Auto-Formalizing Theoretical Domains

op_1355_independent_triple_partition_lower_bound

theoremverified

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.

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

    lines 10–16

    uses Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, G.adj_comm

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

    lines 17–22

    uses Finset.mem_powerset.mp, Finset.mem_filter.mpr, Finset.mem_univ

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

    lines 23–24

    uses Finset.prod_nonneg

      have hn (I : Finset V) : 0 ≤ ∏ x ∈ I, lam x := by
        exact Finset.prod_nonneg fun x hx => hpos x
  4. 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.

    lines 25–28

    uses Finset.prod_one_add

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

    lines 29–31

    uses Finset.sum_le_sum_of_subset_of_nonneg

      have 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

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