hard_core_weighted_closed_neighborhood_bound_ones
When the observable weights a are identically 1, the weighted closed-neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) is equal to the unweighted closed-neighborhood bound hardCoreClosedNeighborhoodBound G lam.
Statement
theorem hard_core_weighted_closed_neighborhood_bound_ones {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) : hardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) = hardCoreClosedNeighborhoodBound G lam
- Source
- folklore
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- hardCoreWeightedClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a,…
- hardCoreClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality and positive vertex fugacities lam, the closed-neighborhood variance lower…
- 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…
Read back from the Lean
For every finite type $V$ with decidable equality, every simple graph $G$ on $V$ with decidable adjacency, and every function $\lambda : V \to \mathbb{R}$, the weighted closed neighborhood bound hardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) evaluated with weights identically equal to $1$ is equal to the unweighted closed neighborhood bound hardCoreClosedNeighborhoodBound G lam.
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 setting the observable weights to identically 1 in the weighted closed-neighborhood bound recovers the unweighted closed-neighborhood bound. Unfolding both definitions reveals that the weighted sum differs only by a factor of $1^2$ multiplying the vertex activity in the numerator of each term. Algebraic simplification reduces $1^2 \cdot \lambda(v)$ to $\lambda(v)$, making both sides identical.
hardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) = hardCoreClosedNeighborhoodBound G lam automation
Unfolding the definitions of the weighted and unweighted closed-neighborhood bounds (`hardCoreWeightedClosedNeighborhoodBound` and `hardCoreClosedNeighborhoodBound`), each vertex v contributes $(1^2 \cdot \lambda(v)) / (1 + \sum_{u \in N[v]} \lambda(u))^2$ to the weighted sum and $\lambda(v) / (1 + \sum_{u \in N[v]} \lambda(u))^2$ to the unweighted sum. Simplification evaluates $1^2 \cdot \lambda(v) = \lambda(v)$, rendering both sides identical and closing the goal by reflexivity.
uses
hard_core_weighted_var_oneshardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) = hardCoreClosedNeighborhoodBound G lam := by first | exact hard_core_weighted_var_ones | (apply hard_core_weighted_var_ones <;> assumption) | (apply hard_core_weighted_var_ones <;> simp_all) | simpa using hard_core_weighted_var_ones | (simp only [hardCoreClosedNeighborhoodBound, hardCoreWeightedClosedNeighborhoodBound] at *; first | exact hard_core_weighted_var_ones | (apply hard_core_weighted_var_ones <;> assumption) | (apply hard_core_weighted_var_ones <;> simp_all) | simpa using hard_core_weighted_var_ones)
hard_core_weighted_var_ones- For any graph G and vertex activities lam, the weighted variance bound with observable weights identically 1 equals the unweighted variance bound hardCoreVarSize G lam.
- The source script uses a fallback search (`first | ...`) passing `hard_core_weighted_var_ones` to `simpa using ...`. However, that lemma concerns variance bounds (`hardCoreWeightedVar` and `hardCoreVarSize`) rather than closed-neighborhood bounds, and is not actually used; `simpa` closes the goal entirely by algebraic simplification ($1^2 \cdot \lambda = \lambda$) and reflexivity.
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.
/-- Specializing the weighted closed-neighborhood bound to constant observable weight 1 recovers the unweighted bound. -/theorem hard_core_weighted_closed_neighborhood_bound_ones {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) : hardCoreWeightedClosedNeighborhoodBound G lam (fun _ => 1) = hardCoreClosedNeighborhoodBound G lam := by first | exact hard_core_weighted_var_ones | (apply hard_core_weighted_var_ones <;> assumption) | (apply hard_core_weighted_var_ones <;> simp_all) | simpa using hard_core_weighted_var_ones | (simp only [hardCoreClosedNeighborhoodBound, hardCoreWeightedClosedNeighborhoodBound] at *; first | exact hard_core_weighted_var_ones | (apply hard_core_weighted_var_ones <;> assumption) | (apply hard_core_weighted_var_ones <;> simp_all) | simpa using hard_core_weighted_var_ones)