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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$ Commented 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
    Commented 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$ Commented 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
    Commented 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$ Commented 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
    Commented Feb 16, 2013 at 12:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .