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

$$\partial h(X,Y)=\sum_{xy\in E,\ x\in X,\ y\in Y}(h(x)-h(y)).$$

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

$$|h(v_n)-h(v_0)|>c^{d(v_n,v_0)}.$$

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

$$A_n=\{a_{n,i}:1\le i\le N_n\},\qquad B_n=\{b_{n,i}:1\le i\le N_n\}.$$

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

$$4p_mp_{m+1}=O(m),$$

so

$$\sum_m \frac1{4p_mp_{m+1}}=\infty.$$

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

$$p_{n+1}x_{n+1}+p_{n-1}x_{n-1} =(p_{n+1}+p_{n-1}+2)x_n .$$

Let

$$h(a_{n,i})=x_n,\qquad h(b_{n,i})=-x_n.$$

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

$$N_{n-1}x_{n-1}+N_{n+1}x_{n+1} =(N_{n-1}+N_{n+1}+2)x_n,$$

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

$$N_0N_1(x_0-x_1),$$

while the crossing $B$-edges contribute

$$N_0N_1((-x_0)-(-x_1))=N_0N_1(x_1-x_0),$$

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

Finally, $h$ has subexponential growth. Put

$$s_n=\frac{x_n}{x_{n-1}}-1\ge0 .$$

From the recurrence,

$$s_{n+1} =\frac{p_{n-1}}{p_{n+1}}\frac{s_n}{1+s_n}+\frac2{p_{n+1}}.$$

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

$$L\le \frac{L}{1+L},$$

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

$$\frac{\log x_n}{n} =\frac1n\sum_{k=1}^n \log(1+s_k)\to0.$$

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

$$|h(v)-h(o)|<c^{d(v,o)}.$$

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.