Skip to main content
1 of 2

Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic functions. Therefore, I apologize for the terminology that I use - it might be not consistent with standard one used in those fields.

Terminology:

Consider a finite, connected graph $G=(V,E)$. For each edge $(i,j)\in E$ there is a "weight" $p_{ij}>0$. In each point $i\in V $ weights satisfy a normalization condition: $\sum_{j:(i,j)\in E} p_{ij}=1$ (note that in general $p_{ij}\neq p_{ji}$). Separate certain set of points $V_1\subset V$ . I shall call $V_1$ the boundary of graph $G$. Now, a function $f\colon V\rightarrow\mathbb{R}$ is harmonic on $G$ (with the boundary $V_1$) if $\ \forall{i\in V\setminus V_1}\ \ f(i)=\sum_{j:(i,j)\in E} p_{ij}f(j)$ and it satisfies certain boundary conditions on $V_1$.

Question:

Consider a source - sink problem. That is: $V_1=V_1^+ \cup V_1^-$ ($V_1^+\cap V_1^-=\emptyset$). Let $f$ be a harmonic function such that $f|_{V_1^+}=1$ and $f|_{V_1^-}=0$. Assume that there are two points $i,j\in V\setminus V_1$ such that $(i,j)\in E$ and $dist(i,V_1^+) < dist(j,V_1^+)$. Here $dist(i,j)$ is a "shortest path metric" on $G$ (without taking weights under account). Under what conditions we will have $f(i)>f(j)$? Physically, if that property is fulfilled it means that "the current flows locally from the direction of the source to the direction of the sink" (one can think that $f$ is an electric potential).

Remark:

Above mentioned property of $f$ is clearly true if we know that properties $(i,j)\in E$, $dist(i,V_1^{+}) < dist(j,V_1^{+})$ imply that there are no other $p\neq i$ for which $dist(p,V_1^+)=dist(i,V_1^+)$ and $(j,p)\in E$. Moreover, it is easy to construct an example showing that if we do not have this property there can be $f(i) < f(j)$ even when $dist(i,V_1^+) < dist(j,V_1^+)$. Yet, this kind of requirement seems to be too restrictive for me. The original problem that led me to above-stated question is a problem of flow trough a sub-lattice of $\mathbb{Z}^2$ defined as $\Delta_N = \lgroup (x,y)\in\mathbb{Z}^2| x+y\leq N-1, x\geq 0,\ y\geq 0 \rgroup$ ($V=\Delta_N$, $E$ is defined in a natural way) with $V_1^+=(0,0)$, $V_1^-=\lgroup (x,y)\in\Delta_N| x+y= N-1 \rgroup$. Clearly, if the network is uniform ($p_{ij}=\frac{1}{ Card \lgroup j|(i,j)\in E\rgroup} $ ) we will have property desired by me. The question is whether it will be fulfilled when I allow general $p_{ij}$ (note however that I exclude the possibility that $p_{ij}=0$ for $(i,j)\in E$).