# Reference request: discrete harmonic functions and ends of graphs

Let $G$ be an infinite locally finite connected graph with finitely many ends. A real-valued function $f : G \to \mathbb{R}$ is harmonic if

$$f(v) = \frac{1}{d_v} \sum_{v \sim w} f(w)$$

where $v \sim w$ means that $v, w$ are connected by an edge. Playing around with a few examples leads me to suspect that the dimension of the space of harmonic functions on $G$ is the number of ends. (Heuristic: given a harmonic function, start with a vertex $v$ and move to a neighbor $w$ of $v$ such that $f(w) \ge f(v)$. If $f$ is nonconstant this should give a path converging to an end, and this should be possible for any end. Moreover a harmonic function should be determined by its "values at the ends.") Does anyone know if this is true and, if so, does anyone know of a reference for this fact?

(Tags are because a major application is to Cayley graphs of finitely generated groups and I would be interested in seeing how far one can push this method to prove basic facts about ends of such graphs.)

-
Erm... So how many ends do $\mathbb Z$ and $\mathbb Z^2$ have? (I see two and one, but, maybe, I'm just nearsighted). – fedja Dec 22 '10 at 2:54
@fedja : Being nearsighted helps in recognizing quasi-isometric invariants like the number of ends! – Andy Putman Dec 22 '10 at 3:09
@fedja: oops. Seems I didn't look at enough examples... – Qiaochu Yuan Dec 22 '10 at 3:36
In a paper of Kapovich on Gromov's proof of Stallings' theorem, he proves that a function on the ends of a manifold taking values in {0,1} has a harmonic extension to the manifold front.math.ucdavis.edu/0707.4231. One can probably also prove this for graphs, possibly with some extra conditions on the graph, such as bounded valence. – Ian Agol Dec 22 '10 at 4:57
@Ricky: Are you sure about $\mathbb{Z}^2$? It seems to me that the space of harmonic functions is infinite dimensional. – Kevin Ventullo Dec 22 '10 at 5:30

Life is much more complicated than that. In nice situations (for instance, if your graph is $\delta$-hyperbolic), then you can attach a more refined boundary than just the ends and (if you are lucky) solve the Dirchlet problem. A lot depends on what kinds of regularity conditions you assign to functions on the boundary at infinity.

This is by now a well-established part of geometric group theory. For instance, it plays a key role in Kleiner's recent new proof of Gromov's theorem on groups with polynomial growth. See here.

One textbook reference that covers some of this information is

Woess, W., Random Walks on Infinite Graphs and Groups, Cam- bridge Tracts in Math. 138, Cambridge Univ. Press, 2000

EDIT : By the way, since you are in Cambridge, Curt McMullen at Harvard is a good person to talk to about this kind of stuff. I learned most of what I know about the subject from a course he taught last year.

-
Off topic, but I don't quite understand Andy P's last comment. Is Harvard near Cambridge MA? It certainly isn't near Cambridge, East Anglia... – Yemon Choi Dec 22 '10 at 3:13
Whoops, I forgot that Qiaochu is currently visiting the real Cambridge right now <grin>. Until recently, he was at MIT... – Andy Putman Dec 22 '10 at 3:15
Harvard is in Cambridge, MA. It is actually on the same street as MIT, about a 30 minute walk away, so I've heard people at both refer to the other as "that school down the street". – Noah Stein Dec 22 '10 at 3:27