The truncated distance kernel

For a graph H, a ratio q, and a radius R, the kernel row of a vertex v assigns q ^ dist(v, z) to every vertex z within extended distance R of v and 0 to every other vertex. Unreachable vertices have extended distance ⊤ and therefore receive 0. The unit kernel row divides by the Euclidean norm of the row, which is at least one because the row has value q ^ 0 = 1 at v.

Spheres and balls are measured by extended distance, so an unreachable vertex lies in no sphere and no ball.

noncomputable def Algebraic.Cutwidth.Gaussian.kernel {W : Type} (H : SimpleGraph W) (q : ℝ) (R : ℕ) (v z : W) : ℝ

The truncated distance kernel: q ^ dist(v, z) when the extended distance from v to z is at most R, and 0 otherwise.

Equations

• Algebraic.Cutwidth.Gaussian.kernel H q R v z = if H.edist v z ≤ ↑R then q ^ H.dist v z else 0

noncomputable def Algebraic.Cutwidth.Gaussian.sphere {W : Type} (H : SimpleGraph W) [Fintype W] (v : W) (d : ℕ) : Finset W

The vertices at extended distance exactly d from v.

Equations

• Algebraic.Cutwidth.Gaussian.sphere H v d = {z : W | H.edist v z = ↑d}

noncomputable def Algebraic.Cutwidth.Gaussian.ball {W : Type} (H : SimpleGraph W) [Fintype W] (v : W) (r : ℕ) : Finset W

The vertices at extended distance at most r from v.

Equations

• Algebraic.Cutwidth.Gaussian.ball H v r = {z : W | H.edist v z ≤ ↑r}

noncomputable def Algebraic.Cutwidth.Gaussian.unitKernel {W : Type} (H : SimpleGraph W) [Fintype W] (q : ℝ) (R : ℕ) (v z : W) : ℝ

The kernel row of v divided by its Euclidean norm.

Equations

• Algebraic.Cutwidth.Gaussian.unitKernel H q R v z = Algebraic.Cutwidth.Gaussian.kernel H q R v z / √(∑ y : W, Algebraic.Cutwidth.Gaussian.kernel H q R v y ^ 2)