Thinking about things more, I would make the following conjecture about convergence. Choose a vertex V of the graph, and let d(V, n) be the set of vertices whose shortest path to V is of length <= n, and let Avg(V, n, f) be the average value of f at the points of d(V,n). Then I conjecture that im A^2n(f) = f^ n—>oo exists (with pointwise convergence) just if lim sup Avg(V, n, f) is finite. n—>oo Andy On Mon, Mar 5, 2018 at 8:22 AM, Andy Latto <andy.latto@pobox.com> wrote:
But I am surprised to hear that A^2n(f) (or A^(2n+1)(f)) might converge for *all* f. Can't I make f increase so fast in terms of distance from some fixed point P that A^(2n)(f)(P), say, gets arbitrarily large as n —> oo ?
You're right, I was misled by bad analogies to the finite case. In particular, the map from f to
lim A^2n(f) = f^ n—>oo
is linear. For vertices p and q, we can define
T(p, q) = f^(q), where f(p) = 1 and f(x) = 0 for p != q.
This is well defined, assuming that f^(even) always converges when f takes on only finitely many non-zero values, which I'm pretty sure of.
Determining convergence once the "transfer function" T has been computed is pretty straightforward; it converges at q just if sum_p (f(p) * T(p,q) converges.
T of course depends on the graph, but I'm not sure there's a simple formula for arbitrary graphs, though calculating it for some simple graphs like an infinite chain, a semi-infinite chain, and a complete tree of degree n seems like a good starting point for understanding T.
Andy
—Dan
Andy Latto wrote: ----- On Sun, Mar 4, 2018 at 2:41 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Let G be an infinite connected graph
G = (V, E)
where V is a countably infinite set and E is a subset of V x V - diagonal,
You don't say whether (x, y) can be in E while (y, x) is not. Are you asking about directed or undirected graphs?
The subject line refers to trees: did you intend to also specify the graph is acyclic?
satisfying 1) and 2):
----- 1) Every edge e in E has 2 endpoints, and any 2 vertices v,w in V bound at most one edge.
2) If for any v in V, deg(v) denotes the number of edges v belongs to, then for all v we have
2 <= deg(v) < oo.
-----
Question: Which f in C approach a limit under iteration of A:
lim A^n(f) = f^ n—>oo
for some f^ in C ???
I don't have a proof yet, but I assuming we're talking about undirected graphs, I believe that this will converge for all f if G is not bipartite. If G is a bipartite graph, which includes all acyclic graphs, then I think that
lim A^2n(f) = f^ n—>oo
and
lim A^(2n+1)(f) = f^ n—>oo
Will always both exist, but will generally be different. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
-- Andy.Latto@pobox.com