12
$\begingroup$

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that this operation does not disconnect the graph.) Are there any estimates on the resulting current?

In more mathematical terms, write $e=(s,t)$, then define the voltage at a vertex $x$ to be [Edit: Formula incorrect see Ori's comment after Victor's answer] $$ V_x = \mathbb{P}(\textrm{a simple random walk starting at } x \textrm{ hits } s \textrm{ before it hits } t) = \mathbb{P}^x(X_{\tau_{ \lbrace s,t \rbrace }}=s) $$

$V_x$ is (up to a constant**) a harmonic function, and the current on the edge $(x,y)$ is just $V_y - V_x$. It turns out $V_x$ may be chosen so that $(x,y) \mapsto V_y-V_x$ is in $\ell^2(E)$.

Are there any finer estimates on the decay of these functions (on the edges)? For example, might it even belong to $\ell^1(E)$?

$\textrm{ }$

*[Edit] Having one end implies being infinite, not X where X stands for cyclic, free, amalgamated product or HNN extension over a finite subgroup (a theorem of Stallings). One could add virtually before these adjectives but it is redundant (see HW's comment)

**[Edit] it could happen that the function is even less uniquely defined. For example, if there is a harmonic function with $\ell^2$ gradient on the graph $\Gamma \setminus e$. However, the element in $\overline{\nabla \ell^2(X)}^{\ell^2(E)}$ (see PPS below) is unique up to a constant. As far as my little knowledge of the topic is concerned, it might happen that this element is also not the best in terms of decay.

PS: it does not matter whether the edge $e$ is removed or not when defining the probability $V_x$.

PPS: this is classical, but a way to see that the current belongs in $\ell^2(E)$, is that $\ell^2(E)$ decomposes as $\overline{\nabla \ell^2(X)} + \ker \textrm{Div}$, projecting the Dirac at $e$ on the first factor gives the desired current (except on the edge $e$). [Edit: another way is given in Victor's answer below]

$\endgroup$
3
  • $\begingroup$ This isn't really my area so forgive me if this is phenomenally stupid: if $G$ is finite, then the function is automatically $\ell^1(E)$, right? So are you asking if there is a naturally-defined class of groups (containing the finite ones of course) for which the function will be $\ell^1(E)$? (i.e. this is true no matter what your choice of subset). Are you thinking that, in general, the function will be $\ell^1$ for all subsets of a given group, or for none of them? Or is it likely to depend on which Cayley graph of a given group you consider? $\endgroup$
    – Nick Gill
    Feb 14, 2013 at 16:33
  • $\begingroup$ Thanks for your questions. This isn't really my area either. But I was indeed thinking that $G$ was infinite (this was implicit in "assume $G$ has one end", but I admit it was unclear). So $G$ is not finite, virtually-cyclic or a free group (or a amalgamted product, etc...) As far as I know, this might depend on the choice of generating set. And I have no clue if it might actually belong to $\ell^1$ (or $\ell^p$ with $p<2$) for any group... $\endgroup$
    – ARG
    Feb 14, 2013 at 23:14
  • $\begingroup$ Your first 'Edit' isn't quite correct: having one end implies being infinite and not an amalgamated product or HNN extension over a finite subgroup. For instance, $\mathbb{Z}^2=\mathbb{Z}∗_{\mathbb{Z}}$ is of course, one-ended. You don't need the 'virtually': it's true that you can't be virtually cyclic, but virtually cyclic groups do in fact split as HNN extensions over a finite subgroup. You might like to mention that this is a theorem of Stallings. $\endgroup$
    – HJRW
    Feb 18, 2013 at 11:19

3 Answers 3

3
$\begingroup$

Do you ask the random walk on your group to be recurrent? As otherwise, you can have strange effects (take $\mathbb{Z}^3$, then the random walk on it hits a given point with probability less than one, so from one point charge you can have a current "flowing to infinity")...

Two remarks from the point of view of physical intuition:

0) [most probably, useless] The fact that the current function is in $l^2$ means that the total power dispersed by the flow is finite (on an edge $e$, you disperse the power $I_e^2 R$), and as the it should be equal to $U^2/R'$, where $R'$ is the equivalent resistance of your network, it means that $R'$ is positive (and this is rather natural: no matter what happens afterwards, you have only $2n$ edges attached to your starting point).

1) If you're asking for your function to be in $l^1$: this is a total number of electrons that are on their way in a given moment. It seems that its finiteness is equivalent for a random walk to be not only recurrent, but even having a finite expectation time of hitting $y$... Am I right here? If yes, it seems to me quite improbable to have such a possibility in an infinite group: I would expect that the distance to a given point can have a zero or positive drift, but not a negative one...

$\endgroup$
6
  • 1
    $\begingroup$ Note that if he group is cyclic or free nonabelian, the Cayley graphs are trees, so the function on edges is supported on a single edge in both cases. On the other hand, the first example gives you recurrent and the second - transient, random walks. On the other hand, I am not sure if integrability of this function is independent of the generating set. $\endgroup$
    – Misha
    Feb 14, 2013 at 23:02
  • $\begingroup$ @Victor: Thanks for your answer! About the probability being ill-defined in transient graphs: the statement is taken from Theorem 8 in Chapter XI of Bollobás' "Modern Graph Theory". I probably wrote it in a unclear fashion and it's certainly best to read the original, but if I should make an attempt to correct it when the group is transient I would try $V_x = \mathbb{P}($ a random walk starting at $x$ hits $s$ before $t |$ it hits either $s$ or $t)$. This fits with "if $e$ disconnects the graph the potential is constant on each of the two components" and preserves $V_x = \sum_y P_{xy} V_y$. $\endgroup$
    – ARG
    Feb 14, 2013 at 23:37
  • 2
    $\begingroup$ Antoine, are you sure about this definition of $V_x$? I don't think it is harmonic (certainly it isn't harmonic when defined on a general graph). $\endgroup$ Feb 16, 2013 at 2:43
  • $\begingroup$ Ori, did I already err in writing $V_x = \mathbb{P}^x(X_{\tau_{\lbrace s,t \rbrace}} = s)$? or in interpreting it? $\endgroup$
    – ARG
    Feb 16, 2013 at 12:50
  • 1
    $\begingroup$ Antoine, these theorems are about finite graphs. I don't have the book in front of me, but looking at the google preview I see that on pg. 307 it says: "let us turn to connected locally finite infinite networks." $\endgroup$ Feb 16, 2013 at 21:44
1
$\begingroup$

The current from a vertex to infinity in any graph is never in $\ell^1(E)$. Any cutset (that is, a set of edges separating the origin vertex from infinity) will contribute at least a constant to the $\ell^1$ norm, and there are infinitely many disjoint cutsets.

$\endgroup$
1
  • $\begingroup$ Thanks! I'm not familiar at all with such things, but even if the current from $1$ to $\infty$ is never in $\ell^1(E)$, the current between $1$ and a neighbour might still be...? $\endgroup$
    – ARG
    Feb 16, 2013 at 12:19
0
$\begingroup$

[Edit: add a heuristic argument for it not being $\ell^1$]

Trying to recycle the answer below and understand what was behind Ori and Victor' ideas:

The current from $1$ to $\infty$ is not in $\ell^1(E)$: take $S_n$ to be the sphere around $1$, and $T_n$ the edges between $S_n$ and $S_{n+1}$. Then the quantity of current in $T_n$ is constant for any $n$.

Assume very naively that $|T_n|$ is roughly $g'(n)$ where $g(n)$ is the growth function (i.e. $g(n) = | \cup_{0\leq i \leq n} S_n|$). Assume very optimistically that the current is uniformly distributed on $T_n$, i.e. $f(e') = 1/|T_n|$ if $e' \in T_n$.

Take the difference between this current $f$ and the one translated to get a current $\tilde{f}$ between $1$ and a neighbour. Assume very crudely that $\tilde{f}$ has values approximately the derivative of $f$. Then $\tilde{f}$ is roughly $g''(n)/g'^2(n)$ on edges at distance $n$ from $1$. So it would never be in $\ell^1$.

There is an obvious flaw in this argument: even if $\tilde{f}$ is a satisfactory current, it might not be the most appropriate (as in the [otherwise excluded] case where $e$ disconnects the graph, see Misha's comment above)

(This is also unhelpful for a decay intermediate between $\ell^1$ and $\ell^2$.)

[Edit: As Ori points out below, this answer is flawed (flow described does not satisfy the two Kirchhoff laws).]

This is just a partial answer, for the case $G=\mathbb{Z}^d$ ($d>1$). [Edit: For the usual generating set, answer may depend on generating set.]

If I'm not mistaken, there's an explicit formula for the current between $0$ and $\infty$ given as follows. Define the current on the first $2^d$-ant (points $x=(x_1,\ldots,x_d)$ with $x_i \geq 0$) as in Bollobás' "Modern Graph theory" proof of Theorem 14 p.309, namely the current between $x$ and $x+ e_i$ (where $e_i$ is a standard basis vector) is: $$ \frac{(x_i+1)}{(n+1)(n+2)\cdots(n+d)} \qquad \textrm{where } n = \sum_{i=1}^d x_i $$ Then sum this with similar currents defined on each $2^d$-ant to get the required harmonic current (except at $0$).

This gives a current between $0$ and $\infty$, obtain one between, say $(1,0,\ldots,0)$ and $\infty$ by simply translating. Take the difference of these two currents to get a (relatively explicit) formula for the current between $0$ and one of its neighbours. A rough estimate (inequalities are up to constants) for the $p$-summability is $$ \sum_{n\geq 0} \sum_{\sum x_i = n} \sum_{i=1}^d \frac{(x_i+1)^p}{n^p (n+1)^p \cdots (n+d)^p} \leq \sum_{n\geq 0} \binom{n+d}{d}\frac{1}{(n+1)^p \cdots (n+d)^p} \leq \sum_{n\geq 0} \frac{1}{n^{d(p-1)}} $$ So it is not in $\ell^1(E)$ but it belongs to $\ell^p(E)$ for $p> 1+\tfrac{1}{d}$.

So allow me to refine the initial question in:

  1. Are there similar estimates in more general groups $G$ on the current between the identity and $\infty$?

  2. Suppose $G$ is of exponential (or maybe superpolynomial) growth, does the current belongs to $\ell^1(E)$? (I guess that some monotonicity may be used to conclude directly it belongs to $\ell^p(E)$ for $p \in ]1,2]$).

$\endgroup$
2
  • 1
    $\begingroup$ What you write isn't the real current on an edge. Rather, it is the flow on this edge for a specific flow defined at the beginning of the paragraph. $\endgroup$ Feb 16, 2013 at 2:54
  • $\begingroup$ Perfectly right, thanks! May the potential of the current between $1$ and $\infty$ in a transient (Cayley) graph be obtained by looking at $V(x) = \sum_{n \geq 0} P^n(1,x)$ (as $PV(x) - V(x) = P^0(1,x) = $ dirac at $1$)? $\endgroup$
    – ARG
    Feb 16, 2013 at 12:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.