Lipschitz Functions on Sparse Graphs

Abstract

In this work we attempt to count the number of integer-valued $h$-Lipschitz functions (functions that change by at most $h$ along edges) on two classes of sparse graphs; grid graphs $L_{m,n}$, and sparse random graphs $G(n,d/n)$. We find that for all $n$-vertex graphs $G$ with $k$ connected components, the number of such functions grows as $(ch{)}^{n-k}$ for some $1\le c\le 2$. In particular, letting $\alpha \approx 1.16234$ be the largest solution to $\tan (1/x)=x$, we prove that as $n\to \infty$ $$c=\alpha \sqrt{2}\approx 1.6438\text{when}G=L_{2,n}$$ and $$1.351\approx {\alpha }^2\le c\le \arctan {(3/4)}^{-1}\approx 1.554\text{when}G=L_{n,n}$$ and $$1+\frac{1}{2d}+O\left(\frac{1}{d^2}\right)\le c\le 1+\frac{4{\ln }^{2}d}{d}+O\left(\frac{1}{d}\right)\text{(w.h.p.) when}G=G(n,d/n)$$

15 pages