Discrete harmonic function

Builds on Graph Harmonic function Laplacian matrix

Definition

Let $G = (V, E)$ be a graph in which every vertex has finitely many neighbours. Let $c \colon V \times V \to [0, \infty)$ be a symmetric weight with $c(x, y) > 0$ if and only if $\set{x, y} \in E$ , and let $c(x) = \sum_{y} c(x, y)$ . A function $f \colon V \to \R$ is harmonic at a vertex $x$ with $c(x) > 0$ if $f(x) = \frac{1}{c(x)} \sum_{y \in V} c(x, y) f(y),$ or equivalently if $\sum_{y \in V} c(x, y) \big(f(y) - f(x)\big) = 0$ . For $A \subseteq V$ , the function $f$ is harmonic on $A$ if it is harmonic at every vertex of $A$ . With unit weights on all edges, harmonicity at $x$ says that $f(x)$ is the average of $f$ over the neighbours of $x$ .

Remarks

Example: on the graph $\Z$ with edges $\set{n, n + 1}$ and unit weights, $f(n) = 3n + 2$ is harmonic on $\Z$ , since $\tfrac12\big(f(n - 1) + f(n + 1)\big) = \tfrac12(6n + 4) = f(n)$ . Non-example: $g(n) = n^2$ is harmonic at no vertex, since $\tfrac12\big((n - 1)^2 + (n + 1)^2\big) = n^2 + 1$ . The expression $\sum_y c(x, y)(f(y) - f(x))$ is minus the weighted graph Laplacian applied to $f$ at $x$ , so the harmonic functions on $V$ form the kernel of the Laplacian. For the random walk with transition probabilities $p(x, y) = c(x, y)/c(x)$ , the function $f$ is harmonic at $x$ exactly when $f(x)$ is the expected value of $f$ after one step from $x$ . This is the discrete form of the mean value property of a harmonic function.

Tag	`J64R5MR303`
URI	`m2://J64R5MR303`
Kind	definition
Writing	W0 stub
MSC	31C20, 05C81
Defines	Discrete harmonic function
Uses	Graph, Harmonic function, Laplacian matrix

Discrete harmonic function

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here