ISSN 2148-838Xhttps://doi.org/10.13069/jacodesmath.1056555 J. Algebra Comb. Discrete Appl. 9(2) • 71–78 Received: 17 March 2021 Accepted: 25 November 2021 Journal of Algebra Combinatorics Discrete Structures and Applications Growth of harmonic functions on biregular trees Research Article Francisco Javier González Vieli Abstract: On a biregular tree of degrees q + 1 and r + 1, we study the growth of two classes of harmonic functions. First, we prove that if f is a bounded harmonic function on the tree and x, y are two adjacent vertices, then |f(x) − f(y)| ≤ 2(qr − 1)‖f‖∞/((q + 1)(r + 1)), thus generalizing a result of Cohen and Colonna for regular trees. Next, we prove that if f is a positive harmonic function on the tree and x, y are two vertices with d(x, y) = 2, then f(x)/(qr) ≤ f(y) ≤ qr ·f(x). 2010 MSC: 31C20, 05C05 Keywords: Biregular tree, Growth, Harmonic function 1. Introduction A tree is homogeneous (or regular) if all its vertices have the same degree; it is biregular if any vertices x and y whose distance is even have the same degree, which we will assume greater than two. Regular and biregular trees are infinite. A complex valued function f defined on the vertices of a graph is harmonic at a vertex x if its value at x is the arithmetical mean of its values at the neighbours of x; the function is harmonic on the graph if it is harmonic at every vertex of the graph. The study of harmonic functions on graphs pertains to such diverse domains as probability [7], potential theory [1], graph theory or harmonic analysis. In particular, since the seminal work of Cartier [4] the properties of harmonic functions on regular trees have been thoroughly investigated (see for example [5], [1] and the references therein). Although they are quite straightforward generalizations of regular trees, biregular trees have not attracted a similar attention. Here we study the growth of harmonic functions on biregular trees using only elementary reasonings. In contrast to Rn [2, p.31], there are non-constant bounded harmonic functions on a regular tree of degree q + 1; but any such function f has its growth limited by the inequality |f(x) − f(y)| ≤ 2(q − 1)‖f‖∞/(q + 1) when x and y are adjacent [5, Theorem 1, p.65]. Here we generalize this result to Francisco Javier González Vieli; Montoie 45, 1007 Lausanne, Switzerland (email: francisco-javier.gonzalez @gmx.ch). 71 https://orcid.org/0000-0002-2245-5757 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 biregular trees: if f is a bounded harmonic function on a biregular tree T of degrees q + 1 and r + 1, and x, y are adjacent vertices, then |f(x)−f(y)| ≤ 2(qr −1)‖f‖∞/((q + 1)(r + 1)). An example shows that this inequality is the best possible. Also in contrast to Rn [2, p.45], there are non-constant positive harmonic functions on a biregular tree but they cannot grow too rapidly. We prove that if f is a positive harmonic function on T and x, y are vertices with d(x,y) = 2, then f(x)/(qr) ≤ f(y) ≤ qr · f(x). We give an example of a positive harmonic function which has maximal growth on a given infinite path (in the terminology of [3]) in T. 2. Bounded harmonic functions Let T be a biregular tree and fix a vertex x0 in T. We suppose that q + 1 is the degree of x0 (and of all vertices z with d(x0,z) even), and that r + 1 is the degree of all q + 1 neighbours of x0 (and of all vertices y with d(x0,y) odd). An easy induction shows that the number of points on the sphere with centre x0 and radius ρ (i.e. the set of vertices in T at distance ρ from x0) is given, for ρ ∈ N,ρ ≥ 1, by |S(x0,ρ)| = (q + 1)rbρ/2cqb(ρ−1)/2c, where we define bac = max{k ∈ Z : k ≤ a} for any a ∈ R. It follows that the number of points on the ball with centre x0 and radius ρ (i.e. the set of vertices in T at distance ≤ ρ from x0) is given, for ρ ∈ N,ρ ≥ 1, by |B(x0,ρ)| = 1 + ρ∑ j=1 (q + 1)rbj/2cqb(j−1)/2c. When the radius is even, this can be written |B(x0,2k)| = 1 + (q + 1)(r + 1) k−1∑ l=0 rl ql = 1 + (q + 1)(r + 1) (qr)k −1 qr −1 , and this result does not depend on the particular degree of x0. Take now a function f harmonic on T; this means that, for all x ∈ T, f(x) = 1 |S(x,ρ)| ∑ y∈S(x,ρ) f(y) when ρ = 1. An induction shows that this also holds for any ρ ∈ N, and then f(x) = 1 |B(x,ρ)| ∑ y∈B(x,ρ) f(y) for any ρ ∈ N. Proposition 2.1. Let T be a biregular tree of degrees q+1 and r+1. If f is a bounded harmonic function on T and x, y are two adjacent vertices in T, then |f(x)−f(y)| ≤ 2(qr −1) (q + 1)(r + 1) ‖f‖∞. (1) Proof. Take k ∈ N, k ≥ 1. We calculate |f(x)−f(y)| = ∣∣∣∣∣∣ 1|B(x,2k)| ∑ z∈B(x,2k) f(z)− 1 |B(y,2k)| ∑ z∈B(y,2k) f(z) ∣∣∣∣∣∣ 72 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 ≤ 1 |B(x,2k)| ∑ z∈B(x,2k)4B(y,2k) |f(z)| ≤ ‖f‖∞ |B(x,2k)4B(y,2k)| |B(x,2k)| = ‖f‖∞ 2(qr)k 1 + (q + 1)(r + 1)((qr)k −1)/(qr −1) , where B(x,2k)4B(y,2k) is the symmetric difference of the two balls. When k tends to +∞, we arrive at (1). Remark 2.2. For regular trees (q = r), this was first established in [5, Theorem 1, p.65]. The proof here is an adaptation of [6]. Is the inequality (1) the best possible? To answer this, we must construct a bounded harmonic function g such that, for some vertices x0 and x1, |g(x0) −g(x1)| is as large as possible with respect to ‖g‖∞. We take x0 ∈ T of degree q + 1 and x1 a neighbour of x0 (of degree r + 1). We put g(x0) = 0 and g(x1) = 1. The vertex x1 has r neighbours x (1) 2 , . . .x (r) 2 other than x0; in order to have ‖g‖∞ as low as possible, we must choose g to take the same value α2 at all these vertices, the harmonicity of g at x1 implying that α2 is given by the equation 1 r + 1 (0 + r ·α2) = 1. Hence α2 = (r + 1)/r. Every vertex x (j) 2 has q neighbours other than x1. Again we must choose g to take the same value α3 at all these vertices, the harmonicity of g at x (j) 2 implying that α3 is given by the equation 1 q + 1 (1 + q ·α3) = r + 1 r , and we find α3 = (1 + q + qr)/qr. Proceeding in this way, we construct a harmonic function g on T by defining g to take the same value αn at all vertices which are at distance n (n ∈ N, n ≥ 1) from x0 and at distance n−1 from x1, this value being αn = ∑n−1 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c if n is even, αn = ∑n−1 j=0 q b(j+1)/2crbj/2c qbn/2crb(n−1)/2c if n is odd; and by defining g to take the same value α−n at all vertices which are at distance n (n ∈ N, n ≥ 1) from x0 and at distance n + 1 from x1, this value being α−n = − ∑n−1 j=0 q bj/2crb(j+1)/2c qbn/2crbn/2c if n is even, α−n = − ∑n−1 j=0 q b(j+1)/2crbj/2c qb(n+1)/2crbn/2c if n is odd. The function g is bounded because supx∈T g(x) is equal to lim k→+∞ α2k = lim k→+∞ (1 + r) ∑k−1 j=0 (qr) j r(qr)k−1 73 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 = lim k→+∞ (1 + r)((qr)k −1)/(qr −1) r(qr)k−1 = (1 + r)q qr −1 and infx∈T g(x) is equal to lim k→+∞ α−2k = lim k→+∞ − (1 + r) ∑k−1 j=0 (qr) j (qr)k = lim k→+∞ − (1 + r)((qr)k −1)/(qr −1) (qr)k = − 1 + r qr −1 . Let now f = g − 1 2 (supx∈T g(x) + infx∈T g(x)), that is, f = g − 1 2 (q −1)(r + 1) qr −1 . Then f is harmonic on T, |f(x0)−f(x1)| = |g(x0)−g(x1)| = 1 and ‖f‖∞ = sup x∈T f(x) = − inf x∈T f(x) = (1 + r)(1 + q) 2(qr −1) , Conclusion 2.3. The inequality (1) is the best possible, being in fact, for the function f just defined and the vertices x0 and x1, an equality. 3. Positive harmonic functions Lemma 3.1. Let x0 and x1 be two adjacent vertices in a biregular tree T, with x0 of degree q + 1. If f is a real valued harmonic function on T, there exists an infinite path (x0,x1, . . . ,xm, . . .) in T such that, for all m ∈ N, m ≥ 2, we have f(xm) ≤ (r + 1)f(xm−1)−f(xm−2) r if m is even, (2) f(xm) ≤ (q + 1)f(xm−1)−f(xm−2) q if m is odd. (3) Proof. Among the r neighbours of x1 which are not x0, we write x2 the one where f takes its smaller value, and x(1)2 , . . . ,x (r−1) 2 the other neighbours: f(x2) ≤ f(x (j) 2 ) for all j = 1, . . . ,r − 1. Since f is harmonic, f(x0) + f(x2) + f(x (1) 2 ) + · · ·+ f(x (r−1) 2 ) r + 1 = f(x1); (4) hence f(x2) + f(x (1) 2 ) + · · ·+ f(x (r−1) 2 ) = (r + 1)f(x1)−f(x0). 74 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 From the choice of x2, we get f(x2) ≤ (r + 1)f(x1)−f(x0) r . This establishes the assertion for the case m = 2. Among the q neighbours of x2 which are not x1, we write x3 the one where f takes its smaller value. A similar argument as above gives f(x3) ≤ (q + 1)f(x2)−f(x1) q . This establishes the assertion for the case m = 3. Proceeding in this way we construct the needed path step by step. Lemma 3.2. Let x0 and x1 be two adjacent vertices in a biregular tree T, with x0 of degree q + 1. Let f be a real valued harmonic function on T, and (x0,x1, . . . ,xm, . . .) an infinite path in T such that, for all m ≥ 2, (2) and (3) hold. Then, for all n ∈ N, n ≥ 2, f(xn) ≤ ∑n−1 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x1)− ∑n−2 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x0) (5) if n is even, and f(xn) ≤ ∑n−1 j=0 q b(j+1)/2crbj/2c qbn/2crb(n−1)/2c f(x1)− ∑n−2 j=0 q b(j+1)/2crbj/2c qbn/2crb(n−1)/2c f(x0) (6) if n is odd. Proof. By induction on n. The case n = 2 is the hypothesis (2). We next turn to the case n = 3. By assumption f(x3) ≤ 1 q [ (q + 1)f(x2)−f(x1) ] and f(x2) ≤ 1 r [ (r + 1)f(x1)−f(x0) ] . Hence f(x3) ≤ 1 q [ (q + 1) 1 r { (r + 1)f(x1)−f(x0) } −f(x1) ] ≤ 1 q [ 1 r (q + 1)(r + 1)f(x1)− 1 r (q + 1)f(x0)−f(x1) ] ≤ 1 q [ (q + 1)(r + 1)−r r f(x1)− q + 1 r f(x0) ] ≤ 1 + q + qr qr f(x1)− 1 + q qr f(x0). The case n = 3 is proved. We suppose now that n > 3 and that the lemma is true for n− 1. We first consider the case where n is even. Then (x1,x2, . . . ,xn) is a path of odd length n−1 in T which satisfies (2) and (3) if we invert the roles of q and r. The induction hypothesis then gives (we invert the roles of q and r in (6)) f(xn) ≤ ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c f(x2)− ∑n−3 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c f(x1). 75 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 But f(x2) ≤ 1 r [ (r + 1)f(x1)−f(x0) ] = ( 1 + 1 r ) f(x1)− 1 r f(x0). Hence f(xn) ≤ ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c (( 1 + 1 r ) f(x1)− 1 r f(x0) ) − ∑n−3 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c f(x1) = ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c f(x1) + ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2cr f(x1) − ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2cr f(x0)− ∑n−3 j=0 r b(j+1)/2cqbj/2c rb(n−1)/2cqb(n−2)/2c f(x1) = rb(n−2+1)/2cqb(n−2)/2c rb(n−1)/2cqb(n−2)/2c f(x1) + ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n+1)/2cqb(n−2)/2c f(x1) − ∑n−2 j=0 r b(j+1)/2cqbj/2c rb(n+1)/2cqb(n−2)/2c f(x0) = rbn/2cqb(n−1)/2c rbn/2cqb(n−1)/2c f(x1) + ∑n−2 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x1) − ∑n−2 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x0) = ∑n−1 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x1)− ∑n−2 j=0 q bj/2crb(j+1)/2c qb(n−1)/2crbn/2c f(x0), where, for the last equality but one, we have used the fact that, since n is even, b(n + 1)/2c = bn/2c and b(n−1)/2c = b(n−2)/2c. We have thus proved (5). The case n odd can be handled in a similar manner. Proposition 3.3. Let T be a biregular tree of degrees q+1 and r+1, and x0 and x1 two adjacent vertices in T with x0 of degree q + 1. If f is a positive harmonic function on T, then q + 1 q(r + 1) f(x0) ≤ f(x1) ≤ r(q + 1) (r + 1) f(x0). Proof. By lemma 3.1, there exists an infinite path (x0,x1, . . . ,xm, . . .) in T such that, for all m ≥ 2, (2) and (3) hold. We can then use (6) with n = 2k + 1 and find f(x2k+1) ≤ (qr)k + (1 + q) ∑k−1 j=0 (qr) j (qr)k f(x1)− (1 + q) ∑k−1 j=0 (qr) j (qr)k f(x0). Since f(x2k+1) is positive, this implies (qr)k + (1 + q) ∑k−1 j=0 (qr) j (qr)k f(x1) ≥ (1 + q) ∑k−1 j=0 (qr) j (qr)k f(x0). 76 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 and so f(x1) ≥ (1 + q) ∑k−1 j=0 (qr) j (qr)k + (1 + q) ∑k−1 j=0 (qr) j f(x0) = (1 + q)((qr)k −1)/(qr −1) (qr)k + (1 + q)((qr)k −1)/(qr −1) f(x0) = (1 + q)((qr)k −1) (qr)k(qr −1) + (1 + q)((qr)k −1) f(x0) = (1 + q)((qr)k −1) qk+1rk+1 −qkrk + qkrk + qk+1rk −1−q f(x0) = (1 + q)((qr)k −1) qk+1rk+1 + qk+1rk −1−q f(x0) = (qr)k(1 + q)− (1 + q) q(qr)k(r + 1)− (1 + q) f(x0). When k tends to +∞, we find f(x1) ≥ 1 + q q(r + 1) f(x0). Inverting the roles of x0 and x1, as well as the roles of q and r, we get f(x0) ≥ 1 + r r(q + 1) f(x1). The conclusion follows. Corollary 3.4. Let T be a biregular tree of degrees q + 1 and r + 1. If f is a positive harmonic function on T and x, y are two vertices in T with d(x,y) = 2, then 1 qr f(x) ≤ f(y) ≤ qr ·f(x). Proof. First, we suppose that x is of degree q + 1. Let z be the vertex in T with d(x,z) = 1 = d(z,y). By Proposition 3.3 we get f(y) ≥ r + 1 r(q + 1) f(z) ≥ r + 1 r(q + 1) · q + 1 q(r + 1) f(x) = 1 rq f(x). The other inequality is obtained by inverting the roles of x and y. For x of degree r + 1, invert the roles of q and r in the preceding reasoning. Let ζ = (. . . ,x−2,x−1,x0,x1,x2, . . .) be an infinite path in T, with x0 of degree q + 1. Is it possible to find a positive harmonic function f on T such that its growth along this path is maximal? If we fix f(x0) = 1, then we deduce from proposition 3.3 and corollary 3.4 that we must set, for all k ∈ Z, f(x2k) = (qr) k and f(x2k+1) = (qr)k r(q + 1) r + 1 . (7) Consider now the r−1 neighbours of x1 other than x0 and x2. If we suppose that f takes the same value α on all these vertices, then the harmonicity of f at x1 implies that (f(x0)+f(x2)+(r−1)α)/(r+1) = f(x1) or 1 r + 1 (1 + qr + (r −1)α) = r(q + 1) r + 1 . 77 F. J. González Vieli / J. Algebra Comb. Discrete Appl. 9(2) (2022) 71–78 Hence 1 + qr + (r−1)α = rq + r and finally α = 1 = f(x0). This also shows that f must take this same value on these r−1 neighbours, because if it was not the case, the value on at least one neighbour, y say, would be less than 1, contradicting proposition 3.3 applied to y and x1. Consider next the q − 1 neighbours of x0 other than x−1 and x1. If we suppose that f takes the same value β on all these vertices, then the harmonicity of f at x0 implies that (f(x−1) + f(x1) + (q − 1)β)/(q + 1) = f(x0) or 1 q + 1 ( q + 1 q(r + 1) + r(q + 1) r + 1 + (q −1)β ) = 1, whose solution is β = (q + 1)/(q(r + 1)) = f(x−1). This also shows that f must take this same value on these q − 1 neighbours, because if it was not the case, the value on at least one neighbour, y say, would be less than (q + 1)/(q(r + 1)), contradicting proposition 3.3 applied to y and x0. Conclusion 3.5. Given an infinite path ζ = (. . . ,x−2,x−1,x0,x1,x2, . . .) in T with x0 of degree q + 1, there exists one and only one positive harmonic function f on T with f(x0) = 1 such that f has maximal growth along ζ. On ζ, f is given by (7) and on a vertex y not in ζ it is defined as follows: let x be the vertex in ζ closest to y, and n the distance between x and y; then f(y) =   f(x) · (qr)−k if n = 2k, f(x) · (qr)−k q + 1 q(r + 1) if n = 2k + 1. Remark 3.6. Proposition 3.3 and corollary 3.4 are in fact true for positive superharmonic functions on T. (A function is superharmonic at a vertex x if its value at x is greater or equal to the arithmetical mean of its values at the neighbours of x.) This follows from the fact that lemma 3.1 and lemma 3.2 are true for real valued superharmonic functions. Indeed, we can modify the proof of lemma 3.1 by changing (4) to f(x0) + f(x2) + f(x (1) 2 ) + · · ·+ f(x (r−1) 2 ) r + 1 ≤ f(x1); hence f(x2) + f(x (1) 2 ) + · · · + f(x (r−1) 2 ) ≤ (r + 1)f(x1) −f(x0). The end of the proof needs no change, and neither do the other proofs need one. References [1] V. Anandam, Harmonic functions and potentials on finite and infinite networks, Springer, Heidelberg, Bologna (2011). [2] S. Axler, P. Bourdon, W. Ramey, Harmonic function theory, Springer-Verlag, New York (2001). [3] N. L. Biggs, Discrete mathematics, Clarendon Press, Oxford University Press, New York (1985). [4] P. Cartier, Fonctions harmoniques sur un arbre, Sympos. Math. 9 (1972) 203–270. [5] J. M. Cohen, F. Colonna, The Bloch space of a homogeneous tree, Bol. Soc. Mat. Mex. 37 (1992) 63–82. [6] E. Nelson, A proof of Liouville’s theorem, Proc. Amer. Math. Soc. 12(6) (1961) 995. [7] W. Woess, Random walks on infinite graphs and groups, Cambridge University Press (2000). 78 https://doi.org/10.1007/978-3-642-21399-1 https://doi.org/10.1007/978-3-642-21399-1 https://doi.org/10.1007/978-1-4757-8137-3 https://dl.acm.org/doi/10.5555/533687#secAbs https://mathscinet.ams.org/mathscinet-getitem?mr=0353467 https://mathscinet.ams.org/mathscinet-getitem?mr=1317563 https://mathscinet.ams.org/mathscinet-getitem?mr=1317563 https://doi.org/10.2307/2034412 https://doi.org/10.1017/CBO9780511470967 Introduction Bounded harmonic functions Positive harmonic functions References