MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
Maybe I am misunderstanding the question, but you can write down (many) nonconstant bounded harmonic functions on a trivalent regular tree. – moonface Dec 15 '09 at 16:37
I think the poster wants to require that there is a constant n such that any face of R^2 \setminus G has at most n edges. The complement of the regular trivalent tree is a single face with infinitely many edges. – David Speyer Dec 15 '09 at 16:44
@moonface: You're right, that's true for most trees. I meant a different restriction on the graph, so I edited the above. @David: Yep :), I should have been more precise. – Gjergji Zaimi Dec 15 '09 at 16:53
up vote 14 down vote accepted

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.

share|cite|improve this answer
You can probably also take any periodic tiling of the hyperbolic plane. And probably the right condition on $G$ is that it be amenable. – Greg Kuperberg Dec 15 '09 at 17:17
Is there a definition of amenable for general graphs? I only knew it for Cayley graphs. – David Speyer Dec 15 '09 at 17:39
Yes: No infinite Ponzi scheme. It makes sense for general metric spaces too, although that's not really different. Also, in this case amenability could be stronger than strictly necessary. The discrete Laplacian is a model of random walks, and you could possibly have a non-amenable structure that is only noticed by non-random walks. – Greg Kuperberg Dec 15 '09 at 18:19
It quickly leaps out that all of these counterexamples are infinite Ponzi schemes, so amenability is a natural condition. It is considered for instance here – Greg Kuperberg Dec 15 '09 at 20:29
I also stumbled upon where they also state that nonamenability is "sort of" necessary in the analogous problem of existence of non-constant harmonic functions. – Gjergji Zaimi Dec 15 '09 at 21:56

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

share|cite|improve this answer

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,, 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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.