Cogrowth of Arbitrary Graphs

Abstract. A “cogrowth set ” of a graph G is the set of vertices in the universal cover of G which are mapped by the universal covering map onto a given vertex of G. Roughly speaking, a cogrowth set is large if and only if G is small. In particular, when G is regular, a cogrowth constant (a measure of the size of the cogrowth set) exists and has been shown to be as large as possible if and only if G is amenable. We present two approaches to the problem of extending this to the non-regular case. First, we show that the result above extends to the case when G is not regular but is the cover of a finite graph. This proof is based on some properties of a family of Laplacians related to the zeta function of the covered graph. An example is given where this result fails when G does not cover a finite graph. Second, for any graph with transient covering tree, we define a new cogrowth constant expressed in terms of harmonic measure and show that G is amenable if and only if this constant is 1. Finally, we show that if G covers a finite graph, then the radial limit set of a cogrowth set has largest possible Hausdorff dimension if and only if G is amenable. 1