AFTD Auto-Formalizing Theoretical Domains

hard_core_weighted_closed_neighborhood_bound_ones

theoremverified

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

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.

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

    line 4

    uses hard_core_weighted_var_ones

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

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

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