AFTD Auto-Formalizing Theoretical Domains

op_1355_claw_free_of_weighted_bound

theoremverifiedformalization

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

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.

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

    lines 6–9

      classical
      have hex : SimpleGraph.IsIndContained (completeBipartiteGraph (Fin 1) (Fin 3)) G := by
        simpa [IsClawFree] using h
      obtain ⟨f⟩ := hex
  2. 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.

    lines 10–28

    uses congrArg

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

    lines 29–32

      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]
  4. 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.

    lines 40–42

    uses op1355_not_claw_free_quadruple_scratch

      classical
      by_contra h
      obtain ⟨c,u,v,w,hadj,hdist,hnon⟩ := op1355_not_claw_free_quadruple_scratch G h
  5. 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.

    lines 43–54

      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']
  6. 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.

    lines 55–64

    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_bound

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

    lines 65–67

    uses not_lt_of_ge, op_1355_center_violation_of_partition_bounds

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

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

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