Vietoris–Rips ultrametric condition for Laplacian approximation

Let GG be a finite weighted graph, let dmind_{\min} denote the relevant minimum spectral separation from Theorem 1, and let L1(α)L_1^{(\alpha)} be the perturbation term in the Laplacian decomposition, measured in the Frobenius norm \left\\|L_1^{(\alpha)}\right\\|_F. For a Vietoris–Rips graph at scale ϵ>0\epsilon>0, its clusters are the connected components obtained by eliminating edges longer than ϵ\epsilon.

Vietoris–Rips ultrametric condition. The Vietoris–Rips clusters for some ϵ>0\epsilon>0 realise the sufficient ultrametric condition

\left\\|L_1^{(\alpha)}\right\\|_F<\frac{d_{\min}}{6}

for each cluster, as well as for the inter-cluster graph, and for some α>0\alpha>0.

This condition would allow the perturbation estimate from the preceding theorem to apply locally to the cluster decomposition and to the inter-cluster graph. The source presents the assertion as plausible, but gives no resolution.

Sources & referencesView supporting material

Primary source

Patrick Erik Bradley, “Local ultrametric approximation of graph distance based Laplacian diffusion”, arXiv:2412.20591 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.