Lipschitz harmonic functions on graphs?

Question

Let $G$ be an (infinite) countable graph of bounded degree with vertex and edge sets $V(g)$ and $E(G)$, respectively. A function $f : V(G) \to \mathbb{R}$ is called harmonic if $$ f(v) = \frac{1}{d_v} \sum_{u \in N(v)} f(u) $$ for all $v \in V(G)$, where in the sum $d_v$ is the degree of $v$ and $N(v)$ is the set of all vertices neighboring $v$. More generally, a function $f$ is harmonic relative to some set $S \subset V(G)$ if the above holds for all $v \in V(G) - S$. A function is Lipschitz if there is some fixed constant $C \in \mathbb{R}$ such that $|f(u) - f(v)| < C$ for all $\{u,v\} \in E(G)$.

Do all such graphs admit a nonconstant Lipschitz harmonic functions? More generally, is there always a nonconstant Lipschitz harmonic function relative to some finite subset $S \subset V(G)$?

[Aside: I am not familiar with this sort of subject at all but I am aware of Tao and Shalom's result that such functions do exist on Cayley graphs of finitely generated (with $S$ empty) with finite symmetric generating sets. I included the group theory tag because of this.]

Answer 1

The answer to the first question is negative. Even more, there are infinite connected graphs that do not admit non-constant harmonic functions. The 1-way infinite path is an example. A more interesting example is the 1-way infinite ladder (see figure). This graph does admit non-constant harmonic functions, but it is possible to show that their values have to grow exponentially in the distance to a fixed vertex.

Finding conditions on the graph that would imply the existence of Lipschitz harmonic functions is an interesting question. This question has been raised in the last paragraph of Benjamini's lecture notes "Coarse Geometry and Randomness". (The author attributes it to Uri Bader.)

(It is stated there that every transient graph admits a non-constant Lipschitz harmonic function, but I believe I have a counterexample, which is rather complicated to detail here)

It would be interesting to extend the result of Tao & Yahuda to vertex-transitive locally finite graphs.

---

For the second question, if you allow harmonicity to fail even at a single vertex o, then

Theorem 1: Every connected, infinite, locally finite graph has a Lipschitz harmonic function relative to $S=\{o\}$.

To prove this, and the claims I made above, it is convenient to use the well-known relationship between harmonic functions and electrical currents. The bottomline is that every harmonic function $h$ gives rise to a flow, with the flow along a directed edge $e=uv$ equalling $h(v)-h(u)$. Harmonicity of $h$ at a vertex $u$ is equivalent with preservation of current at $u$ (Kirchhof's node law). We can conversely define $h$ (up to an additive constant) from a flow $i$ iff $i$ satisfies Kirchhof's cycle law, which says that $i$ adds up to 0 along any directed cycle. See e.g. Lovasz's "Random Walks on Graphs: A Survey" for details.

Using this connection to electrical currents, Theorem 1 can be proved as follows:

Proof: Let $B_n, n\in \mathbb{N}$ denote the set of vertices at distance exactly $n$ from $o$. For every $n$, let $i_n$ denote the electrical current of intensity 1 from $o$ to $B_n$. Note that $i_n$ takes values in the interval $[0,1]$, because no edge in an electrical network carries more current than the total coming out of the source. It follows that the sequence $i_n, n\in \mathbb{N}$ has an accumulation point $i$. It is straightforward to check that

1. $i$ takes values in the interval $[0,1]$
2. $i$ satisfies Kirchhof's node law at every vertex except $o$
3. $i$ satisfies Kirchhof's cycle law.

Thus $i$ induces a function $h$ on the vertices (Set $h(o)=0$, set $h(u)=h(o)+i(uo)$ for each neighbour $u$ of $o$, and so on) which is harmonic relative to $o$. It follows from 1) that $h$ is Lipschitz.