Potential Theory and the Boundary of Combinatorial Graphs

Abstract

Let $G=(V,E)$ be a finite, connected graph. We investigate a notion of boundary $\partial G\subseteq V$ and argue that it is well behaved from the point of view of potential theory. This is done by proving a number of discrete analogous of classical results for compact domains $\hat{I}\text{c◯}\subset {\mathbb{R}}^d$. These include (1) an analogue of Pólya's result that a random walk in $\hat{I}\text{c◯}$ typically hits the boundary $\partial \hat{I}\text{c◯}$ within $\lesssim \mbox{diam}(Ω)^2$ units of time, (2) an analogue of the Faber-Krahn inequality, (3) an analogue of the Hardy inequality, (4) an analogue of the Alexandrov-Bakelman-Pucci estimate, (5) a stability estimate for hot spots and (6) a Theorem of Björck stating that probability measures $\hat{I}¼$ that maximize ${\int }_{\hat{I}\text{c◯}\times \hat{I}\text{c◯}}\Vert x-y{\Vert }^{\hat{I}}\pm d\hat{I}¼(x)d\hat{I}¼(y)$ are fully supported in the boundary.