graph_idle_measure
def
The lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
Statement
noncomputable def graph_idle_measure {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x : V) : V → ℝ
- Defined in
- arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 2.2 (the measure μ_x^α).
- Verified
- 10 Oct 2026
- Axioms
- none listed
- Used by 23
- lly_five_vertex_pos_of_min_degree_twoEvery connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge.
- 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).
- five_vertex_t_star_wasserstein_leFor the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3,…
- lly_curvature_pos_of_edge_connectivity_geIf a finite connected graph on n vertices has edge-connectivity κ'(G) ≥ 2n/3 − 1, then every edge xy has κ_LLY(x, y) > 0.
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 1.
- graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- lly_five_vertex_t_star_curvatureFor the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.
- graph_idle_measure_eq_mixFor α < 1 and any β, μ_x^β = λ μ_x^α + (1 − λ) δ_x with λ = (1 − β)/(1 − α).
- 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.
- graph_idle_transport_plan_main_marginalsWith β = (1/2)/d_x, γ = (1/2)/d_y and d_x ≤ d_y, A.card ≤ B.card, the main plan has nonnegative entries, row sums μ_x^{1/2} and column…
- 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_idle_wasserstein_lt_one_of_edge_partitionGiven the edge partition of a graph of diameter at most 2 whose minimum degree is at least 2n/3 − 1, the idleness-1/2 measures at the…
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
- graph_lly_curvature_pos_of_wasserstein_lt_oneIf the Wasserstein distance between the lazy random-walk measures μ_x^α and μ_y^α on an edge xy is strictly less than 1 for some α ∈ (0,…
- 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.
- graph_idle_transport_plan_specialIf the edge partition has |A| = |B| ≥ 1, deg x = deg y, |B| = |C|+2 and an A–B edge, then μ_x^{1/2} and μ_y^{1/2} admit a plan of cost at…
Lean source view module on GitHub
/-- The measure `μ_x^α`: `α` at `x`, `(1 - α)/deg x` on each neighbour of `x`, `0` elsewhere. -/ noncomputable def graph_idle_measure {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x : V) : V → ℝ := fun v => if v = x then α else if G.Adj x v then (1 - α) / (G.degree x : ℝ) else 0