4
$\begingroup$

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 the 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$).

$\endgroup$
7
  • 1
    $\begingroup$ In general, the (unique) harmonic function $f$ is given by $f(x)=\mathbb{E}f_0(X_n)$, where $X_i$ is a random walk starting at $x$ and $X_n$ is the first vertex on the boundary hit by the walk. So if you allow general $p_{ij}$, you can have a single "super fast" path (say, with $p$ along the path equal $1-\epsilon$) to the boundary and other paths going through a region of uniform edge probabilities. If a vertex $v$ is adjacent to that "fast" path, a walk starting there may hit the boundary faster than starting from a nonadjacent vertex $w$, even if $w$ is closer to the boundary. $\endgroup$ Dec 12, 2010 at 13:48
  • $\begingroup$ It is by no means clear to me that in your example, even if the network is uniform, you have the desired property: when you pass to the limit as $N\to\infty$, you get the usual Laplace equation inside with the Neumann boundary condition on two sides of the unit triangle $x,y>0,x+y<1$, which $1-x-y$ (the only suitable harmonic function that would depend on $x+y$ only) does not satisfy. Did you try numeric experiments with $n>10$? $\endgroup$
    – fedja
    Dec 12, 2010 at 16:04
  • $\begingroup$ Indeed. It is not that clear that this will be the case in my example. You can say that I relayed on "physical intuition" when I gave this remark (conservation of the total current that flow perpendicular to $x+y=const.$ cuts) .Yet, I did try both numerics and analytical approach (I was able to get the exact expression for $f$ for this problem) - the property that interests me holds for any size of the $\Delta_N$ (in case of uniform network). As for "continuum limit" - it is singular since you put the "current source" exactly into one of the edges of a unit triangle. $\endgroup$ Dec 12, 2010 at 17:32
  • $\begingroup$ Yes, we have a singular source ($V^+$), so my intuition would be that we get essentially the renormalized function $-\log|z|$ in the quarter circle that is transferred to the triangle by the conformal map preserving the corners for large $n$. But $x+y=C$ do not correspond to $|z|=c'$ under such map. I'll try to run a few simulations myself a bit later. You may be right, but then it goes against everything I know of the Laplace equation... Note that on the boundary we have 3 adjacent nodes, not 4, and 2 of them go "away". $\endgroup$
    – fedja
    Dec 12, 2010 at 23:04
  • $\begingroup$ Thanks for your comment. When I take a limit $N\rightarrow \infty $ ( while keeping source of unit current at $(0,0)$) potential at $(0,0)$ (or resistance of the network) has a logarithmic asymptotic (when I keep $f|_{V_1^-}=0$). About level sets $x+y=const.$ - for $N\geq 4$ they do not correspond to constant potential: only for $x+y=0$, $x+y=1$ and $x+y=N-1$ you have fixed value of $f$. $\endgroup$ Dec 12, 2010 at 23:33

0

Your Answer

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