15
$\begingroup$

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)

$\endgroup$
3
  • 1
    $\begingroup$ Maybe I am misunderstanding the question, but you can write down (many) nonconstant bounded harmonic functions on a trivalent regular tree. $\endgroup$
    – moonface
    Dec 15, 2009 at 16:37
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 15, 2009 at 16:44
  • $\begingroup$ @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. $\endgroup$ Dec 15, 2009 at 16:53

5 Answers 5

15
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ You can probably also take any periodic tiling of the hyperbolic plane. And probably the right condition on $G$ is that it be amenable. $\endgroup$ Dec 15, 2009 at 17:17
  • 1
    $\begingroup$ Is there a definition of amenable for general graphs? I only knew it for Cayley graphs. $\endgroup$ Dec 15, 2009 at 17:39
  • $\begingroup$ 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. $\endgroup$ Dec 15, 2009 at 18:19
  • 1
    $\begingroup$ 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 arxiv.org/abs/0706.2844 $\endgroup$ Dec 15, 2009 at 20:29
  • 1
    $\begingroup$ I also stumbled upon jstor.org/stable/119840?seq=1 where they also state that nonamenability is "sort of" necessary in the analogous problem of existence of non-constant harmonic functions. $\endgroup$ Dec 15, 2009 at 21:56
9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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