AFTD Auto-Formalizing Theoretical Domains

hardCoreVarSize

def

Given a finite graph G on a type V with decidable equality and vertex fugacities lam, the variance of the independent set size hardCoreVarSize G lam is defined as the second moment minus the square of the first moment of the cardinality |I| of an independent set I chosen with probability proportional to ∏_{v ∈ I} lam v.

Statement

noncomputable def hardCoreVarSize {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) : ℝ
Defined in
OP-1340; Scott-Sokal 2005 (arXiv:cond-mat/0309352); knowledgebase
Verified
09 Nov 2026
Axioms
none listed
Used by 3
  • petersen_hard_core_var_per_vertex_eq_polyFor every real activity x, the per-vertex hard-core variance of the Petersen graph hardCoreVarSize petersen_graph (fun _ => x) / 10 equals…
  • hard_core_weighted_var_onesWhen the observable weights a are identically 1, the weighted hard-core variance hardCoreWeightedVar G lam (fun _ => 1) is equal to the…
  • op_1340_empty_graph_equalityOn the empty (edgeless) graph (⊥ : SimpleGraph V) on a finite type V with decidable equality and positive vertex fugacities lam,…

Read back from the Lean

Given a finite type $V$ with decidable equality, a simple graph $G$ on $V$ with decidable adjacency, and a vertex-weight (fugacity) function $\lambda : V \to \mathbb{R}$, hardCoreVarSize G lam is defined as the variance of the size of an independent set under the hard-core model with activities $\lambda$: 1. Let $\mathcal{I}$ be the collection of all subsets $I \subseteq V$ that are independent sets in $G$ (i.e., no two vertices in $I$ are adjacent in $G$). 2. Let $Z = \sum_{I \in \mathcal{I}} \prod_{v \in I} \lambda(v)$ be the partition function. 3. Let $E_1 = \frac{1}{Z} \sum_{I \in \mathcal{I}} |I| \prod_{v \in I} \lambda(v)$ (the first moment / expected size). 4. Let $E_2 = \frac{1}{Z} \sum_{I \in \mathcal{I}} |I|^2 \prod_{v \in I} \lambda(v)$ (the second moment of the size). The definition returns $E_2 - E_1^2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The variance of the independent set size |I| in the inhomogeneous hard-core model on G with vertex fugacities lam. -/
noncomputable def hardCoreVarSize {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) : ℝ :=
  let indep := Finset.univ.filter (fun I : Finset V => G.IsIndepSet (I : Set V))
  let Z := ∑ I ∈ indep, ∏ v ∈ I, lam v
  let E1 := (∑ I ∈ indep, (∏ v ∈ I, lam v) * (I.card : ℝ)) / Z
  let E2 := (∑ I ∈ indep, (∏ v ∈ I, lam v) * ((I.card : ℝ) ^ 2)) / Z
  E2 - E1 ^ 2
See it in the graphDiscuss this resultChallenge it