Properties of p-modulus on radially symmetric infinite trees

Abstract

On a finite graph, the p-modulus of a family of paths takes the form of a standard convex optimization problem. The optimal value of this problem provides information about the underlying graph, and has been shown to be closely related to several important graph theoretic quantities including shortest path, effective resistance, and minimum cut. Some of these concepts have meaningful and interesting extensions to infinite graphs. For example, certain effective resistance calculations on infinite trees are known to be related to the transience or recurrence of random walks on these trees. The goal of this dissertation is to extend the theory of p-modulus to the case of infinite trees. While many known results from finite graphs have analogs in the infinite tree setting, the infinite nature of the problem setting gives rise to a number of interesting and subtle properties. For example, while modulus problems on a finite graph involve optimization in a finite-dimensional space with a finite number of constraints, the corresponding problem on an infinite tree requires optimization over a countably infinite number of decision variables with an uncountably infinite number of constraints. This makes the analysis both more interesting and more complex. This dissertation first establishes the theory of p-modulus (specifically, the theory of p-modulus of a family of infinite paths) on an infinite rooted tree, then explores its interpretation and properties. One key result is the formulation of p-modulus in the infinite tree as a limit of p-modulus on truncated trees, with a formula given in terms of a series. The convergence of the series implies a positive modulus, while divergence implies that the modulus is zero. This distinction between trees with positive modulus and trees with zero modulus plays an important role in this dissertation. The value of modulus is related to the ``bushiness'' of the tree at infinity; trees which branch many times have larger modulus, while trees that do not branch much have smaller modulus. In fact, if a tree does not branch sufficiently, its modulus may be zero, a fact that is related to the recurrence of a random walk on the tree when the parameter p in the p-modulus equals 2. This dissertation extends previous results on modulus for finite graphs by showing that 1-modulus is related to the minimum cut problem, 2-modulus is related to effective resistance, and infinity-modulus is related to the shortest path. Another key result of this dissertation is the existence of a critical p-value for certain trees. The value of p-modulus when p is above this critical value is zero, while the value of p-modulus when p is below the critical value is positive. This provides a sense of ``dimension'' for the tree. As one particular application, this dissertation also connects the value of this critical exponent to the transience or recurrence of a random walk.