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) $$
Categories: math.CO