Discrete harmonic function on a planar graph

Question

Given a graph $G$ we will call a function $f:V(G)\to \mathbb{R}$ discrete harmonic if for all $v\in V(G)$ , the value of $f(v)$ is equal to the average of the values of $f$ at all the neighbors of $v$. This is equivalent to saying the discrete Laplacian vanishes.

Discrete harmonic functions are sometimes used to approximate harmonic functions and most of the time they have similar properties. For the plane we have Liouville's theorem which says that a bounded harmonic function has to be constant. If we take a discrete harmonic function on $\mathbb{Z}^2$ it satisfies the same property (either constant or unbounded).

Now my question is: If we take a planar graph $G$ so that every point in the plane is contained in an edge of $G$ or is inside a face of $G$ that has less than $n\in \mathbb{N}$ edges, does a discrete harmonic function necessarily have to be either constant or unbounded?

I know the answer is positive if $G$ is $\mathbb{Z}^2$, the hexagonal lattice and triangular lattice, I suspect the answer to my question is positive, but I have no idea how to prove it.

Edited the condition of the graph to "contain enough cycles". (So trees are ruled out for example)

Answer 1

The answer is no.

I first describe the graph $G$. Let $N_i$ be a sequence of positive integers; we will choose $N_i$ later. Let $T$ be an infinite tree which has one root vertex, the root has $N_1$ children; the children of that root have $N_2$ children, those children have $N_3$ children and so forth. Let $V_0$ be the set containing the root, $V_1$ be the set of children of the root, $V_2$ the children of the elements of $V_1$, and so forth. To form our graph, take $T$ and add a sequence of cycles, one going through the vertices of $V_1$, one through $V_2$ and so forth. (In the way which is compatible with the obvious planar embedding of $T$.)

Every face of $G$ is either a triangle or a quadrilateral.

We will build a harmonic function $f$ on $G$ as follows: On the root, $f$ will be $0$. On $V_1$, we choose $f$ to be nonzero, but average to $0$. On $V_i$, for $i \geq 2$, we compute $f$ inductively by the condition that, for every $u \in V_{i-1}$, the function $f$ is constant on the children of $u$. Of course, we may or may not get a bounded function depending on how we choose the $N_i$. I will now show that we can choose the $N_i$ so that $f$ is bounded. Or, rather, I will claim it and leave the details as an exercise for you.

Let $a_i$ be a decreasing sequence of positive reals, approaching zero. Take $N_i = 6/(a_{i+1} - a_i)$. Exercise: If $f$ on $V_1$ is taken between $-1+a_1$ and $1-a_1$, then $f$ on $V_i$ will lie between $-1+a_i$ and $1-a_i$. In particular, $f$ will be bounded between $-1$ and $1$ everywhere.

Answer 2

Benjamini and Schramm proved that an infinite, bounded degree, planar graph is non-Liouville if and only if it is transient.

Answer 3

For general complete Riemannian manifolds other than the plane, one need some curvature conditions to guarantee the Liouville's theorem. Similarly, for planar graphs, one need some curvature constraints too. See Geometric analysis aspects of infinite semiplanar graphs with nonnegative curvature Hua, Jost, Liu, http://arxiv.org/abs/1107.2826, where the Liouville's theorem and recurrency of random walks are proved on semiplanar graphs (graphs that could be embedded in a 2-manifold, including planar graphs) with nonnegative Higuchi's curvature, a analogue of the sectional curvature (or Ricci curvature) of a 2-manifold.

Answer 4

For instance, any regular $H_{p,q}$ tessellation of the hyperbolic space $\mathbb{H}_2$ with $\frac{1}{q}+\frac{1}{q}<4$ does the job.

Answer 5

another way to ensure that bounded harmonic functions on a graph $G$ are constant is to consider a random walks $X_n$: since $M_n = V(X_n)$ is a bounded martingale, it converges almost surely. Hence, if one can prove that random walks on $G$ are recurrent, this shows that $V$ has to be constant. Of course, this can be difficult to show that random walks on $G$ are recurrent.