op_1355_claw_free_of_weighted_bound
If a finite simple graph G on a finite type V with decidable equality satisfies the weighted hard-core closed-neighborhood variance bound hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a for all positive vertex fugacities lam and all nonnegative observable weights a, then G is claw-free.
Statement
theorem op_1355_claw_free_of_weighted_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbound : ∀ (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v), hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a) : IsClawFree G
- Formalizes
- OP-1355
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- hardCoreWeightedVarGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a, hardCoreWeightedVar G lam a…
- hardCoreWeightedClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a,…
- IsClawFreeA simple graph G is claw-free if it does not contain the complete bipartite graph K_{1,3} as an induced subgraph.
- op_1355_independent_triple_partition_lower_boundIf three distinct pairwise nonadjacent vertices have activity 10 and every activity is nonnegative, the hard-core partition function is at…
- op_1355_claw_center_partition_upper_boundThe total weight of independent sets containing the center is at most 17/16 for the explicit embedded-claw activity profile.
- op_1355_claw_neighborhood_sum_upper_boundThe closed-neighborhood activity sum at the center is at most 31+1/16 for the explicit embedded-claw profile.
- op_1355_center_violation_of_partition_boundsA center-only observable violates the weighted local variance bound whenever the center activity is one, its partition weight is between 0…
Read back from the Lean
Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Suppose that for every function $\lambda : V \to \mathbb{R}$ satisfying $\lambda(v) > 0$ for all $v \in V$, and for every function $a : V \to \mathbb{R}$ satisfying $a(v) \ge 0$ for all $v \in V$, the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam a is less than or equal to the hard-core weighted variance hardCoreWeightedVar G lam a. Then $G$ is claw-free (i.e., $G$ does not contain an induced subgraph isomorphic to the complete bipartite graph $K_{1,3}$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by contradiction: if G is not claw-free, it contains an induced claw K_{1,3} with center c and leaves u, v, w. Assigning vertex fugacities 1 at c, 10 at the leaves {u, v, w}, and a tiny value ε elsewhere makes the partition function large (Z ≥ 1331 from the 8 independent subsets of {u, v, w}) while keeping the weight of independent sets containing c small (at most 17/16, since c blocks all three leaves). Testing the variance bound against the indicator observable of c produces a strict inequality in the opposite direction, contradicting the hypothesis that the bound holds universally.
If G is not claw-free, there exists an induced subgraph embedding f from the complete bipartite graph K_{1,3} into G. automation
By definition, a graph G is claw-free if it does not contain the claw K_{1,3} as an induced subgraph. Negating this definition gives an induced subgraph embedding f from K_{1,3} into G.
classical have hex : SimpleGraph.IsIndContained (completeBipartiteGraph (Fin 1) (Fin 3)) G := by simpa [IsClawFree] using h obtain ⟨f⟩ := hex
The images u, v, w of the three leaf vertices of K_{1,3} under f are pairwise distinct. automation
Define c as the image of the solitary center vertex in K_{1,3}, and u, v, w as the images of the three leaf vertices. Since f is an embedding, it is injective; if any two leaf images were equal, injectivity would force the distinct indices in Fin 3 to be equal, which is contradicted by numerical evaluation.
uses
congrArglet c := f (Sum.inl (0 : Fin 1)) let u := f (Sum.inr (0 : Fin 3)) let v := f (Sum.inr (1 : Fin 3)) let w := f (Sum.inr (2 : Fin 3)) have huv : u ≠ v := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv have huw : u ≠ w := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv have hvw : v ≠ w := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv
The vertices c, u, v, w form an induced claw: c is adjacent to u, v, w, and no edge exists among {u, v, w}. automation
Because f is an induced embedding, two vertices in G are adjacent if and only if their preimages are adjacent in K_{1,3}. In K_{1,3}, the center is connected to all three leaves, while no two leaves are adjacent to each other.
refine ⟨c,u,v,w, ⟨?_,?_,?_⟩, ⟨huv,huw,hvw⟩, ⟨?_,?_,?_⟩⟩ all_goals dsimp only [c, u, v, w] all_goals rw [f.map_rel_iff] all_goals simp [completeBipartiteGraph]
Assume for contradiction that G is not claw-free, giving an induced claw with center c and leaves u, v, w.
We proceed by contradiction. Supposing G is not claw-free, the scratch lemma produces a center vertex c adjacent to three distinct, mutually non-adjacent leaves u, v, w.
uses
op1355_not_claw_free_quadruple_scratchclassical by_contra h obtain ⟨c,u,v,w,hadj,hdist,hnon⟩ := op1355_not_claw_free_quadruple_scratch G h
Define vertex fugacities lam that are strictly positive, equal to 1 at c, equal to 10 at {u, v, w}, and equal to a small eps elsewhere. automation
Let eps = 1 / (16 * 2^|V|), which is strictly positive. We set lam(c) = 1, lam(x) = 10 for x ∈ {u, v, w}, and lam(x) = eps elsewhere. Since c is adjacent to each leaf, c is distinct from u, v, and w, so lam(c) = 1, while lam(u) = lam(v) = lam(w) = 10, and lam is strictly positive on all vertices.
let eps : ℝ := 1 / (16 * (2:ℝ)^Fintype.card V) have heps : 0 < eps := by dsimp [eps]; positivity let lam : V → ℝ := fun x => if x=c then 1 else if x=u ∨ x=v ∨ x=w then 10 else eps have hlamdef : ∀ 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) := by intro x; rfl have hpos : ∀ x, 0 < lam x := by intro x dsimp only [lam] split_ifs <;> positivity have hc : lam c = 1 := by simp [lam] have hu : lam u = 10 := by simp [lam, hadj.1.ne'] have hv : lam v = 10 := by simp [lam, hadj.2.1.ne'] have hw : lam w = 10 := by simp [lam, hadj.2.2.ne']
Under fugacities lam, the partition function satisfies Z ≥ 1331, the center independent set sum satisfies 0 ≤ P ≤ 17/16, and the closed neighborhood sum satisfies 0 < D ≤ 33. automation
The three mutually non-adjacent vertices {u, v, w} have fugacities 10, so their 8 independent subsets contribute at least (1 + 10)³ = 1331 to the partition function Z. Any independent set containing c cannot contain any of its neighbors u, v, w, so the total weight P of such sets is at most 17/16. Finally, the closed neighborhood sum D = 1 + ∑_{x ∈ N[c]} lam(x) has lam(c) = 1 and three neighbors contributing 10 each, with any other neighbors contributing at most eps, bounding D by 1 + 31 + 1/16 ≤ 33.
uses
Finset.prod_nonneg,Finset.sum_nonneg,le_of_lt,op_1355_claw_center_partition_upper_bound,op_1355_claw_neighborhood_sum_upper_bound,op_1355_independent_triple_partition_lower_boundhave hZ := op_1355_independent_triple_partition_lower_bound G u v w hdist hnon lam (fun x => le_of_lt (hpos x)) ⟨hu,hv,hw⟩ have hPmax := op_1355_claw_center_partition_upper_bound G c u v w hadj hdist hnon lam hlamdef have hP : 0 ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x := by exact Finset.sum_nonneg fun I _ => Finset.prod_nonneg fun x _ => le_of_lt (hpos x) have hD : 0 < 1 + ∑ x ∈ insert c (G.neighborFinset c), lam x := by have hs : 0 ≤ ∑ x ∈ insert c (G.neighborFinset c), lam x := Finset.sum_nonneg fun x _ => le_of_lt (hpos x) linarith have hDmax : 1 + (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ 33 := by have hN := op_1355_claw_neighborhood_sum_upper_bound G c u v w hadj hdist hnon lam hlamdef linarith
The variance bound is strictly violated for the observable indicator of c, contradicting the hypothesis and establishing that G is claw-free. automation
For the nonnegative observable a = 1_{c}, the center violation lemma shows that the bounds Z ≥ 1331, P ≤ 17/16, and D ≤ 33 force the variance of a to be strictly strictly less than the closed neighborhood bound term. However, the hypothesis guarantees that the closed neighborhood bound is less than or equal to the variance for all positive fugacities and nonnegative observables, yielding a contradiction.
uses
not_lt_of_ge,op_1355_center_violation_of_partition_boundshave hviol := op_1355_center_violation_of_partition_bounds G lam c hc hZ hP hPmax hD hDmax have ha : ∀ x, 0 ≤ (if x = c then (1:ℝ) else 0) := by intro x; split_ifs <;> norm_num exact (not_lt_of_ge (hbound lam hpos _ ha)) hviol
congrArg- Applying a function to equal arguments yields equal results.
Finset.prod_nonneg- A finite product of nonnegative terms is nonnegative.
Finset.sum_nonneg- A finite sum of nonnegative terms is nonnegative.
le_of_lt- If a < b, then a ≤ b.
not_lt_of_ge- If a ≤ b, then it is false that b < a.
op1355_not_claw_free_quadruple_scratch- If G is not claw-free, there exist vertices c, u, v, w such that c is adjacent to u, v, w, the vertices u, v, w are pairwise distinct, and no two of u, v, w are adjacent.
op_1355_claw_center_partition_upper_bound- Under the specified fugacity assignment on a claw, the sum of weights of independent sets containing the claw center c is at most 17/16.
op_1355_claw_neighborhood_sum_upper_bound- Under the specified fugacity assignment on a claw, the sum of fugacities in the closed neighborhood of the center c is at most 31 + 1/16.
op_1355_center_violation_of_partition_bounds- If lam(c) = 1, the partition function Z is at least 1331, the center independent sum P satisfies 0 ≤ P ≤ 17/16, and the closed neighborhood sum D satisfies 0 < D ≤ 33, then the hard-core variance of the indicator observable of c is strictly less than the closed neighborhood bound.
op_1355_independent_triple_partition_lower_bound- In any graph with nonnegative vertex fugacities where three mutually non-adjacent vertices u, v, w each have fugacity 10, the hard-core partition function is at least (1 + 10)³ = 1331.
- The proof relies on several auxiliary bounds proved separately for the hard-core model on claws: a lower bound on the partition function from the three leaves, an upper bound on independent sets containing the center, an upper bound on the closed neighborhood sum, and an algebraic lemma showing that these bounds force the variance bound to be strictly violated.
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.
theorem op1355_not_claw_free_quadruple_scratch {V : Type*} (G : SimpleGraph V) (h : ¬ IsClawFree G) : ∃ c u v w : V, (G.Adj c u ∧ G.Adj c v ∧ G.Adj c w) ∧ (u ≠ v ∧ u ≠ w ∧ v ≠ w) ∧ (¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w) := by classical have hex : SimpleGraph.IsIndContained (completeBipartiteGraph (Fin 1) (Fin 3)) G := by simpa [IsClawFree] using h obtain ⟨f⟩ := hex let c := f (Sum.inl (0 : Fin 1)) let u := f (Sum.inr (0 : Fin 3)) let v := f (Sum.inr (1 : Fin 3)) let w := f (Sum.inr (2 : Fin 3)) have huv : u ≠ v := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv have huw : u ≠ w := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv have hvw : v ≠ w := by intro hh have hi := f.injective hh have hv := congrArg (fun z : Fin 1 ⊕ Fin 3 => match z with | Sum.inl _ => 99 | Sum.inr k => k.val) hi norm_num at hv refine ⟨c,u,v,w, ⟨?_,?_,?_⟩, ⟨huv,huw,hvw⟩, ⟨?_,?_,?_⟩⟩ all_goals dsimp only [c, u, v, w] all_goals rw [f.map_rel_iff] all_goals simp [completeBipartiteGraph]/-- Graphs satisfying the weighted hard-core closed-neighborhood variance bound for all positive activities and nonnegative weights are claw-free. -/theorem op_1355_claw_free_of_weighted_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbound : ∀ (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v), hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a) : IsClawFree G := by classical by_contra h obtain ⟨c,u,v,w,hadj,hdist,hnon⟩ := op1355_not_claw_free_quadruple_scratch G h let eps : ℝ := 1 / (16 * (2:ℝ)^Fintype.card V) have heps : 0 < eps := by dsimp [eps]; positivity let lam : V → ℝ := fun x => if x=c then 1 else if x=u ∨ x=v ∨ x=w then 10 else eps have hlamdef : ∀ 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) := by intro x; rfl have hpos : ∀ x, 0 < lam x := by intro x dsimp only [lam] split_ifs <;> positivity have hc : lam c = 1 := by simp [lam] have hu : lam u = 10 := by simp [lam, hadj.1.ne'] have hv : lam v = 10 := by simp [lam, hadj.2.1.ne'] have hw : lam w = 10 := by simp [lam, hadj.2.2.ne'] have hZ := op_1355_independent_triple_partition_lower_bound G u v w hdist hnon lam (fun x => le_of_lt (hpos x)) ⟨hu,hv,hw⟩ have hPmax := op_1355_claw_center_partition_upper_bound G c u v w hadj hdist hnon lam hlamdef have hP : 0 ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x := by exact Finset.sum_nonneg fun I _ => Finset.prod_nonneg fun x _ => le_of_lt (hpos x) have hD : 0 < 1 + ∑ x ∈ insert c (G.neighborFinset c), lam x := by have hs : 0 ≤ ∑ x ∈ insert c (G.neighborFinset c), lam x := Finset.sum_nonneg fun x _ => le_of_lt (hpos x) linarith have hDmax : 1 + (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ 33 := by have hN := op_1355_claw_neighborhood_sum_upper_bound G c u v w hadj hdist hnon lam hlamdef linarith have hviol := op_1355_center_violation_of_partition_bounds G lam c hc hZ hP hPmax hD hDmax have ha : ∀ x, 0 ≤ (if x = c then (1:ℝ) else 0) := by intro x; split_ifs <;> norm_num exact (not_lt_of_ge (hbound lam hpos _ ha)) hviol