op_1355_clique_components_variance_ge_bound
For any finite simple graph G on a finite type V with decidable equality whose connected components are all cliques, and for all positive vertex fugacities lam and all nonnegative observable weights a, the weighted hard-core closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam a is at most the weighted hard-core variance hardCoreWeightedVar G lam a.
Statement
theorem op_1355_clique_components_variance_ge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a
- Formalizes
- knowledgebase
- Verified
- 10 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,…
- op_1355_complete_graph_variance_ge_boundOn the complete graph (⊤ : SimpleGraph V) on a finite type V with decidable equality, for all positive vertex fugacities lam and all…
- finite_variance_recurrence_additiveIf partition functions and the first two unnormalized moments satisfy the independent-component recurrences with nonzero denominators, the…
- simple_graph_clique_components_independent_iff_injectiveIn a graph whose connected components are cliques, a set is independent exactly when the component map is injective on it.
- simple_graph_clique_components_closed_neighborhoodIn a graph whose connected components are cliques, a vertex closed neighborhood is its connected-component fiber.
- suppThe support $\mathrm{supp}(v) \subseteq \mathrm{Fin}\,n$ consists of coordinates where either component of $v$ is nonzero; the…
Read back from the Lean
For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, any positive weight function $\lambda : V \to \mathbb{R}$ (i.e., $\lambda(v) > 0$ for all $v \in V$), and any non-negative function $a : V \to \mathbb{R}$ (i.e., $a(v) \ge 0$ for all $v \in V$):
if every connected component of $G$ is a clique (that is, for every connected component $c \in G\text{.ConnectedComponent}$, the vertex set $c\text{.supp}$ induces a clique in $G$),
then the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam a is less than or equal to the variance under the hard-core model hardCoreWeightedVar G lam a.
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 establishes that for any finite graph whose connected components are cliques, the weighted hard-core closed-neighborhood bound is at most the weighted hard-core variance. Because each component is a clique, an independent set contains at most one vertex per component, allowing independent sets and their weight polynomials to be decomposed component by component. This product structure yields step recurrences for the partition function and its first two moments, which via an additive recurrence lemma decompose the total variance into a sum of component variances. Likewise, since the closed neighborhood of any vertex is its entire component, the closed-neighborhood bound also decomposes as a sum of complete-graph bounds over the components. Comparing the two sums term by term using the Cauchy-Schwarz inequality and an algebraic inequality for complete graphs yields the result.
For distinct vertices u and v in a new component c ∉ S, the families of sets obtained by inserting u versus inserting v into independent sets supported on S are disjoint.
Suppose toward a contradiction that some set belongs to both image families, so insert u J = insert v K for J, K ∈ cliqueIndep G S. Then u ∈ insert v K, which means u = v (contradicting u ≠ v) or u ∈ K. But every vertex of K has its component in S, which would imply c ∈ S, contradicting c ∉ S.
uses
Finset.disjoint_left,Finset.mem_insert_selfintro u hu v hv hne simp only [compFiber, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv dsimp [Function.onFun] rw [Finset.disjoint_left] intro I hI simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hI rcases hI with ⟨J, ⟨hJ, -⟩, rfl⟩ intro h_mem simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at h_mem rcases h_mem with ⟨K, ⟨hK, -⟩, heq⟩ have hu_in : u ∈ insert v K := by rw [heq] exact Finset.mem_insert_self u J simp only [Finset.mem_insert] at hu_in rcases hu_in with rfl | huK · exact hne rfl · have hcomp := hK u huK rw [hu] at hcomp exact hc hcomp
For any vertex u in a new component c ∉ S, the insertion map J ↦ insert u J is injective on cliqueIndep G S.
If insert u J = insert u K, then since all vertices of J and K have components in S while u has component c ∉ S, u cannot belong to J or K. Therefore, any element x belongs to J if and only if it belongs to K, which proves J = K.
simp only [compFiber, Finset.mem_filter, Finset.mem_univ, true_and] at hu intro J hJ K hK heq simp only [cliqueIndep, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hJ hK have huJ : u ∉ J := by intro h have := hJ.1 u h rw [hu] at this exact hc this have huK : u ∉ K := by intro h have := hK.1 u h rw [hu] at this exact hc this ext x have hx : x ∈ insert u J ↔ x ∈ insert u K := by rw [heq] simp only [Finset.mem_insert] at hx by_cases hxu : x = u · subst hxu simp [huJ, huK] · simp [hxu] at hx exact hx
Every independent set supported on S ∪ {c} either is supported entirely on S, or is obtained by inserting a unique vertex from c into an independent set supported on S.
Let I be an independent set supported on S ∪ {c}. We case split on whether I contains a vertex in component c. If it contains some u with component c, then because the component map is injective on I, u is the unique such vertex. Removing u leaves an independent set I \ {u} whose vertices all lie in S, so I = insert u (I \ {u}). If I contains no vertex in c, all its vertices already lie in S.
uses
Finset.insert_eraseclassical ext I simp only [cliqueIndep, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨hS, hinj⟩ by_cases he : ∃ u ∈ I, G.connectedComponentMk u = c · obtain ⟨u,huI,huc⟩ := he right refine ⟨u, ?_, I.erase u, ?_, Finset.insert_erase huI⟩ · simp [compFiber, huc] · constructor · intro v hv have hvI := (Finset.mem_erase.mp hv).2 have hm := hS v hvI simp only [Finset.mem_insert] at hm rcases hm with hvc | hvS · have hvu := hinj hvI huI (hvc.trans huc.symm) exact ((Finset.mem_erase.mp hv).1 hvu).elim · exact hvS · intro v hv w hw heq exact hinj (Finset.mem_erase.mp hv).2 (Finset.mem_erase.mp hw).2 heq · left refine ⟨?_, hinj⟩ intro v hv have hm := hS v hv simp only [Finset.mem_insert] at hm rcases hm with hvc | hvS · exact (he ⟨v,hv,hvc⟩).elim · exact hvS
Conversely, any independent set supported on S, and any set formed by inserting a vertex from component c into an independent set supported on S, is an independent set supported on S ∪ {c}.
In the first case, any independent set on S already has all vertices in S ⊆ S ∪ {c}. In the second case, inserting u ∈ c into J ∈ cliqueIndep G S adds a vertex outside S, so u ∉ J; the resulting set insert u J has all vertices in S ∪ {c}, and the component map remains injective because u is the only vertex mapping to c and J has no vertex mapping to c.
uses
Finset.mem_insert_of_mem· rintro (⟨hS, hinj⟩ | ⟨u,hu,J,⟨hJ,hinj⟩,rfl⟩) · refine ⟨?_, hinj⟩ intro v hv exact Finset.mem_insert_of_mem (hS v hv) · have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have huJ : u ∉ J := by intro huJ apply hc simpa [huc] using hJ u huJ refine ⟨?_, ?_⟩ · intro v hv simp only [Finset.mem_insert] at hv rcases hv with rfl | hv · simpa [huc] · exact Finset.mem_insert_of_mem (hJ v hv) · intro v hv w hw heq simp only [Finset.coe_insert, Set.mem_insert_iff] at hv hw rcases hv with rfl | hv <;> rcases hw with rfl | hw · rfl · have : G.connectedComponentMk w ∈ S := hJ w hw rw [← heq, huc] at this exact (hc this).elim · have : G.connectedComponentMk v ∈ S := hJ v hv rw [heq, huc] at this exact (hc this).elim · exact hinj hv hw heq
The family of independent sets supported on S is disjoint from the union of families of sets containing a vertex from component c.
Any set in the latter union contains a vertex u with component c. If it were also supported on S, the component of u would have to belong to S, which contradicts c ∉ S.
uses
Finset.disjoint_left,Finset.mem_insert_selfclassical apply Finset.disjoint_left.mpr intro I hI hnew obtain ⟨u,hu,himg⟩ := Finset.mem_biUnion.mp hnew obtain ⟨J,hJ,hJI⟩ := Finset.mem_image.mp himg subst I have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have hI' := (Finset.mem_filter.mp hI).2.1 u (Finset.mem_insert_self u J) exact hc (huc ▸ hI')
Any sum of a function over independent sets supported on S ∪ {c} splits into the sum over S plus a double sum over u ∈ c and independent sets on S with u inserted.
By the decomposition lemma, cliqueIndep G (insert c S) is the disjoint union of cliqueIndep G S and the union over u ∈ c of the image families. Applying the disjoint union sum formula, the pairwise disjoint union sum formula over u ∈ c, and the image sum formula using injectivity of insertion gives the desired identity.
uses
cliqueIndep_insert_decomposition,Finset.sum_union,cliqueIndep_disjoint_old_new,Finset.sum_biUnion,cliqueIndep_pairwiseDisjoint,Finset.sum_image,cliqueIndep_insert_injOnclassical rw [cliqueIndep_insert_decomposition G c S hc, Finset.sum_union (cliqueIndep_disjoint_old_new G c S hc), Finset.sum_biUnion (cliqueIndep_pairwiseDisjoint G c S hc)] congr 1 apply Finset.sum_congr rfl intro u hu exact Finset.sum_image (cliqueIndep_insert_injOn G c S hc u hu)
A vertex in a component c ∉ S cannot belong to any independent set supported on S.
If u ∈ I where I ∈ cliqueIndep G S, then the component of u would belong to S, which contradicts c ∉ S.
intro hui have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have hS := (Finset.mem_filter.mp hI).2.1 u hui exact hc (huc ▸ hS)
The partition function Z satisfies the step recurrence Z(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * Z(S).
Apply the sum decomposition to the product weight ∏_{v ∈ I} λ(v). For each term with u inserted, the weight factors as λ(u) * ∏_{v ∈ I} λ(v) because u ∉ I. Factoring the sum over u ∈ c out of the inner sum over I and combining with the base term Z(S) yields (1 + ∑_{u ∈ c} λ(u)) * Z(S).
uses
cliqueIndep_sum_insert,Finset.prod_insert,cliqueIndep_freshclassical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, ∏ v ∈ insert u I, lam v) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by rw [Finset.sum_mul] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum] apply Finset.sum_congr rfl intro I hI exact Finset.prod_insert (cliqueIndep_fresh G c S hc u hu I hI) rw [h] ring
The first-moment sum A satisfies the step recurrence A(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * A(S) + (∑_{u ∈ c} λ(u) a(u)) * Z(S).
Applying the sum decomposition to the first-moment terms, the sum ∑_{v ∈ insert u I} a(v) splits into a(u) + ∑_{v ∈ I} a(v) since u ∉ I. Distributing the product weight and regrouping sums yields (1 + ∑ λ(u)) * A(S) from the ∑_{v ∈ I} a(v) part, and (∑ λ(u) a(u)) * Z(S) from the a(u) part.
uses
cliqueIndep_sum_insert,Finset.prod_insert,Finset.sum_insert,cliqueIndep_freshclassical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, (∏ v ∈ insert u I, lam v) * ∑ v ∈ insert u I, a v) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by rw [Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro I hI have hf := cliqueIndep_fresh G c S hc u hu I hI rw [Finset.prod_insert hf, Finset.sum_insert hf] ring rw [h] ring
The second-moment sum B satisfies the step recurrence B(S ∪ {c}) = (1 + ∑_{u ∈ c} λ(u)) * B(S) + 2 * (∑_{u ∈ c} λ(u) a(u)) * A(S) + (∑_{u ∈ c} λ(u) a(u)^2) * Z(S).
Expanding the square (a(u) + ∑_{v ∈ I} a(v))^2 into (∑ a(v))^2 + 2 a(u) ∑ a(v) + a(u)^2 and applying the sum decomposition produces three groups of terms corresponding to B(S), A(S), and Z(S) with the stated coefficients.
uses
cliqueIndep_sum_insert,Finset.prod_insert,Finset.sum_insert,cliqueIndep_freshclassical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, (∏ v ∈ insert u I, lam v) * (∑ v ∈ insert u I, a v)^2) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) + 2 * (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by have htwo : 2 * (∑ u ∈ compFiber G c, lam u * a u) = ∑ u ∈ compFiber G c, 2 * (lam u * a u) := by rw [Finset.mul_sum] rw [htwo, Finset.sum_mul, Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro I hI have hf := cliqueIndep_fresh G c S hc u hu I hI rw [Finset.prod_insert hf, Finset.sum_insert hf] ring rw [h] ring
The collection of independent sets supported on the empty set of components consists solely of the empty set.
Any set whose vertices have components in ∅ must be empty, and the empty set vacuously satisfies the injectivity and membership requirements.
uses
Finset.notMem_emptyext I simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] constructor · rintro ⟨h, -⟩ ext x simp only [Finset.notMem_empty, iff_false] exact fun hx => Finset.notMem_empty _ (h x hx) · rintro rfl refine ⟨by simp, by simp [Set.InjOn]⟩
When every connected component of G is a clique, cliqueIndep G Finset.univ equals the set of all independent sets of G.
In a disjoint union of cliques, a subset of vertices is independent if and only if it contains at most one vertex from each component, which is precisely the injectivity of the component projection on that subset.
uses
simple_graph_clique_components_independent_iff_injectiveext I simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and] rw [simple_graph_clique_components_independent_iff_injective G hclique] simp
The partition function Z(S) is strictly positive for positive vertex fugacities λ > 0.
The empty set belongs to cliqueIndep G S and has weight 1. Since all weights are non-negative, the total sum is at least 1, hence strictly positive.
uses
zero_lt_one,Finset.single_le_sumunfold cliqueZ refine lt_of_lt_of_le zero_lt_one ?_ have h_empty : (∏ v ∈ (∅ : Finset V), lam v) = 1 := Finset.prod_empty rw [← h_empty] have hem : (∅ : Finset V) ∈ cliqueIndep G S := by simp [cliqueIndep, Set.InjOn] exact Finset.single_le_sum (f := fun I : Finset V => ∏ v ∈ I, lam v) (fun I _ => Finset.prod_nonneg fun v _ => le_of_lt (hlam v)) hem
The weighted closed-neighborhood bound splits into a sum over connected components.
In a graph whose components are cliques, the closed neighborhood of any vertex v is the entire connected component containing v. Grouping the sum fiberwise by connected components, the denominator is constant on each component and factors out, giving the componentwise sum.
uses
Finset.sum_fiberwise,Finset.sum_div,simple_graph_clique_components_closed_neighborhoodclassical unfold hardCoreWeightedClosedNeighborhoodBound rw [← Finset.sum_fiberwise Finset.univ G.connectedComponentMk (fun v => (a v ^ 2 * lam v) / (1 + ∑ u ∈ insert v (G.neighborFinset v), lam u)^2)] apply Finset.sum_congr rfl intro c hc rw [Finset.sum_div] apply Finset.sum_congr rfl intro v hv have hvc : G.connectedComponentMk v = c := by simpa [compFiber] using hv rw [simple_graph_clique_components_closed_neighborhood G hclique v, hvc] change (a v^2 * lam v) / (1 + ∑ u ∈ compFiber G c, lam u)^2 = _ ring
The weighted hard-core variance decomposes as a sum of component variances.
By cliqueIndep_univ, the total variance is B(univ)/Z(univ) - (A(univ)/Z(univ))^2. The step recurrences for Z, A, and B match the hypotheses of the general additive variance recurrence theorem finite_variance_recurrence_additive with base values A(∅) = B(∅) = 0 and strictly positive partition function. Applying this recurrence expresses the total variance as the sum over all components of the variance on each component.
uses
cliqueZ_pos,cliqueIndep_empty,finite_variance_recurrence_additive,cliqueIndep_Z_step,cliqueIndep_A_step,cliqueIndep_B_step,cliqueIndep_univclassical have hZ : ∀ S, cliqueZ G lam S ≠ 0 := fun S => ne_of_gt (cliqueZ_pos G lam hlam S) have hs : ∀ c, 1 + (∑ v ∈ compFiber G c, lam v) ≠ 0 := by intro c have h : 0 ≤ ∑ v ∈ compFiber G c, lam v := Finset.sum_nonneg fun v _ => le_of_lt (hlam v) linarith have hb : cliqueA G lam a ∅ = 0 ∧ cliqueB G lam a ∅ = 0 := by simp [cliqueA, cliqueB, cliqueIndep_empty] have hrec := finite_variance_recurrence_additive (cliqueZ G lam) (cliqueA G lam a) (cliqueB G lam a) (fun c => ∑ v ∈ compFiber G c, lam v) (fun c => ∑ v ∈ compFiber G c, lam v * a v) (fun c => ∑ v ∈ compFiber G c, lam v * a v^2) hZ hs hb (fun c S hc => cliqueIndep_Z_step G lam c S hc) (fun c S hc => cliqueIndep_A_step G lam a c S hc) (fun c S hc => cliqueIndep_B_step G lam a c S hc) Finset.univ have hv : hardCoreWeightedVar G lam a = cliqueB G lam a Finset.univ / cliqueZ G lam Finset.univ - (cliqueA G lam a Finset.univ / cliqueZ G lam Finset.univ)^2 := by unfold hardCoreWeightedVar cliqueB cliqueA cliqueZ rw [cliqueIndep_univ G hclique] rw [hv, hrec]
The closed-neighborhood bound is at most the hard-core variance.
Both the closed-neighborhood bound and the variance decompose as sums over the connected components of G. For each component c, with S = ∑ λ(v), M1 = ∑ λ(v) a(v), and M2 = ∑ λ(v) a(v)^2, Cauchy-Schwarz gives M1^2 ≤ S * M2. The complete-graph variance inequality op_1355_complete_graph_div_sq_le_div_sub_div_sq then implies that the component closed-neighborhood bound M2 / (1+S)^2 is at most the component variance M2 / (1+S) - (M1 / (1+S))^2. Summing these inequalities over all components completes the proof.
uses
cliqueBound_eq,cliqueVar_eq_sum,Finset.sum_le_sum,op_1355_complete_graph_div_sq_le_div_sub_div_sq,op_1355_complete_graph_weighted_cauchy_schwarzrw [cliqueBound_eq G hclique lam a, cliqueVar_eq_sum G hclique lam a hlam] apply Finset.sum_le_sum intro c hc apply op_1355_complete_graph_div_sq_le_div_sub_div_sq · exact Finset.sum_nonneg fun v _ => le_of_lt (hlam v) · exact op_1355_complete_graph_weighted_cauchy_schwarz (compFiber G c) lam a fun v _ => le_of_lt (hlam v)
On any finite graph whose connected components are cliques, the weighted closed-neighborhood bound is at most the weighted hard-core variance.
This main theorem directly invokes In703.in703_main.
uses
In703.in703_mainexact In703.in703_main G lam hlam a ha hclique
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_insert_self- An element always belongs to the set obtained by inserting it into any finite set.
Finset.insert_erase- Inserting an element into a finite set after erasing it recovers the original set, provided the element was originally in the set.
Finset.mem_insert_of_mem- Any element of a finite set is also an element of the set obtained by inserting an additional element.
cliqueIndep_insert_decomposition- Independent sets supported on S ∪ {c} partition into those supported on S and those obtained by inserting some vertex u from component c into an independent set supported on S.
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
cliqueIndep_disjoint_old_new- The family of independent sets supported on S is disjoint from the family of sets obtained by inserting a vertex from a component c ∉ S.
Finset.sum_biUnion- The sum of a function over a pairwise disjoint indexed union of finite sets equals the iterated sum over indices and member sets.
cliqueIndep_pairwiseDisjoint- For c ∉ S, inserting distinct vertices from component c into sets of cliqueIndep G S produces disjoint families of sets.
Finset.sum_image- Summing over the image of an injective map on a finite set equals summing the composed function over the domain set.
cliqueIndep_insert_injOn- Inserting a vertex u from a component c ∉ S is an injective map on independent sets supported on S.
cliqueIndep_fresh- A vertex in a component outside S cannot belong to any independent set supported on S.
cliqueIndep_sum_insert- A sum over independent sets on S ∪ {c} equals the sum over S plus the sum over u in component c of sums with u inserted.
Finset.prod_insert- The product of a function over an inserted element and a set equals the value at the element times the product over the set, if the element was not in the set.
Finset.sum_insert- The sum of a function over an inserted element and a set equals the value at the element plus the sum over the set, if the element was not in the set.
Finset.notMem_empty- No element belongs to the empty set.
simple_graph_clique_components_independent_iff_injective- In a graph whose connected components are cliques, a set of vertices is independent if and only if the component map is injective on that set.
zero_lt_one- Zero is strictly less than one.
Finset.single_le_sum- For any non-negative function on a finite set, the value at any single element is at most the sum over the entire set.
Finset.sum_fiberwise- A sum over a finite set equals the sum over the fibers of a function on that set.
Finset.sum_div- Division of a finite sum by a scalar distributes over each term of the sum.
simple_graph_clique_components_closed_neighborhood- In a graph whose components are cliques, the closed neighborhood of any vertex is the entire connected component containing that vertex.
cliqueZ_pos- For strictly positive fugacities, the partition function restricted to any subset of components is strictly positive.
cliqueIndep_empty- The only independent set whose vertices all belong to the empty set of components is the empty set.
finite_variance_recurrence_additive- Given partition functions and moment sums satisfying linear step recurrences with base values zero, the variance of the combined system equals the sum of the individual component variances.
cliqueIndep_Z_step- The partition function multiplies by 1 + ∑ λ(u) over component c when adding component c.
cliqueIndep_A_step- The first-moment sum satisfies the linear step recurrence when adding a new component c.
cliqueIndep_B_step- The second-moment sum satisfies the quadratic step recurrence when adding a new component c.
cliqueIndep_univ- When all components are cliques, independent sets supported on all components are precisely the independent sets of the graph.
cliqueBound_eq- The weighted closed-neighborhood bound equals the sum over components of the complete-graph bound for each component.
cliqueVar_eq_sum- The weighted hard-core variance equals the sum over components of the complete-graph variance for each component.
Finset.sum_le_sum- If one function is pointwise less than or equal to another on a finite set, its sum is at most the other's sum.
op_1355_complete_graph_div_sq_le_div_sub_div_sq- For non-negative S and moments satisfying Cauchy-Schwarz, the complete-graph neighborhood bound is at most the complete-graph variance.
op_1355_complete_graph_weighted_cauchy_schwarz- The Cauchy-Schwarz inequality for weighted sums with non-negative weights.
In703.in703_main- The main variance bound theorem for graphs with clique components, proved in the In703 namespace.
- The recurrence lemma `finite_variance_recurrence_additive` and the complete graph variance bound `op_1355_complete_graph_div_sq_le_div_sub_div_sq` are external lemmas from the knowledge base.
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.
set_option maxHeartbeats 1000000set_option maxRecDepth 10000namespace In703open scoped Classicalvariable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)noncomputable def compFiber (c : G.ConnectedComponent) : Finset V := Finset.univ.filter (fun v => G.connectedComponentMk v = c)noncomputable def cliqueIndep (S : Finset G.ConnectedComponent) : Finset (Finset V) := Finset.univ.filter fun I => (∀ v ∈ I, G.connectedComponentMk v ∈ S) ∧ (I : Set V).InjOn G.connectedComponentMklemma cliqueIndep_pairwiseDisjoint (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : (↑(compFiber G c) : Set V).PairwiseDisjoint (fun u => (cliqueIndep G S).image (insert u)) := by intro u hu v hv hne simp only [compFiber, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hu hv dsimp [Function.onFun] rw [Finset.disjoint_left] intro I hI simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hI rcases hI with ⟨J, ⟨hJ, -⟩, rfl⟩ intro h_mem simp only [cliqueIndep, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at h_mem rcases h_mem with ⟨K, ⟨hK, -⟩, heq⟩ have hu_in : u ∈ insert v K := by rw [heq] exact Finset.mem_insert_self u J simp only [Finset.mem_insert] at hu_in rcases hu_in with rfl | huK · exact hne rfl · have hcomp := hK u huK rw [hu] at hcomp exact hc hcomplemma cliqueIndep_insert_injOn (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) (u : V) (hu : u ∈ compFiber G c) : Set.InjOn (insert u) (cliqueIndep G S : Set (Finset V)) := by simp only [compFiber, Finset.mem_filter, Finset.mem_univ, true_and] at hu intro J hJ K hK heq simp only [cliqueIndep, Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] at hJ hK have huJ : u ∉ J := by intro h have := hJ.1 u h rw [hu] at this exact hc this have huK : u ∉ K := by intro h have := hK.1 u h rw [hu] at this exact hc this ext x have hx : x ∈ insert u J ↔ x ∈ insert u K := by rw [heq] simp only [Finset.mem_insert] at hx by_cases hxu : x = u · subst hxu simp [huJ, huK] · simp [hxu] at hx exact hxlemma cliqueIndep_insert_decomposition (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : cliqueIndep G (insert c S) = cliqueIndep G S ∪ (compFiber G c).biUnion (fun u => (cliqueIndep G S).image (insert u)) := by classical ext I simp only [cliqueIndep, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_biUnion, Finset.mem_image] constructor · rintro ⟨hS, hinj⟩ by_cases he : ∃ u ∈ I, G.connectedComponentMk u = c · obtain ⟨u,huI,huc⟩ := he right refine ⟨u, ?_, I.erase u, ?_, Finset.insert_erase huI⟩ · simp [compFiber, huc] · constructor · intro v hv have hvI := (Finset.mem_erase.mp hv).2 have hm := hS v hvI simp only [Finset.mem_insert] at hm rcases hm with hvc | hvS · have hvu := hinj hvI huI (hvc.trans huc.symm) exact ((Finset.mem_erase.mp hv).1 hvu).elim · exact hvS · intro v hv w hw heq exact hinj (Finset.mem_erase.mp hv).2 (Finset.mem_erase.mp hw).2 heq · left refine ⟨?_, hinj⟩ intro v hv have hm := hS v hv simp only [Finset.mem_insert] at hm rcases hm with hvc | hvS · exact (he ⟨v,hv,hvc⟩).elim · exact hvS · rintro (⟨hS, hinj⟩ | ⟨u,hu,J,⟨hJ,hinj⟩,rfl⟩) · refine ⟨?_, hinj⟩ intro v hv exact Finset.mem_insert_of_mem (hS v hv) · have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have huJ : u ∉ J := by intro huJ apply hc simpa [huc] using hJ u huJ refine ⟨?_, ?_⟩ · intro v hv simp only [Finset.mem_insert] at hv rcases hv with rfl | hv · simpa [huc] · exact Finset.mem_insert_of_mem (hJ v hv) · intro v hv w hw heq simp only [Finset.coe_insert, Set.mem_insert_iff] at hv hw rcases hv with rfl | hv <;> rcases hw with rfl | hw · rfl · have : G.connectedComponentMk w ∈ S := hJ w hw rw [← heq, huc] at this exact (hc this).elim · have : G.connectedComponentMk v ∈ S := hJ v hv rw [heq, huc] at this exact (hc this).elim · exact hinj hv hw heqlemma cliqueIndep_disjoint_old_new (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : Disjoint (cliqueIndep G S) ((compFiber G c).biUnion (fun u => (cliqueIndep G S).image (insert u))) := by classical apply Finset.disjoint_left.mpr intro I hI hnew obtain ⟨u,hu,himg⟩ := Finset.mem_biUnion.mp hnew obtain ⟨J,hJ,hJI⟩ := Finset.mem_image.mp himg subst I have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have hI' := (Finset.mem_filter.mp hI).2.1 u (Finset.mem_insert_self u J) exact hc (huc ▸ hI')lemma cliqueIndep_sum_insert (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) (f : Finset V → ℝ) : (∑ I ∈ cliqueIndep G (insert c S), f I) = (∑ I ∈ cliqueIndep G S, f I) + ∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, f (insert u I) := by classical rw [cliqueIndep_insert_decomposition G c S hc, Finset.sum_union (cliqueIndep_disjoint_old_new G c S hc), Finset.sum_biUnion (cliqueIndep_pairwiseDisjoint G c S hc)] congr 1 apply Finset.sum_congr rfl intro u hu exact Finset.sum_image (cliqueIndep_insert_injOn G c S hc u hu)lemma cliqueIndep_fresh (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) (u : V) (hu : u ∈ compFiber G c) (I : Finset V) (hI : I ∈ cliqueIndep G S) : u ∉ I := by intro hui have huc : G.connectedComponentMk u = c := by simpa [compFiber] using hu have hS := (Finset.mem_filter.mp hI).2.1 u hui exact hc (huc ▸ hS)lemma cliqueIndep_Z_step (lam : V → ℝ) (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : (∑ I ∈ cliqueIndep G (insert c S), ∏ v ∈ I, lam v) = (1 + ∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by classical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, ∏ v ∈ insert u I, lam v) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by rw [Finset.sum_mul] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum] apply Finset.sum_congr rfl intro I hI exact Finset.prod_insert (cliqueIndep_fresh G c S hc u hu I hI) rw [h] ringlemma cliqueIndep_A_step (lam a : V → ℝ) (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : (∑ I ∈ cliqueIndep G (insert c S), (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) = (1 + ∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by classical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, (∏ v ∈ insert u I, lam v) * ∑ v ∈ insert u I, a v) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by rw [Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro I hI have hf := cliqueIndep_fresh G c S hc u hu I hI rw [Finset.prod_insert hf, Finset.sum_insert hf] ring rw [h] ringlemma cliqueIndep_B_step (lam a : V → ℝ) (c : G.ConnectedComponent) (S : Finset G.ConnectedComponent) (hc : c ∉ S) : (∑ I ∈ cliqueIndep G (insert c S), (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) = (1 + ∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) + 2 * (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by classical rw [cliqueIndep_sum_insert G c S hc] have h : (∑ u ∈ compFiber G c, ∑ I ∈ cliqueIndep G S, (∏ v ∈ insert u I, lam v) * (∑ v ∈ insert u I, a v)^2) = (∑ u ∈ compFiber G c, lam u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2) + 2 * (∑ u ∈ compFiber G c, lam u * a u) * (∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a v) + (∑ u ∈ compFiber G c, lam u * a u^2) * (∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam v) := by have htwo : 2 * (∑ u ∈ compFiber G c, lam u * a u) = ∑ u ∈ compFiber G c, 2 * (lam u * a u) := by rw [Finset.mul_sum] rw [htwo, Finset.sum_mul, Finset.sum_mul, Finset.sum_mul, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro u hu rw [Finset.mul_sum, Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib, ← Finset.sum_add_distrib] apply Finset.sum_congr rfl intro I hI have hf := cliqueIndep_fresh G c S hc u hu I hI rw [Finset.prod_insert hf, Finset.sum_insert hf] ring rw [h] ringnoncomputable def cliqueZ (lam : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ := ∑ I ∈ cliqueIndep G S, ∏ v ∈ I, lam vnoncomputable def cliqueA (lam a : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ := ∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * ∑ v ∈ I, a vnoncomputable def cliqueB (lam a : V → ℝ) (S : Finset G.ConnectedComponent) : ℝ := ∑ I ∈ cliqueIndep G S, (∏ v ∈ I, lam v) * (∑ v ∈ I, a v)^2lemma cliqueIndep_empty : cliqueIndep G ∅ = {∅} := by ext I simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_singleton] constructor · rintro ⟨h, -⟩ ext x simp only [Finset.notMem_empty, iff_false] exact fun hx => Finset.notMem_empty _ (h x hx) · rintro rfl refine ⟨by simp, by simp [Set.InjOn]⟩lemma cliqueIndep_univ [DecidableRel G.Adj] (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : cliqueIndep G Finset.univ = ({I | G.IsIndepSet (↑I : Set V)} : Finset (Finset V)) := by ext I simp only [cliqueIndep, Finset.mem_filter, Finset.mem_univ, true_and] rw [simple_graph_clique_components_independent_iff_injective G hclique] simplemma cliqueZ_pos (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (S : Finset G.ConnectedComponent) : 0 < cliqueZ G lam S := by unfold cliqueZ refine lt_of_lt_of_le zero_lt_one ?_ have h_empty : (∏ v ∈ (∅ : Finset V), lam v) = 1 := Finset.prod_empty rw [← h_empty] have hem : (∅ : Finset V) ∈ cliqueIndep G S := by simp [cliqueIndep, Set.InjOn] exact Finset.single_le_sum (f := fun I : Finset V => ∏ v ∈ I, lam v) (fun I _ => Finset.prod_nonneg fun v _ => le_of_lt (hlam v)) hemlemma cliqueBound_eq [DecidableRel G.Adj] (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (lam a : V → ℝ) : hardCoreWeightedClosedNeighborhoodBound G lam a = ∑ c : G.ConnectedComponent, (∑ v ∈ compFiber G c, lam v * a v^2) / (1 + ∑ u ∈ compFiber G c, lam u)^2 := by classical unfold hardCoreWeightedClosedNeighborhoodBound rw [← Finset.sum_fiberwise Finset.univ G.connectedComponentMk (fun v => (a v ^ 2 * lam v) / (1 + ∑ u ∈ insert v (G.neighborFinset v), lam u)^2)] apply Finset.sum_congr rfl intro c hc rw [Finset.sum_div] apply Finset.sum_congr rfl intro v hv have hvc : G.connectedComponentMk v = c := by simpa [compFiber] using hv rw [simple_graph_clique_components_closed_neighborhood G hclique v, hvc] change (a v^2 * lam v) / (1 + ∑ u ∈ compFiber G c, lam u)^2 = _ ringlemma cliqueVar_eq_sum [DecidableRel G.Adj] (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) (lam a : V → ℝ) (hlam : ∀ v, 0 < lam v) : hardCoreWeightedVar G lam a = ∑ c : G.ConnectedComponent, ((∑ v ∈ compFiber G c, lam v * a v^2) / (1 + ∑ v ∈ compFiber G c, lam v) - ((∑ v ∈ compFiber G c, lam v * a v) / (1 + ∑ v ∈ compFiber G c, lam v))^2) := by classical have hZ : ∀ S, cliqueZ G lam S ≠ 0 := fun S => ne_of_gt (cliqueZ_pos G lam hlam S) have hs : ∀ c, 1 + (∑ v ∈ compFiber G c, lam v) ≠ 0 := by intro c have h : 0 ≤ ∑ v ∈ compFiber G c, lam v := Finset.sum_nonneg fun v _ => le_of_lt (hlam v) linarith have hb : cliqueA G lam a ∅ = 0 ∧ cliqueB G lam a ∅ = 0 := by simp [cliqueA, cliqueB, cliqueIndep_empty] have hrec := finite_variance_recurrence_additive (cliqueZ G lam) (cliqueA G lam a) (cliqueB G lam a) (fun c => ∑ v ∈ compFiber G c, lam v) (fun c => ∑ v ∈ compFiber G c, lam v * a v) (fun c => ∑ v ∈ compFiber G c, lam v * a v^2) hZ hs hb (fun c S hc => cliqueIndep_Z_step G lam c S hc) (fun c S hc => cliqueIndep_A_step G lam a c S hc) (fun c S hc => cliqueIndep_B_step G lam a c S hc) Finset.univ have hv : hardCoreWeightedVar G lam a = cliqueB G lam a Finset.univ / cliqueZ G lam Finset.univ - (cliqueA G lam a Finset.univ / cliqueZ G lam Finset.univ)^2 := by unfold hardCoreWeightedVar cliqueB cliqueA cliqueZ rw [cliqueIndep_univ G hclique] rw [hv, hrec]theorem in703_main [DecidableRel G.Adj] (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a := by rw [cliqueBound_eq G hclique lam a, cliqueVar_eq_sum G hclique lam a hlam] apply Finset.sum_le_sum intro c hc apply op_1355_complete_graph_div_sq_le_div_sub_div_sq · exact Finset.sum_nonneg fun v _ => le_of_lt (hlam v) · exact op_1355_complete_graph_weighted_cauchy_schwarz (compFiber G c) lam a fun v _ => le_of_lt (hlam v)end In703/-- On any finite graph whose connected components are cliques, the weighted hard-core closed-neighborhood variance bound holds. -/theorem op_1355_clique_components_variance_ge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (hlam : ∀ v, 0 < lam v) (a : V → ℝ) (ha : ∀ v, 0 ≤ a v) (hclique : ∀ c : G.ConnectedComponent, G.IsClique c.supp) : hardCoreWeightedClosedNeighborhoodBound G lam a ≤ hardCoreWeightedVar G lam a := by exact In703.in703_main G lam hlam a ha hclique