discrete harmonic extension (an exercise of Grimmett's "probability on graphs")

257 Views Asked by At

I'm struggling with exercise 1.3 in Grimmett's book "probability on graphs". Take $G = (V,E)$ a finite connected graph with given positive conductances $(w_e)_{e \in E}$, and let $(x_v)_{v \in V}$ be a family of numbers with total sum equal to 0. We add to the graph $G$ an extra vertex $\infty$, and each site of $V$ is joined to this new vertex $\infty$ by an edge $\langle v,\infty \rangle$ (the exercise does not make it very clear, but I understand that the conductances of these edges are of our choosing). The question is to show that there exists a current $i$ (i.e. a flow satisfying Kirchoff's laws) on the extended graph, such that the current crossing the edge $\langle v,\infty \rangle$ is $x_v$.

I attempted a few things, but so far unsuccessfully. In particular, the exercise is supposed to be the continuation of another exercise where currents are described in terms of the counting of spanning trees. Let me recall this here. For every edge $\langle a, b \rangle$, let us say that a spanning tree $T$ satisfies the property $\Pi(s,a,b,t)$ if the unique path in $T$ going from $s$ to $t$ crosses the edge $\langle a, b \rangle$ in the direction from $a$ to $b$. Let $$ N^*(T) = \prod_{e \in T} w_e, $$ $$ N^*(s,a,b,t) = \sum_{T \text{ satisfies } \Pi(s,a,b,t)} N^*(T), $$ and $$ N^* = \sum_T N^*(T), $$ where the last two sums are for spanning trees $T$. Then the unit current $i$ between $s$ and $t$ is such that $$ i_{a,b} = \frac{1}{N^*} \big(N^*(s,a,b,t) - N^*(s,b,a,t) \big). $$ This may be interesting for the problem I mentionned before, because we can decompose the set of spanning trees as follows. Either the spanning tree goes across only one edge of the type $\langle v,\infty \rangle$, in which case it does not contribute to the computation of the current across that edge ; else, two edges are crossed. In this case, we can decompose the part of the spanning tree within the original graph $G$ in two parts, forming a ``bush'' in Grimmett's terminology, i.e. a spanning set that has two connected components. I tried to use this decomposition to relate to currents in the original graph, but failed so far. Any help would be appreciated...

By the way, Grimmett's book is available for download on his web site, here.