Cogrowth of regular graphs

Abstract:

Let $\mathcal {G}$ be a $d$-regular graph and $T$ the covering tree of $\mathcal {G}$. We define a cogrowth constant of $\mathcal {G}$ in $T$ and express it in terms of the first eigenvalue of the Laplacian on $\mathcal {G}$. As a corollary, we show that the cogrowth constant is as large as possible if and only if the first eigenvalue of the Laplacian on $\mathcal {G}$ is zero. Grigorchuk’s criterion for amenability of finitely generated groups follows.