graph_idle_measure_nonneg
μ_x^α is nonnegative for 0 ≤ α ≤ 1.
Statement
theorem graph_idle_measure_nonneg {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x v : V) : 0 ≤ graph_idle_measure G α x v
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
- Used by 9
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- graph_ollivier_curvature_div_le_two_div_distIn a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
- five_vertex_min_degree_two_idle_coupling_boundIn any 5-vertex graph with minimum degree at least 2 and adjacent vertices x and y, the idle measures at α = 1/2 satisfy 1 < 2 S0 + m_xy.
The proof, explained
The proof unfolds the definition of graph_idle_measure and splits into the three cases of its piecewise definition: when v = x, when v is a neighbor of x, and when v is neither equal nor adjacent to x. In each case, nonnegativity holds directly from the assumptions on α (0 ≤ α ≤ 1), the nonnegativity of graph degrees, and reflexivity of ≤.
It suffices to verify nonnegativity across the three piecewise cases defining graph_idle_measure.
Unfolding the definition of graph_idle_measure expands the term into nested conditionals: if v = x then α, else if G.Adj x v then (1 - α) / degree(x), else 0. The split_ifs tactic splits the proof into these three branches: v = x, v ≠ x with x adjacent to v, and v ≠ x with x not adjacent to v.
unfold graph_idle_measure split_ifs
When v = x, the measure is α, which is nonnegative.
This follows directly from the theorem's hypothesis hα0, which states 0 ≤ α.
· exact hα0When v ≠ x and x is adjacent to v, the measure is (1 - α) / degree(x), which is nonnegative.
By div_nonneg, a quotient is nonnegative whenever both the numerator and the denominator are nonnegative. The numerator 1 - α is nonnegative by linear arithmetic from the assumption α ≤ 1 (hα1), and the denominator degree(x) is nonnegative because graph degrees are natural numbers (Nat.cast_nonneg).
uses
div_nonneg,Nat.cast_nonneg· exact div_nonneg (by linarith) (Nat.cast_nonneg _)
When v ≠ x and x is not adjacent to v, the measure is 0, which is nonnegative.
The remaining branch evaluates to 0, and 0 ≤ 0 holds reflexively by le_rfl.
uses
le_rfl· exact le_rfl
div_nonneg- If a and b are nonnegative, their quotient a / b is nonnegative.
Nat.cast_nonneg- The coercion of any natural number into an ordered ring or semiring is nonnegative.
le_rfl- Less-than-or-equal is reflexive: a ≤ a for every a.
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.
theorem graph_idle_measure_nonneg {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (x v : V) : 0 ≤ graph_idle_measure G α x v := by unfold graph_idle_measure split_ifs · exact hα0 · exact div_nonneg (by linarith) (Nat.cast_nonneg _) · exact le_rfl