Lipschitz Functions on Sparse Graphs II

Korsky, Saffat and Aiylam introduced a growth constant $c(G)$ for integer-valued $h$-Lipschitz functions on a finite graph $G$ and proved that, for $G=G(n,d\mathrm{/}n)$, $$\frac{1}{2d}+O(d^{-2})\le \log c(G)\le \frac{4{\log }^{2}d}{d}+O(d^{-1})$$ with high probability. We sharpen the random-graph part of their result; as $n\to \mathrm{\infty }$ and then $d\to \mathrm{\infty }$, we prove $$\log c(G)=\frac{{\pi }^2}{6d}+o(d^{-1})$$ with high probability. Additionally, we derive bounds on $\log c(Q_d)$ where $Q_d$ is the $d$-dimensional hypercube graph: $$\frac{{\pi }^2}{6d}+o(d^{-1})\le \log c(Q_d)\le (\frac{3}{4}+o(1))\frac{\log d}{d}\mathrm{.}$$