[math-fun] Averaging functions on trees
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, 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. ----- Let C denote all functions V(G) —> reals: C = {f : V(G) —> R} For any v in V let the star star(v) of v be the set of vertices w at the other end of all edges vx containing v: star(v) = {x in V | vx is in E} Define A : C —> C by letting A(f) at a vertex v be the average of f(x) on the star of v: A(f)(v) = (Sum_{x in star(v)} f(x)) / |star(v)|. Question: Which f in C approach a limit under iteration of A: lim A^n(f) = f^ n—>oo for some f^ in C ??? —Dan
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. Andy
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
participants (2)
-
Andy Latto -
Dan Asimov