2 edited body

A nice application is showing that every Cayley graph of an Abelian group with a set of generators of logarithmic size has also logarithmic diameter.

More precisely, let $G$ is be an Abelian group and let $S$ be a symmetric generating set for $G$ of size $d = c_{0} \log n$ (where $n = |G|$ and $c_{0} > 0$ is a constant. Then for any $c_{1} > 0$ such that: $$(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) < 1$$

we have $diam(G) \geq c_{1} \log n$, where $diam(G)$ is the diameter of the Cayley graph of $G$ with generating set $S$.

The proof uses a simple observation that the number of distinct pairs of endpoints of paths of length $l$ is at most $\binom{d+l}{l}$, since to determine an element of $G$ as a word in generators we only need to specify which generator appears how many times (because of commutativity the order is unimportant). So we have: $$\sum\limits_{l=0}^{c_{1} \log n} \binom{c_{0}\log n + l}{l} \leq 2^{(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) \log n} < n$$ so the number of vertices reachable from a fixed vertex by a path of length $l \leq c_{1}\log n$ is strictly smaller than $n$. This implies that $diam(G) \geq c_{1}\log n$.

This fact is used by Newman and Rabinovich in "Hard Metrics From Cayley Graphs Of Abelian Groups" to give a simple example of an $n$-point metric space which requires distortion $\Omega(\log n)$ to embed it into $\ell_{2}$.

1

A nice application is showing that every Cayley graph of an Abelian group with a set of generators of logarithmic size has also logarithmic diameter.

More precisely, let $G$ is an Abelian group and let $S$ be a symmetric generating set for $G$ of size $d = c_{0} \log n$ (where $n = |G|$ and $c_{0} > 0$ is a constant. Then for any $c_{1} > 0$ such that: $$(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) < 1$$

we have $diam(G) \geq c_{1} \log n$, where $diam(G)$ is the diameter of the Cayley graph of $G$ with generating set $S$.

The proof uses a simple observation that the number of distinct pairs of endpoints of paths of length $l$ is at most $\binom{d+l}{l}$, since to determine an element of $G$ as a word in generators we only need to specify which generator appears how many times (because of commutativity the order is unimportant). So we have: $$\sum\limits_{l=0}^{c_{1} \log n} \binom{c_{0}\log n + l}{l} \leq 2^{(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) \log n} < n$$ so the number of vertices reachable from a fixed vertex by a path of length $l \leq c_{1}\log n$ is strictly smaller than $n$. This implies that $diam(G) \geq c_{1}\log n$.

This fact is used by Newman and Rabinovich in "Hard Metrics From Cayley Graphs Of Abelian Groups" to give a simple example of an $n$-point metric space which requires distortion $\Omega(\log n)$ to embed it into $\ell_{2}$.