A study of 2-ended graphs via harmonic functions

NEW

Problem: Reconstructed conjecture: in the category of connected, simple, locally finite unit-conductance graphs, let $G=(V,E)$ be recurrent and quasi-isometric to $\mathbb R$. For a harmonic $h:V\to\mathbb R$, write

If some finite cut $E(X,Y)$ separating the two ends satisfies $\partial h(X,Y)=0$, then $h$ is constant or has exponential growth along vertices escaping to infinity: there are $c>1$ and $v_n$ with $d(v_n,v_0)\to\infty$ and

The escape condition is the standard non-vacuous meaning of “grows exponentially”; without it the wording is ambiguous.

Result: The conjecture is false. The obstruction is unbounded local degree.

Let $p_n=\lceil \sqrt{n+1}\rceil$ for $n\ge0$, and put $N_n=p_{|n|}$. For each $n\in\mathbb Z$, take two sets

Join every vertex of $A_n$ to every vertex of $A_{n+1}$, every vertex of $B_n$ to every vertex of $B_{n+1}$, and add matching edges $a_{n,i}b_{n,i}$. This graph is locally finite.

Mapping each vertex in layer $n$ to $n\in\mathbb Z$ is a quasi-isometry: graph distance changes layer number by at most one, and any two vertices in layers $m,n$ are at distance at most $|m-n|+3$. Hence $G\simeq_{\mathrm{QI}}\mathbb R$.

It is recurrent by Nash-Williams. The cutset separating $\{|k|\le m\}$ from infinity has size

so

Now define $x_0=1$, $x_1=(1+1/p_1)x_0$, $x_{-n}=x_n$, and for $n\ge1$

Let

For $a_{n,i}$, the harmonicity equation is exactly

and the equation for $b_{n,i}$ is its negative. Thus $h$ is harmonic and nonconstant.

For the cut $X=\bigcup_{n\le0}(A_n\cup B_n)$, $Y=V\setminus X$, the crossing $A$-edges contribute

while the crossing $B$-edges contribute

so $\partial h(X,Y)=0$.

Finally, $h$ has subexponential growth. Put

From the recurrence,

Since $p_n\to\infty$, taking limsup gives

so $L=0$. Hence $s_n\to0$, and therefore

Thus $x_n=e^{o(n)}$. Since distance from a fixed base vertex is comparable to $|n|$, for every $c>1$ all sufficiently distant vertices satisfy

So $h$ is nonconstant, satisfies the zero-flux condition, but does not grow exponentially.

Citation: Counterexample above. Nash-Williams recurrence criterion: C. St. J. A. Nash-Williams, “Random walk and electric currents in networks,” Proc. Cambridge Philos. Soc. 55 (1959), or Lyons–Peres, Probability on Trees and Networks, Cambridge Univ. Press, Ch. 2.